Please enable JavaScript.
Coggle requires JavaScript to display documents.
Balanced Search Tree - Coggle Diagram
Balanced Search Tree
Representation-Change Variety
2-3 Trees
2-3-4 Trees
B-Trees
AVL Tree
Balance Factor = 1, 0, -1
Rotation
Single
R-Rotation
L-Rotation
Double
LR-Rotation
RL-Rotation
Cworst(n) ∈ Θ(log n)
Instance-Simplification Variety
Self-Balancing
AVL Tree
|Height(Left Subtree) - Height(Right Subtree)| ≤ 1
Red Black Tree
Height(Left Subtree) x 2 ≥ Height(Right Subtree) or Height(Left Subtree) ≤ 2 x Height(Right Subtree)
Unbalanced Tree
Rotation
Balanced Tree
Splay Trees