Please enable JavaScript.
Coggle requires JavaScript to display documents.
Balanced Search Trees, balance before insertion - Coggle Diagram
Balanced Search Trees
Instance Simplification
red-black tree
tolerates very large subtrees
AVL Trees
subtrees left and right
height between -1 and 1
efficiency
tree height
worst case: Θ(log n)
frequent rotations
constant balancing
rotation types
double right/left
left/right mirror
double left/right
new key insertion at right subtree left child
single left
right mirror
single right
key insertion left subtree
rotations
restores the balanced requirement
preserve the tree
like a safe point
Representation Change
b-trees
perfect balanced
differ in node elements
2/3 or 2/3/4 trees
balance before insertion
-1
1