Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM8 - Coggle Diagram
MM8
Approaches for balacing Binary Search Trees
Balacing BSTs prevent the worst case scenario
instance-simplification
self-balancing trees
AVL tree
difference between the heights of the left and right subtrees of every node never exceed 1
red-black tree
the height of one subtree can be up to twice as large as the other subtree of the same node
Rotation
special transformation that restore the balace required after the tree heights become unbalanced
representation-change
2-3 tree
2-3-4 tree
B-tree
Allow more than one element in a node of a search tree
AVL tree
Balance Factor
The balance factor of a node is the difference between the heights of its left and right subtree
in AVL tree it must be either 0, +1 or -1
Empty trees have a balance factor of -1
rotation
done if the balance factor of a node become +2 or -2
types
single right rotation (R-rotation)
single left rotation (L-rotation)
double left-right rotation (LR-rotation)
left rotation followed by a right rotation on the new root
double right-left rotation (RL-rotation)
right rotation followed by a left rotation on the new root
Efficiency
Θ(log n) in the worst case
1.01log2n in the avarage case