Trees and Graphs Flashcards
Trees
Data structures with a root node and children nodes. Each child may also have children. The tree does not contain cycles.
Binary Trees
A tree in which each node has up to two children
Leaf Node
A node with no children.
Binary Search Tree
A binary tree in which every node fits a specific ordering property: left descendants <= n < all right descendants. This must be true for each node n and all of node n’s descendants, not just immediate children. Some binary search trees cannot have duplicates, others will have duplicates on the right, or either side.
Balanced Tree
Balanced enough to ensure O(log n) for insert and find, but not necessarily perfectly balanced.
Complete Binary Tree
A binary tree in which every level of the tree is completely filled, except for maybe the last level. Filling on the last level is from left to right.
Full Binary Tree
A binary tree in which every node has either zero or two children. No nodes have only one child.
Perfect Binary Tree
All Interior node have two children and all leaf nodes are at the same level.
Number of Nodes in a Perfect Binary Tree
The first level has 20, the second level has 21, the ith level has 2(i-1) and the last level has 2(N-1) where N is the depth of the tree. Total: 2**N - 1.
In-Order Binary Tree Traversal
Visit the left branch, then the current node, and finally, the right branch. When performed on a binary search tree, it visits the nodes in ascending order.
Implement In-Order Binary Tree Traversal
If node is not null, traverse the left child, then visit the center node, and then traverse the right child.
Pre-Order Binary Tree Traversal
Visits the current node before its child nodes. The root is always the first node visited.
Implement Pre-Order Binary Tree Traversal
if node is not null, visit the current node, traverse the left child node, then traverse the right child node.
Post-Order Tree Traversal
Visits the current node after its child nodes. The root is always the last node visited.
Implement Post-Order Tree Traversal
if node is not null, traverse the left child node, then traverse the right child node, then visit the current node.
Min-Heaps
Complete binary tree where each node is smaller than its children. The root is the minimum element of the tree. Two key operators exist: insert and extract_min
Max-Heaps
Same as a min-heap, but elements are in descending order.
insert
start by inserting the element at the bottom of the min-heap. Insert at the next available spot, so as to maintain the complete tree property. Then fix tree by swapping the new element with its parent, until we find an appropriate spot for the element. Bubble up mini element. This takes O(log n).
Extract Minimum Element (Min Heap, Binary Search Tree)
Remove the min element and swap it with the last element in the heap. Then, bubble down element, swapping it with its smaller child until the min-heap property is restored. The algorithm will take O(log n) time.
Tries (Prefix Trees)
Variant of an n-ary tree in which characters are stored at each node. Null or * words indicate the end (like the end of a word). Very commonly used to store the entire language for quick prefix lookups.
Graphs
A collection of nodes connected by edges. Graphs can either be directed or undirected. Graphs may contain more than one disconnected sub-graphs.
Connected Graph
A path exists between every pair of vertices of a graph.
Acyclic Graph
Contains no cycles.
Adjacency List
Every vertex or nodes stores a list of adjacent vertices. An undirected node will store each edge twice.
Implement Adjacency List
One Graph Class with field nodes. One Node class with field children and field data.
Adjacency Matrices
An NxN boolean matrix where N is the number of nodes in the graph. A true value at matrix[i][j] means edge from node i to node j. Undirected graphs have symmetric matrices.
Depth-First Search
Start at root node or arbitrarily selected node, and explore each branch completely. DFS is preferred if we want to visit every node in the graph. Tree traversal algorithms are simpler forms of DFS, but w/o markers.
Breadth-First Search
Start at root node or arbitrarily selected node, and explore each neighbor before moving onto any of their children. BFS is preferred if we want to find the shortest path between two nodes.
Implement DFS
Recursive function searching a root node. If root node is null, return. Visit root, then mark it as visited. For each neighboring node, if node is not visited, search it recursively.
Implement BFS
Use a method that searches the root node using a queue. Set root to marked. Enqueue the root. While queue is not empty, dequeue a node, visit the node. For all adjacent nodes, if the adjacent node is not marked, set it to mark, and enqueue the adjacent node.
Bidirectional Search
Finds shortest path between a source and destination node. Two BFS run simultaneously from each node.
Run time of BS vs. BFS
BS will have O(kd/2) while BFS will have O(kd) if we assume each node has at most k connections. This is because searching each level will require k*number of nodes we are searching. Previous levels will have at most k nodes.
