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.
