Please enable JavaScript.
Coggle requires JavaScript to display documents.
Balanced Search Tree - Coggle Diagram
Balanced Search Tree
On the worst case, a tree can become severely unbalanced, with its height = n - 1
On the average case, Binary Trees search, insertion and deletion are all in Θ(log n), however...
With that, there are two approaches to avoid the worst-case imbalance
Self-balancing Trees
-
If an insertion or deletion violates the balance requirement, the tree is restructured with rotations
AVL Tree
The balance requirement is that the difference between the heights of the left and right subtree can't exceed 1
Each node has an balance factor (0, 1 or -1)
Rotation
If a node balance factor becomes 2 or -2, the subtree of that node do a local transformation called rotation (if there are many unbalanced nodes, the rotation is made closest to the newly inserted leaf)
-
-
3. LR-rotation: a combination of two rotations: we perform the L-rotation of the left subtree of root r followed by the R-rotation of the new tree rooted at r
It's used when a new key is inserted into the right subtree of the left child of a tree whose root had the balance of +1 before the insertion.
-
AVL Efficiency
Even though rotations aren't trivial transformations, they can be done in constant time
rotations also guarantee that the resulting tree is balanced, avoid the worst case of a height = n - 1
-