Please enable JavaScript.
Coggle requires JavaScript to display documents.
Balanced search Trees - Coggle Diagram
Balanced search Trees
Types
AVL
Difference between
the heights of the left and right subtrees of every node never exceed 1.
Red-black
Tolerates the height of one subtree being twice as large as the
other subtree of the same node.
Self-balancing
An unbalanced
binary search tree is transformed into a balanced one.
Splay
Time efficiency
Worse case
θ (n)
Insertion
Average case
θ (log n)
Deletion
Searching
Rotations
AVL
single left rotation/ L-rotation
Double left-right rotation/ LR-rotation
combination of two rotations: l-rotation followed by r-rotation
Single right rotation/ R-rotation
Double right-left rotation/ RL-rotation
combination of two rotations: r-rotation followed by l-rotation