ANNOUNCEMENTS:
our expectations on the additional notes: basic questions on definitions
TODAYS TOPIC:
Operations: search, insert and delete.
Binary search trees BST average case Olog n
But worst case On.
BST ideally heightbalanced if
1 every leaf has depth h or h1
2 every node of depth h1 has two children
Examples:
o o o o
o o o o o
o o o o
o
NonExamples:
o o o
o o o o o
o o o o o
o o
BST ideally balanced h log n search Olog n
But insertion deletion On: maintaining ideal balance is hard
Introducing AVL trees AdelsonVelski and Landis
Compromise between arbitrary and ideally balanced BST
Balance factor of a node m: BFm hRm hLm
difference between heights of right and left subtrees
Heightbalanced tree: every node m, 1 BFm 1
Convention:
height of empty tree 1
height of single node 0
If BFm 1, m is right heavy
BFm 1, m is left heavy
BFm 0, m is balanced
Examples:
o o o o
o o o o o
o o o o o
o o
Is one of the heightbalanced trees above NOT ideally balanced?
NonExamples:
o o o
o o o o o
o o o o o
o o o
Worst case height is 1.44 log n 2 search Olog n
Maintaining heightbalance easier: Insert delete Olog n
Augment data structure: store BF for each node
Examples:
0
0 0 0
0 0 0 0 0
0 0
Search operation: same as usual
Insert operation: insert as usual, then rebalance
update balance factors
rebalance
Consider simple cases, inserting n into existing AVL:
before:
o BF 0
after:
dec BF to 1 inc BF to 1
n n
before:
o BF 1
o BF 0
after:
X dec BF to 2 X dec BF to 2 o inc BF to 0
dec BF to 1 inc BF to 1 o n
n n
Observations:
Inserting n always modifies BF of parent.
Either original BF 0, and new BF 1,
or, new BF 0.
Case new BF 0:
height of parent tree has not changed. Done.
Case new BF 1:
height of parent increased by one. Recurse up the tree.
Parents parent new BF may be 2, 1, 0, 1, 2.
How far up? how many ancestors are affected?
What about new BF outside valid range?
b dec BF to 2
a dec BF to 1
n
Tree rotation: preserves ordering, alters balance
a BF 0
n b
Single rotation two trees, same ordering: A b C d E
Constant time operation
b left rotation d
A d b E
C E right rotation A C
hL hA hL 1 maxhC,hA
hR 1 maxhC,hE hR hE
BF 1 maxhC,hE hA BF hE 1 maxhC,hA
change in BF of root depends on hA, hC, hE
For AVL, 1 BFm 1, so hA, hC, hE not independent.
Double rotation two trees, same ordering: A b C d E f G
b RL rotation d
A f b f
d G LR rotation A C E G
C E
hL hA hL 1 maxhA,hC
hR 1 maxhG,1maxhC,hE hR 1 maxhE,hG
Insertx, T
1. Search tree and insert x into a new leaf n, maintaining order.
2. Set BFn to 0.
3. Let i parentn.
REPEAT:
a If n is in right subtree of i, increment BFi
otherwise n is in left subtree of i, decrement BFi
inc examples of when to
increment or decrement
0 inc
note: algorithm will generally
0 0 dec stop before reaching all ancestors
n 0
b If BFi 0, RETURN
i became balanced by insertion, height of tree i did not change
Observation: consider the path traced from n up to the root: all path nodes below i and above n must have BF not 0. Proof: line b above.
c If BFi 2 and BFrchildi 1 then
single left rotation on i
adjust the balance factors of the rotated nodes
RETURN
BFrchildi 1 hE hC 1
BFi 2 2 1 hC 1 hA
hA hC
BEFORE INSERTION BEFORE ROTATION AFTER
hL hC hL hC hL 1 hC
hR hC 1 hR hC 2 hR 1 hC
BF 1 BF 2 BF 0
BF 0, and hi unchanged, so ancestors of i unaffected.
d If BFi 2 and BFrchildi 1 then
double right left rotation on i
adjust the balance factors of the rotated nodes
RETURN
Before:
BFi 2 hA hC hE
BFrchildi 1 hG hE
After:
hL 1 hE, hR 1 hE, BF 0
e If BFi 2 and BFlchildi 1 then
right rotation on i
adjust the balance factors
RETURN
mirror image of c
f If BFi 2 and BFlchildi 1
double left right rotation on i
adjust the balance factors
RETURN
mirror image of d
Argue that if BFi 1, then we need to continue upward
g if i root RETURN
i parenti walk up the tree
END WHILE