Week03 Tree Notes
Heap Animation
Heap from 2:50, Heap Insertion from 5:00, Heap Deletion from 8:21
What is Heapify ?
The name of heapify is misleading, actually it is better called percolate down.
When we are inserting an element to the end of a heap array, we are doing bubbling up or percolating up. When we remove one element from the top of a heap and replace the top with the last element of the heap array, we need to move min or max element down - percolate down, or another name - heapify.
The swapping of elements during percolating up or down bears some resemblance with Bubble Sort. The different is that for Bubble sort, each element has only ONE next or child element, while for a heap, each node has two child nodes.
Further Reading
Auto-balancing Binary Search Trees
Auto-balaning binary search trees can reduce the depth difference of the left child tree and the right child tree of a node. The most important auto-balancing binary search trees include the AVL tree and the Red-Black tree.
The special operations invovlved for auto-balancing binary search trees are rotation operations.
AVL tree is the plain auto-balancing tree which limit the depth difference under 1. There are four cases of rotations for an AVL tree as shown as follows:
The Red-Black tree, on the other hand, does not aim to control the depth different so strictly but reduceds the number of rotation operations.
Red-Black trees have wide applications in areas such as database, data structure, etc.
AVL Tree
AVL Tree
AVL Tree implementation in C
Red Black Tree
Requirements
A node is either red or black. - Nodes require one storage bit to keep track of color.
The root and leaves (NIL) are black.
If a node is red, then its children are black.
All paths from a node to its NIL descendants contain the same number of black nodes.
Properties
Use and store the height of the black nodes in each node.
The longest path (root to farthest NIL) is no more than twice the length of the shortest path (root to nearest NIL).
- Shortest path: all black nodes
-Longest path: alternating red and black
A red black tree is a data structure which allows for Insertion, Deletion and Searching of the tree bounded by O(log(n)) time at the expense of an extra color bit for every node. It is easier to code than an AVL tree (which has near perfect balancing but slightly more overhead).
Red Black Trees are used for the implementation of the C++ Map (and also Set) STL containers. (and even for the Java Library)
The Completely Fair Scheduler of the Linux 2.6+ kernel uses a Red Black Tree implementation.
A red black tree, owning to its relative ease to code and good time complexity for the supported operations, is widely used.
AVL trees are more rigidly balanced than red black trees, leading to slower insertion and removal but faster retrieval. Red Black trees are good if there are similar number of insertions, deletions and lookups. For much larger number of lookups than insertions, you might want to look at the AVL tree.
B tree and B+ tree
B+ trees are widly used in databases and file systems.
Last updated