Red-black trees
Follow up to 61B Application 202005111503
Final Presentation: https://docs.google.com/presentation/d/1N-4scA49OzqpBgj9vMNlcxGICdljYSD0U8ERGjdeQ6w/edit#slide=id.p
Binary Search Tree
- A binary search tree is a tree with one additional constraint — it keeps the elements in the tree in a particular order. Formally each node in the BST has two children (if any are missing we consider it a nil node), a left child and a right child. Nodes are rooted in place based on their values, with the smallest on the left and largest on the right.
2-3-4 Trees
- B-tree invariants:
- All leaves must be the same distance from the source
- A non-leaf node with k-items must have exactly k+1 children.
Red-black trees are structurally identical to a 2-3 tree!
Why red-black tree over 2-3 tree?
- Inconvenient to manage multiple different types of nodes, need to keep track of how to insert in each of them, etc.
Insertion into a red-black tree
- When inserting: Use a red link.
- If there is a right leaning “3-node”, we have a Left Leaning Violation.
- Rotate left the appropriate node to fix.
- If there are two consecutive left links, we have an Incorrect 4 Node Violation.
- Rotate right the appropriate node to fix.
- If there are any nodes with two red children, we have a Temporary 4 Node.
- Color flip the node to emulate the split operation.
Important red-black tree properties
General Notes
- Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.
- The leaf nodes of red–black trees do not contain data.
- Can either be null or a sentinel
- In-order traversal: The search-time results from the traversal from root to leaf, and therefore a balanced tree of n nodes, having the least possible tree height, results in O(log n) search time.
uid: 202005202245 tags: #algorithms