Learn about tree, tree traversal, binary heap, trie and their running time.
Tree
- Tree is a data structure composed of nodes.
- Each tree has a root node.
- The root node has zero or more child nodes.
- Each child node has zero or more child nodes, and so on.
- Features of tree
- Tree cannot contain cycles.
- The nodes may or may not be in a particular order.
- They may or may not have links back to their parent nodes.
Trees vs. Binary Trees
- Binary tree is a tree in which each node has up to two children.
- Other than that, it will be \(n\)-ary tree.
- A node is called a leaf node if it has no children.
Binary Tree vs. Binary Search Tree
- Binary search tree is a binary tree in which every node fits a specific ordering property:
- For each node \(n\), \(\text{all left descendents} <= n < \text{all right descendents}\)
- In some definitions, the tree cannot have duplicate values.
- In others, the duplicate values will be on the right or can be on either side.
Balanced vs. Unbalanced
- In order to guarantee that \(H = \log N\) (\(H\):height, \(N\): number of nodes), we can force the tree to be height-balanced.
- Relation between \(H\) and \(N\) in a tree can vary from \(H=N\) (degenerate tree) to \(H=\log N\).
- Two common types of balanced trees are red-black trees and AVL trees
Complete Binary Trees
- Complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level.
Full Binary Trees
- Full binary tree is a binary tree in which every node has either zero or two children, no nodes have only one child.
Perfect Binary Trees
- Perfect binary tree is one that is both full and complete.
- A perfect tree must have exactly \(2^k-1\) nodes where \(k\) is the number of levels.
Binary Tree Traversal
Pre-Order Traversal
- In a pre-order traversal, the root of tree is visited first and then the subtrees rooted at its children are traversed recursively.
- Time complexity: \(O(n)\), where \(n\) is the number of positions in the tree.
Algorithm preorder(T, p):
perform the "visit" action for position p
for each child c in T.children(p) do
preorder(T,c) # recursively traverse the subtree rooted at c
Post-Order Traversal
- In a post-order traversal, it recursively traverses the subtrees rooted at the children of the root first, and then visits the root.
- Time complexity: \(O(n)\), where \(n\) is the number of positions in the tree.
Algorithm postorder(T, p):
for each child c in T.children(p) do
postorder(T,c) # recursively traverse the subtree rooted at c
perform the "visit" action for position p
In-Order Traversal
- In a in-order traversal, for every position p, the inorder traversal visits p after all the positions in the left subtree of p and before all the positions in the right subtree of p.
- Time complexity: \(O(n)\), where \(n\) is the number of positions in the tree.
Algorithm inorder(p):
if p has a left child lc then
inorder(lc) # recursively traverse the left subtree of p
perform the "visit" action for position p
if p has a right child rc then
inorder(rc) # recursively traverse the right subtree of p
Binary Heaps (Min-Heaps and Max-Heaps)
- Min-heap is a complete binary tree where each node is smaller than its children.
- The root is the minimum element in the tree.
- Max-heap is essentially equivalent but the elements are in descending order rather than ascending order.
Insert
- Insert element at the rightmost spot, then we fix the tree by swapping the new element with its parent, until we find an appropriate spot for the element.
- Takes \(O(\log n)\) time, where \(n\) is the number of nodes in the heap.
Extract Minimum Element
- First, we remove the minimum element and swap it with the last element in the heap.
- Then, we bubble down this element, swapping it with one of its children until the min-heap property is restored.
- Takes \(O(\log n)\) time, where \(n\) is the number of nodes in the heap.
Analysis of a Heap-Based Priority Queue
Python’s heapq Module
- Python’s standard distribution includes a heapq module that provides support for min-heap priority queues.
- Functions: heappush(L,e), heappop(L), heappushpop(L,e), heapreplace(L,e), heapify(L), nlargest(k,iterable), nsmallest(k,iterable)
Tries (Prefix Trees)
- Trie is a variant of an n-ary tree in which characters are stored at each node.
- Each path down the tree may represent a word.
- The * nodes (null nodes) are often used to indicate complete words.
- A node in a trie could have anywhere from 1 through \(\text{alphabet_size}+1\) children (or, 0 if a boolean flag is used instead of a * node).
- A trie can check if a string is a valid prefix in \(O(k)\) time, where \(k\) is the length of the string.
