Balanced Binary Search Tree (AVL)
AVL TREES
Perfectly Balance, as all things should be.
Previously, when look at normal BST, if it is imbalance, its o(n). But if it is balance,
ie. h= logn always => O(logn)
1. Keep a height variable at each node
o.height = max(o.left.height, o.right.height) + 1
2.Maintain the variant: All nodes in BST must be height balanced
Both sides must be height balanced.
|o.left.height() – o.right.height()| ≤ 1
3. Rebalance via rotations
Balance Factor:
Define b(o) = o.left.height() – o.right.height()
b(o) of an empty tree (null) is -1 //its oni one side
if b(o) > 1 or b(o) < -1 for any o, the tree is no longer height balanced.
Ensure that both left and right side of the node has at most a difference of 1
b(o) of an empty tree (null) is -1 //its oni one side
if b(o) > 1 or b(o) < -1 for any o, the tree is no longer height balanced.
Ensure that both left and right side of the node has at most a difference of 1
Balancing O(n) time because we need to go through every element to count.
Claim:
A height balance tree with n nodes has at most height h< 2logn so
Time to do any operation on the tree -> h= O(logn)
Rotations
4 types:
Left rotation
Applies: Y is X 's right child
Objective: Want y to be X's parents but need to preserve BST properties
We want to shift Y up one level and X down one level
What is the worst case time complexity of left rotation
O(1)
->We are just moving references around
function rotateLeft(x)
y = x.right // reassign parent
y.parent = x.parent // make y into x’s parent
x.parent = y // move B x.right = y.left
if (x.right is not null)
x.right.parent = x // make x into y’s child
y.left = x // update heights and parent referencereturn y
//We need to write for both sides x and y
Is the BST property preserved for the parent?
Yes
Right rotation
Objective: Want y to be x’s parent
But must preserve BST properties.Applies: y is x’s left child.
function rotateRight(x)
y = x.left // reassign parent
y.parent = x.parent// make y into x’s parent
x.parent = y // move B
x.left = y.right
if (x.left is not null)
x.left.parent = x // make x into y’s child
y.right = x // update heights and parent reference
return y
We turn Right when node is imbalance on the left (Left side is longer)
Turn left if node is imbalance on the right
Left-Right rotation
AKA Double right
left rotate my left child first before right rotate myself
If the unbalance side follow this order: node , left, right
Right-Left rotation
AKA double left
right rotate my right child first before left rotate myself
If the unbalance side follow this order: node , right , left
Inbalance can be caused by insertion and deletion
if tree is right heavy
if tree’s right subtree is left heavy
right rotate, left rotate
else
left rotate
else if tree is left heavy
if tree’s left subtree is right heavy
left rotate, right rotate
else
right rotate
We need to check
1. Parent is balance
2. If parent is not balance, check the child on the side which is imbalance
if the child has balance factor 's sign is opposite of the parents, its a double rotate
else its just a single rotate
When to balance?
Can rotation increase height of tree? No, it either decrease by one or leave it the same
Rotation required after insert: 1, Just swap the imbalance side of the tree, up to the root
Rotation maybe required after deletion: O(logN) We need to go all the way up to the root
Left rotation
Applies: Y is X 's right child
Objective: Want y to be X's parents but need to preserve BST properties
We want to shift Y up one level and X down one level
What is the worst case time complexity of left rotation
O(1)
->We are just moving references around
function rotateLeft(x)
y = x.right // reassign parent
y.parent = x.parent // make y into x’s parent
x.parent = y // move B x.right = y.left
if (x.right is not null)
x.right.parent = x // make x into y’s child
y.left = x // update heights and parent referencereturn y
//We need to write for both sides x and y
Is the BST property preserved for the parent?
Yes
Right rotation
Objective: Want y to be x’s parent
But must preserve BST properties.Applies: y is x’s left child.
function rotateRight(x)
y = x.left // reassign parent
y.parent = x.parent// make y into x’s parent
x.parent = y // move B
x.left = y.right
if (x.left is not null)
x.left.parent = x // make x into y’s child
y.right = x // update heights and parent reference
return y
We turn Right when node is imbalance on the left (Left side is longer)
Turn left if node is imbalance on the right
Left-Right rotation
AKA Double right
left rotate my left child first before right rotate myself
If the unbalance side follow this order: node , left, right
Right-Left rotation
AKA double left
right rotate my right child first before left rotate myself
If the unbalance side follow this order: node , right , left
Inbalance can be caused by insertion and deletion
if tree is right heavy
if tree’s right subtree is left heavy
right rotate, left rotate
else
left rotate
else if tree is left heavy
if tree’s left subtree is right heavy
left rotate, right rotate
else
right rotate
We need to check
1. Parent is balance
2. If parent is not balance, check the child on the side which is imbalance
if the child has balance factor 's sign is opposite of the parents, its a double rotate
else its just a single rotate
When to balance?
Can rotation increase height of tree? No, it either decrease by one or leave it the same
Rotation required after insert: 1, Just swap the imbalance side of the tree, up to the root
Rotation maybe required after deletion: O(logN) We need to go all the way up to the root