Trees#
Contents#
A tree is an undirected acyclic graph \(G = (V, E)\).
Parent-child nomenclature
The node that has no parent node is called the root node. (The root node is usually the entrypoint into the tree, and the starting point of tree algorithms.)
A node without child nodes is a called leaf node.
A node that is not a leaf node is called an internal node.
A node should have at most one parent node. If there is a node with more than one parent node then the “tree” has a cycle (which then by definition makes it not a tree).
The trivial tree consists of the root node that is also a leaf node.
A nontrivial tree consists of the root node that is an internal node, which means that it has at least one child node.
Fanout (or maximum degree) is the number of child nodes. This term may be used with respect to the entire tree, or with respect to a particular node.
\(\text{height} = \log_\text{fanout} |V|\)
Binary Trees#
fanout = 2, every node has at most 2 child nodes
A complete binary tree is a tree in which each node has as many children as it possibly can, except for the last level of the tree
Binary trees facilitate high-speed searching and sorting of data, efficient elimination of duplicate data items, representing file system directories and compiling expressions into machine language.
tree traversal
lookup of a value
insert a value into the heap
Binary Heap#
A binary heap is a complete binary tree in which each node satisfies the heap property.
Max Heap
every node must be larger than its children
the root is the largest element
Min Heap
every node must be smaller than its children
the root is the smallest element
Efficient access to the min (or max), which is useful for something like a priority queue.
When a new node is inserted into the tree, it may not satisfy the min (or max) heap property and so the tree may need to be adjusted. The up-heap operation repeatedly looks at the node and its parent and swaps them if the node is smaller than its parent in the case of min heap. Thus the cost of inserting a node into the tree is the sum of the costs of finding the appropriate insertion location and of the upheap operation which maintains the heap property.
The cost of the up-heap operation is \(\Theta(\log_2 |V|)\)
The cost of inserting a node into the correct location in the tree depends on the details of the implementation of the heap. In a linked-list implementation, we have to traverse the tree starting from the root:
\(O(|V|)\)
struct T = {
int val;
T *l_child;
T *r_child;
};
The insertion cost in a linked-list approach might be optimized by tracking a pointer to the next insertion spot, or other ways.
The other way to implement is with an array, which only requires \(\Theta(1)\) insertion. The first element is the root
\( \begin{aligned} \text{level} &= i \\ \text{left\_subtree} &= 2i + 1 \\ \text{right\_subtree} &= 2i + 2 \\ \end {aligned} \)
\( \begin{aligned} i &= 0 \\ \text{l}_0 &= 1 \\ \text{r}_0 &= 2 \\ i &= 1 \\ \text{l}_1 &= 3 \\ \text{r}_1 &= 4 \\ \end {aligned} \)
In an array implementation, use a down-heap operation to pop the root node.
Removing the root node as-is would require shifting the entire array to fill the hold, which would require linear time. By using a down-heap operation, we reduce this cost to \(\log_2 |V|\)
Down-heap
First swap root with last node
Pop the root node from the end of the array
Perform down-heap on the new root to maintain heap property
max heap: swap node with largest child
min heap: swap node with smallest child
Insertion
add new node at the end of the array \(\Theta(1)\)
up-heap until the heap property is satisfied \(O(\log_2 |V|)\)
Pop
swap the root with the last node \(\Theta(1)\)
down-heap until the heap property is satisfied \(O(\log_2 |V|)\)
max heap: swap node with largest child
min heap: swap node with smallest child
Update value (increase priority of PQ)
Delete an arbitrary node
Terms#
[ w ] Arborescence
[ w ] Binary Heap
[ w ] Binary Tree
[ w ] Binary Search Tree
[ w ] Branching Factor
[ w ] d-ary Heap
[ w ] Heap
[ w ] k-ary Tree
[ w ] Node
[ w ] Parse Tree
[ w ] Search Tree
[ w ] Splay Tree
[ w ] Ternary Search Tree
[ w ] Ternary Tree
[ w ] Tree (data structure)
[ w ] Tree (graph theory)
[ w ] Tree Structure
[ w ] Tree Traversal