Red Black Tree Rules - type of BST
- Root is always black
- Each node is colored black or red
- A null node is colored black –> every new node must be inserted red
- every red node has two black noeds
- every path from ANY node to ANY of its descendant null node must have the same number of black nodes
VAL vs red-black trees
red-black trees are less-perfectly balanced. However, they generally need fewer rotations during insertion/deletion, which makes red-black tree superior for growing or shrinking a tree, but less efficient for searching.
Both O(log n) time complexity
AVL might have greater height and use more memory than Red Black Trees
VAL self-balancing BST
Uses balance factor (absolut delta between height of left and right subtree).
Balanced if this delta is smaller equal to one for every node.
How to rebalance AVL
Start from the lowest unbalanced tree.
Label the three nodes, starting from the unbalanced one.
Rearrange.
Check balance factor of ancestor
Condition that must be fulfilled such that tree operations are log n
Tree must be balanced
