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 depthh1 has two children
Examples:
o oo o
oo o o o
o o o o
o
NonExamples:
oo o
oo o o o
oooo o
o o
BST ideally balancedh log nsearch Olog n
But insertiondeletion 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: BFmhRmhLm
difference between heights of right and left subtrees
Heightbalanced tree: every node m, 1BFm1
Convention:
height of empty tree1
height of single node0
If BFm1, m is right heavy
BFm1, m is left heavy
BFm 0, m is balanced
Examples:
o oo o
oo o o o
o o o o o
o o
Is one of the heightbalanced trees above NOT ideally balanced?
NonExamples:
oo o
oo o oo
o ooo o
oo o
Worst case height is 1.44 log n2search Olog n
Maintaining heightbalance easier: Insertdelete Olog n
Augment data structure: store BF for each node
Examples:
0
0 00
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:
oBF0
after:
dec BF to 1 inc BF to 1
n n
before:
o BF1
o BF0
after:
X dec BF to 2 Xdec BF to 2oinc BF to 0
dec BF to 1inc BF to 1 o n
nn
Observations:
Inserting n always modifies BF of parent.
Either original BF0, and new BF1,
or, new BF0.
Case new BF0:
height of parent tree has not changed. Done.
Case new BF1:
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?
bdec BF to 2
adec BF to 1
n
Tree rotation: preserves ordering, alters balance
a BF0
nb
Single rotationtwo trees, same ordering: A b C d E
Constant time operation
bleft rotation d
Adb E
C Eright rotationA C
hLhAhL1maxhC,hA
hR1maxhC,hEhRhE
BF 1maxhC,hEhA BF hE1maxhC,hA
change in BF of root depends on hA, hC, hE
For AVL, 1BFm1, so hA, hC, hE not independent.
Double rotationtwo trees, same ordering: A b C d E f G
b RL rotationd
Afbf
d G LR rotationA CE G
C E
hLhA hL1maxhA,hC
hR1maxhG,1maxhC,hEhR1maxhE,hG
Insertx, T
1. Search tree and insert x into a new leaf n, maintaining order.
2. Set BFn to 0.
3. Let iparentn.
REPEAT:
a If n is in right subtree of i, increment BFi
otherwise n is in left subtree of i, decrement BFi
incexamples of when to
increment or decrement
0inc
note: algorithm will generally
0 0decstop before reaching all ancestors
n 0
b If BFi0, 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 BFi2 and BFrchildi1 then
single left rotation on i
adjust the balance factors of the rotated nodes
RETURN
BFrchildi1 hEhC1
BFi2 21hC1hA
hAhC
BEFORE INSERTIONBEFORE ROTATIONAFTER
hLhChLhC hL1hC
hRhC1hRhC2 hR1hC
BF 1 BF 2BF 0
BF0, and hi unchanged, so ancestors of i unaffected.
d If BFi2 and BFrchildi1 then
double right left rotation on i
adjust the balance factors of the rotated nodes
RETURN
Before:
BFi2 hAhChE
BFrchildi1 hGhE
After:
hL1hE, hR1hE, BF0
e If BFi2 and BFlchildi1 then
right rotation on i
adjust the balance factors
RETURN
mirror image of c
f If BFi2 and BFlchildi1
double left right rotation on i
adjust the balance factors
RETURN
mirror image of d
Argue that if BFi1, then we need to continue upward
g if iroot RETURN
iparentiwalk up the tree
END WHILE
Reviews
There are no reviews yet.