AVL Trees in Data Structures
CSE373: Data Structures & Algorithms
Lecture 7:
AVL
Trees
Linda Shapiro
Winter 2015
Announcements
•
HW2 due
TODAY
•
TA sessions this week
–
Thursday: Binary Search Trees and AVL Trees
•
Last lecture: Binary Search Trees
•
Today…
AVL Trees
Winter 2015
CSE373: Data Structures & Algorithms
2
Review: Binary
Search
Tree (BST)
•
Structure
property (binary tree)
–
Each node has
2
children
–
Result: keeps operations simple
•
Order
property
–
All keys in left subtree smaller
than node’s key
–
All keys in right subtree larger
than node’s key
–
Result: easy to find any given key
Winter 2015
3
CSE373: Data Structures & Algorithms
BST: Efficiency of Operations?
Winter 2015
CSE373: Data Structures & Algorithms
4
•
Problem: operations may be inefficient if BST is
unbalanced.
•
Find, insert, delete
–
O(n) in the worst case
•
BuildTree
–
O(n
2
) in the worst case
Observation
•
BST: the shallower the better!
S
o
l
u
t
i
o
n
:
R
e
q
u
i
r
e
a
n
d
m
a
i
n
t
a
i
n
a
B
a
l
a
n
c
e
C
o
n
d
i
t
i
o
n
t
h
a
t
1.
Ensures depth is always
O
(
log
n
)
– strong enough!
2.
Is efficient to maintain
– not too strong!
Winter 2015
5
CSE373: Data Structures & Algorithms
How can we make a BST efficient?
•
When we
build
the tree, make sure it’s balanced.
•
BUT
…Balancing a tree
only
at build time is insufficient because
sequences of operations can eventually transform our carefully
balanced tree into the
dreaded list
•
So, we also need to also
keep
the tree balanced as we perform
operations.
Potential Balance Conditions
1.
Left and right subtrees of the
root
have equal number of nodes
2.
Left and right subtrees of the
root
have equal
height
Too weak!
Height mismatch example:
Too weak!
Double chain example:
Winter 2015
6
CSE373: Data Structures & Algorithms
Potential Balance Conditions
3.
Left and right subtrees of
every node
have equal number of nodes
4.
Left and right subtrees of
every node
have equal
height
Too strong!
Only perfect trees (2
n
– 1 nodes)
Too strong!
Only perfect trees (2
n
– 1 nodes)
Winter 2015
7
CSE373: Data Structures & Algorithms
8
The AVL Balance Condition
L
e
f
t
a
n
d
r
i
g
h
t
s
u
b
t
r
e
e
s
o
f
e
v
e
r
y
n
o
d
e
h
a
v
e
h
e
i
g
h
t
s
d
i
f
f
e
r
i
n
g
b
y
a
t
m
o
s
t
1
D
e
f
i
n
i
t
i
o
n
:
b
a
l
a
n
c
e
(
n
o
d
e
)
=
h
e
i
g
h
t
(
n
o
d
e
.
l
e
f
t
)
–
h
e
i
g
h
t
(
n
o
d
e
.
r
i
g
h
t
)
A
V
L
p
r
o
p
e
r
t
y
:
f
o
r
e
v
e
r
y
n
o
d
e
x
,
–
1
b
a
l
a
n
c
e
(
x
)
1
•
Ensures small depth
–
This is because an AVL tree of height
h
must have a number of nodes
exponential
in
h
T
h
u
s
h
e
i
g
h
t
m
u
s
t
b
e
l
o
g
(
n
u
m
b
e
r
o
f
n
o
d
e
s
)
.
•
Efficient to maintain
–
Using single and double rotations
Winter 2015
CSE373: Data Structures & Algorithms
9
The
AVL Tree
Data Structure
An AVL tree is a
self-balancing
binary search tree.
Structural properties
1.
Binary tree
property (same as BST)
2.
Order
property
(same as for BST)
1.
Balance property:
balance of every node is between -1 and 1
R
e
s
u
l
t
:
W
o
r
s
t
-
c
a
s
e
d
e
p
t
h
i
s
O
(
l
o
g
n
)
•
Named after inventors Adelson-Velskii and Landis (AVL)
–
First invented in 1962
Winter 2015
CSE373: Data Structures & Algorithms
11
1
8
4
6
10
12
7
0
0
0
0
1
1
2
3
Is this an AVL tree?
Winter 2015
CSE373: Data Structures & Algorithms
10
Yes!
Because the left and right subtrees of
every node
have
heights
differing by
at most 1
3
11
7
1
8
4
6
2
5
0
0
0
0
1
1
2
3
4
Is this an AVL tree?
Winter 2015
CSE373: Data Structures & Algorithms
11
Nope!
The left and right subtrees of some nodes
(e.g. 1, 4, 6) have heights that differ by
more than 1
What do AVL trees give us?
•
If we have an AVL tree, then the number of nodes is an
exponential function of the height.
•
Thus the height is a log function of the number
of nodes!
•
And thus find
is
O
(
log
n
)
But as we insert and delete elements, we need to:
1.
Track balance
2.
Detect imbalance
3.
Restore balance
Winter 2015
12
CSE373: Data Structures & Algorithms
An AVL Tree
20
9
2
15
5
10
30
17
7
0
0
0
0
1
1
2
2
3
Track height at all times!
Winter 2015
CSE373: Data Structures & Algorithms
13
AVL tree operations
•
A
V
L
f
i
n
d
:
–
Same as BST
find
•
A
V
L
i
n
s
e
r
t
:
–
First BST
insert
,
then
check balance and potentially “fix” the
AVL tree
–
Four different imbalance cases
•
A
V
L
d
e
l
e
t
e
:
–
The “easy way” is lazy deletion
–
Otherwise, do the deletion and then check for several imbalance
cases (we will skip this)
Winter 2015
CSE373: Data Structures & Algorithms
14
Insert: detect potential imbalance
1.
Insert the new node as in a BST (a new leaf)
2.
For each node on the path from the root to the new leaf, the
insertion may (or may not) have changed the node’s height
3.
So after insertion in a subtree, detect height imbalance and
perform a
rotation
to restore balance at that node
All the action is in defining the correct
rotations
to restore balance
Fact that an implementation can ignore:
–
There must be a
deepest
element that is imbalanced after the
insert (all descendants still balanced)
–
After rebalancing this deepest node, every node is balanced
–
So
at most one node needs to be rebalanced
Winter 2015
15
CSE373: Data Structures & Algorithms
Case #1: Example
Winter 2015
16
CSE373: Data Structures & Algorithms
Insert(
6
)
Insert(
3
)
Insert(
1
)
Third insertion violates
balance property
•
happens to be at
the root
What is the only way to
fix this?
Fix: Apply “Single Rotation”
•
Single rotation:
The basic operation we’ll use to rebalance
–
Move child of unbalanced node into parent position
–
Parent becomes the “other” child (always okay in a BST!)
–
Other subtrees move in only way BST allows (next slide)
Winter 2015
17
CSE373: Data Structures & Algorithms
3
1
6
0
0
1
6
3
0
1
2
AVL Property violated at node 6
Child’s new-height = old-height-before-insert
1
The example generalized: Left of Left
•
Insertion into
left-left
grandchild causes an imbalance
–
1 of 4 possible imbalance causes (other 3 coming up!)
•
Creates an imbalance in the AVL tree (specifically
a
is imbalanced)
Winter 2015
18
CSE373: Data Structures & Algorithms
a
Z
Y
b
X
h
h
h
h
+
1
h
+
2
Winter 2015
CSE373: Data Structures & Algorithms
19
Winter 2015
CSE373: Data Structures & Algorithms
20
The general left-left case
•
So we
rotate
at
a
–
Move left child of unbalanced node into parent position
–
Parent becomes the right child
–
Other sub-trees move in the only way BST allows:
•
using BST facts: X < b < Y < a < Z
Winter 2015
21
CSE373: Data Structures & Algorithms
•
A
single rotation
restores balance at the node
–
To same height as before insertion,
so ancestors now balanced
a
Z
Y
b
X
h
+
1
h
h
h
+
2
h
+
3
b
Z
Y
a
h
+
1
h
h
h
+
1
h
+
2
Another example:
insert(16)
Winter 2015
22
CSE373: Data Structures & Algorithms
10
4
22
8
15
3
6
19
17
20
24
16
10
4
8
15
3
6
19
17
20
16
22
24
The general right-right case
•
Mirror image to left-left case, so you rotate the other way
–
Exact same concept, but needs different code
Winter 2015
23
CSE373: Data Structures & Algorithms
a
Z
Y
X
h
h
h
+
1
h
+
3
b
h
+
2
b
Z
Y
a
X
h
h
h
+
1
h
+
1
h
+
2
Two cases to go
Unfortunately, single rotations are not enough for insertions in the
left-right subtree or the right-left subtree
Simple example:
insert
(1),
insert
(6),
insert
(3)
–
First wrong idea:
single rotation like we did for left-left
Winter 2015
24
CSE373: Data Structures & Algorithms
3
6
1
0
1
2
6
1
3
1
0
0
Violates order
property!
Two cases to go
Unfortunately, single rotations are not enough for insertions in the
left-right subtree or the right-left subtree
Simple example:
insert
(1),
insert
(6),
insert
(3)
–
Second wrong idea:
single rotation on the child of the
unbalanced node
Winter 2015
25
CSE373: Data Structures & Algorithms
3
6
1
0
1
2
6
3
1
0
1
2
Still
unbalanced!
Sometimes two wrongs make a right
•
First idea violated the order property
•
Second idea didn’t fix balance
•
But if we do both single rotations, starting with the second, it
works! (And not just for this example.)
•
Double rotation:
1.
Rotate problematic child and grandchild
2.
Then rotate between self and new child
Winter 2015
26
CSE373: Data Structures & Algorithms
The general right-left case
Winter 2015
27
CSE373: Data Structures & Algorithms
Comments
•
Like in the left-left and right-right cases, the height of the subtree
after rebalancing is the same as before the insert
–
So no ancestor in the tree will need rebalancing
•
Does not have to be implemented as two rotations; can just do:
Winter 2015
28
CSE373: Data Structures & Algorithms
Easier to remember than you may think:
Move c to grandparent’s position
Put a, b, X, U, V, and Z in the only legal positions for a BST
The last case: left-right
•
Mirror image of right-left
–
Again, no new concepts, only new code to write
Winter 2015
29
CSE373: Data Structures & Algorithms
a
h
-
1
h
h
h
V
U
h
+
1
h
+
2
h
+
3
Z
X
b
c
c
X
h
-
1
h
+
1
h
h
+
1
V
U
h
+
2
Z
a
h
b
h
Insert, summarized
•
Insert as in a BST
•
Check back up path for imbalance, which will be 1 of 4 cases:
–
Node’s left-left grandchild is too tall
–
Node’s left-right grandchild is too tall
–
Node’s right-left grandchild is too tall
–
Node’s right-right grandchild is too tall
•
Only one case occurs because tree was balanced before insert
•
After the appropriate single or double rotation, the smallest-
unbalanced subtree has the same height as before the insertion
–
So all ancestors are now balanced
Winter 2015
30
CSE373: Data Structures & Algorithms
Example
20
9
2
15
5
10
30
17
7
0
0
0
0
1
1
2
2
3
Winter 2015
CSE373: Data Structures & Algorithms
31
Insert a 6
20
9
2
15
5
10
30
17
7
0
0
0
0
1
1
2
2
3
Winter 2015
CSE373: Data Structures & Algorithms
32
6
4
What’s the deepest node
that
is unbalanced?
What’s the case?
What do we do?
left-left
Insert a 6
20
7
2
15
5
10
30
17
6
0
0
0
0
1
0
1
2
2
Winter 2015
CSE373: Data Structures & Algorithms
33
9
3
Insert a 13
20
7
2
15
5
10
30
17
6
0
0
0
0
1
0
1
2
2
Winter 2015
CSE373: Data Structures & Algorithms
34
9
3
13
Insert a 14
20
7
2
15
5
10
30
17
6
0
0
0
0
2
0
1
3
2
Winter 2015
CSE373: Data Structures & Algorithms
35
9
4
13
14
0
1
What is the
deepest
unbalanced node?
Insert a 14
20
7
2
15
5
10
30
17
6
0
0
0
0
2
0
1
3
2
Winter 2015
CSE373: Data Structures & Algorithms
36
9
4
13
14
0
1
What is the
deepest
unbalanced node?
Which of the four
cases is this?
Still left-left!
Single rotation
Insert a 14
20
7
2
15
5
10
30
17
6
0
0
0
1
2
0
1
2
Winter 2015
CSE373: Data Structures & Algorithms
37
9
3
13
14
0
1
0
Now efficiency
•
Worst-case complexity of
find
:
O
(
log
n
)
–
Tree is balanced
•
Worst-case complexity of
insert
:
O
(
log
n
)
–
Tree starts balanced
–
A rotation is
O
(1) and there’s an
O
(
log
n
) path to root
–
Tree ends balanced
•
Worst-case complexity of
buildTree
:
O
(
n
log
n
)
Takes some more rotation action to handle
delete
…
Winter 2015
38
CSE373: Data Structures & Algorithms
Pros and Cons of AVL Trees
Winter 2015
CSE373: Data Structures & Algorithms
39
Arguments for AVL trees:
1.
All operations logarithmic worst-case because trees are
always
balanced
2.
Height balancing adds no more than a constant factor to the speed
of
insert
and
delete
Arguments against AVL trees:
1.
More di
fficult to program & debug [but done once in a library!]
2.
More space for height field
3.
Asymptotically faster but rebalancing takes a little time
4.
If
amortized
(later) logarithmic time is enough, use splay trees (also
in the text)
AVL trees are self-balancing binary search trees that help maintain efficiency in operations by ensuring the tree remains balanced. By enforcing a balance condition, AVL trees aim to keep the depth of the tree logarithmic, leading to O(log n) complexity for operations such as find, insert, and delete. This summary delves into the efficiency of binary search trees, the importance of balance conditions, and potential criteria for achieving balance in AVL trees.
Uploaded on Nov 25, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSE373: Data Structures & Algorithms Lecture 7: AVL Trees Linda Shapiro Winter 2015
Announcements HW2 due TODAY TA sessions this week Thursday: Binary Search Trees and AVL Trees Last lecture: Binary Search Trees Today AVL Trees Winter 2015 CSE373: Data Structures & Algorithms 2
Review: Binary Search Tree (BST) Structure property (binary tree) Each node has 2 children Result: keeps operations simple 8 Order property All keys in left subtree smaller than node s key All keys in right subtree larger than node s key Result: easy to find any given key 5 11 2 6 10 12 4 7 9 14 13 Winter 2015 CSE373: Data Structures & Algorithms 3
BST: Efficiency of Operations? Problem: operations may be inefficient if BST is unbalanced. Find, insert, delete O(n) in the worst case BuildTree O(n2) in the worst case Winter 2015 CSE373: Data Structures & Algorithms 4
How can we make a BST efficient? Observation BST: the shallower the better! Solution: Require and maintain a Balance Condition that 1. Ensures depth is alwaysO(logn) strong enough! 2. Is efficient to maintain not too strong! When we build the tree, make sure it s balanced. BUT Balancing a tree only at build time is insufficient because sequences of operations can eventually transform our carefully balanced tree into the dreaded list So, we also need to also keep the tree balanced as we perform operations. Winter 2015 CSE373: Data Structures & Algorithms 5
Potential Balance Conditions 1. Left and right subtrees of the root have equal number of nodes Too weak! Height mismatch example: 2. Left and right subtrees of the root have equal height Too weak! Double chain example: Winter 2015 CSE373: Data Structures & Algorithms 6
Potential Balance Conditions 3. Left and right subtrees of every node have equal number of nodes Too strong! Only perfect trees (2n 1 nodes) 4. Left and right subtrees of every node have equal height Too strong! Only perfect trees (2n 1 nodes) Winter 2015 CSE373: Data Structures & Algorithms 7
The AVL Balance Condition Left and right subtrees of every node have heights differing by at most 1 Definition: balance(node) = height(node.left) height(node.right) AVL property: for every node x, 1 balance(x) 1 Ensures small depth This is because an AVL tree of height h must have a number of nodes exponential in h Thus height must be log(number of nodes). Efficient to maintain Using single and double rotations 8 Winter 2015 CSE373: Data Structures & Algorithms
The AVL Tree Data Structure An AVL tree is a self-balancing binary search tree. Structural properties 1. Binary tree property (same as BST) 2. Order property (same as for BST) 1. Balance property: balance of every node is between -1 and 1 Result: Worst-case depth is O(log n) Named after inventors Adelson-Velskii and Landis (AVL) First invented in 1962 Winter 2015 CSE373: Data Structures & Algorithms 9
Is this an AVL tree? 3 6 1 2 4 8 0 1 11 0 1 7 0 0 12 10 Yes! Because the left and right subtrees of every node have heights differing by at most 1 Winter 2015 CSE373: Data Structures & Algorithms 10
Is this an AVL tree? 4 6 3 1 4 8 2 1 5 7 11 0 0 0 3 1 2 0 Nope! The left and right subtrees of some nodes (e.g. 1, 4, 6) have heights that differ by more than 1 Winter 2015 CSE373: Data Structures & Algorithms 11
What do AVL trees give us? If we have an AVL tree, then the number of nodes is an exponential function of the height. Thus the height is a log function of the number of nodes! And thus find is O(logn) But as we insert and delete elements, we need to: 1. Track balance 2. Detect imbalance 3. Restore balance Winter 2015 CSE373: Data Structures & Algorithms 12
An AVL Tree Node object key 10 3 value 10 height 3 2 2 children 5 20 1 1 0 0 15 30 2 9 0 0 7 17 Track height at all times! Winter 2015 CSE373: Data Structures & Algorithms 13
AVL tree operations AVL find: Same as BST find AVL insert: First BST insert, thencheck balance and potentially fix the AVL tree Four different imbalance cases AVL delete: The easy way is lazy deletion Otherwise, do the deletion and then check for several imbalance cases (we will skip this) Winter 2015 CSE373: Data Structures & Algorithms 14
Insert: detect potential imbalance 1. 2. Insert the new node as in a BST (a new leaf) For each node on the path from the root to the new leaf, the insertion may (or may not) have changed the node s height So after insertion in a subtree, detect height imbalance and perform a rotation to restore balance at that node 3. All the action is in defining the correct rotations to restore balance Fact that an implementation can ignore: There must be a deepest element that is imbalanced after the insert (all descendants still balanced) After rebalancing this deepest node, every node is balanced So at most one node needs to be rebalanced Winter 2015 CSE373: Data Structures & Algorithms 15
Case #1: Example Insert(6) Insert(3) Insert(1) 0 1 2 6 6 6 0 1 3 3 Third insertion violates balance property happens to be at the root 0 1 1 What is the only way to fix this? 3 0 0 6 1 Winter 2015 CSE373: Data Structures & Algorithms 16
Fix: Apply Single Rotation Single rotation:The basic operation we ll use to rebalance Move child of unbalanced node into parent position Parent becomes the other child (always okay in a BST!) Other subtrees move in only way BST allows (next slide) AVL Property violated at node 6 1 2 3 6 1 0 0 3 1 6 0 1 Child s new-height = old-height-before-insert Winter 2015 CSE373: Data Structures & Algorithms 17
The example generalized: Left of Left Insertion into left-left grandchild causes an imbalance 1 of 4 possible imbalance causes (other 3 coming up!) Creates an imbalance in the AVL tree (specifically a is imbalanced) h+2 a h+3 a h+1 h+2 h b h b h h h+1 h Z Z X Y X Y Winter 2015 CSE373: Data Structures & Algorithms 18
Winter 2015 CSE373: Data Structures & Algorithms 19
Winter 2015 CSE373: Data Structures & Algorithms 20
The general left-left case So we rotate at a Move left child of unbalanced node into parent position Parent becomes the right child Other sub-trees move in the only way BST allows: using BST facts: X < b < Y < a < Z h+3 h+2 a b h+2 h+1 h a b h h+1 h+1 h h Z X X Y Y Z A single rotation restores balance at the node To same height as before insertion, so ancestors now balanced Winter 2015 CSE373: Data Structures & Algorithms 21
Another example: insert(16) 15 8 22 24 19 4 10 6 3 17 20 16 15 8 19 22 4 10 17 16 20 24 6 3 Winter 2015 CSE373: Data Structures & Algorithms 22
The general right-right case Mirror image to left-left case, so you rotate the other way Exact same concept, but needs different code h+3 a h+2 b h+2 h h+1 b h+1 a h X h h h+1 Z Y Z X Y Winter 2015 CSE373: Data Structures & Algorithms 23
Two cases to go Unfortunately, single rotations are not enough for insertions in the left-right subtree or the right-left subtree Simple example: insert(1), insert(6), insert(3) First wrong idea: single rotation like we did for left-left 2 1 1 Violates order property! 6 1 6 0 0 3 1 0 3 Winter 2015 CSE373: Data Structures & Algorithms 24
Two cases to go Unfortunately, single rotations are not enough for insertions in the left-right subtree or the right-left subtree Simple example: insert(1), insert(6), insert(3) Second wrong idea: single rotation on the child of the unbalanced node 2 2 1 1 Still unbalanced! 1 1 6 3 0 0 3 6 Winter 2015 CSE373: Data Structures & Algorithms 25
Sometimes two wrongs make a right First idea violated the order property Second idea didn t fix balance But if we do both single rotations, starting with the second, it works! (And not just for this example.) Double rotation: 1. Rotate problematic child and grandchild 2. Then rotate between self and new child 2 2 1 1 1 3 1 6 1 3 0 0 0 0 3 1 6 6 Winter 2015 CSE373: Data Structures & Algorithms 26
The general right-left case h+3 a h+2 h b h+1 h c X h h-1 Z V U h+2 c h+3 h+1 a h+1 b h+2 a h h c h h h+1 h h-1 b U X h-1 V X U Z h V Z Winter 2015 CSE373: Data Structures & Algorithms 27
Comments Like in the left-left and right-right cases, the height of the subtree after rebalancing is the same as before the insert So no ancestor in the tree will need rebalancing Does not have to be implemented as two rotations; can just do: h+3 h+2 a c h+2 h b h+1 h+1 h+ 1 b h a c h X h h h-1 h h-1 Z U V V X U Z Easier to remember than you may think: Move c to grandparent s position Put a, b, X, U, V, and Z in the only legal positions for a BST Winter 2015 CSE373: Data Structures & Algorithms 28
The last case: left-right Mirror image of right-left Again, no new concepts, only new code to write h+3 h+2 a c h+2 h b h+1 h+ 1 h+1 a b c h Z h h h h-1 h h-1 U V X X U Z V Winter 2015 CSE373: Data Structures & Algorithms 29
Insert, summarized Insert as in a BST Check back up path for imbalance, which will be 1 of 4 cases: Node s left-left grandchild is too tall Node s left-right grandchild is too tall Node s right-left grandchild is too tall Node s right-right grandchild is too tall Only one case occurs because tree was balanced before insert After the appropriate single or double rotation, the smallest- unbalanced subtree has the same height as before the insertion So all ancestors are now balanced Winter 2015 CSE373: Data Structures & Algorithms 30
Example 3 10 2 2 5 20 1 1 0 0 15 30 2 9 0 0 7 17 Winter 2015 CSE373: Data Structures & Algorithms 31
Insert a 6 What s the deepest node that is unbalanced? 4 What s the case? 10 3 What do we do? 2 5 20 2 1 0 0 15 30 2 9 0 1 left-left 7 17 0 6 Winter 2015 CSE373: Data Structures & Algorithms 32
Insert a 6 3 10 2 2 5 20 1 1 0 0 15 30 2 7 0 0 0 6 17 9 Winter 2015 CSE373: Data Structures & Algorithms 33
Insert a 13 3 10 2 2 5 20 1 1 0 0 15 30 2 7 0 0 0 17 6 13 9 Winter 2015 CSE373: Data Structures & Algorithms 34
Insert a 14 4 10 2 What is the deepest unbalanced node? 3 5 20 1 2 0 0 15 30 2 7 0 1 0 0 17 6 13 9 140 Winter 2015 CSE373: Data Structures & Algorithms 35
Insert a 14 4 10 2 What is the deepest unbalanced node? 3 5 20 1 2 0 0 15 30 2 7 Which of the four cases is this? 0 1 0 0 17 6 13 9 Still left-left! Single rotation 140 Winter 2015 CSE373: Data Structures & Algorithms 36
Insert a 14 3 10 2 2 5 15 1 0 1 2 7 1 20 13 0 0 0 0 30 17 0 14 6 9 Winter 2015 CSE373: Data Structures & Algorithms 37
Now efficiency Worst-case complexity of find: O(logn) Tree is balanced Worst-case complexity of insert: O(logn) Tree starts balanced A rotation is O(1) and there s an O(logn) path to root Tree ends balanced Worst-case complexity of buildTree: O(n logn) Takes some more rotation action to handle delete Winter 2015 CSE373: Data Structures & Algorithms 38
Pros and Cons of AVL Trees Arguments for AVL trees: 1. All operations logarithmic worst-case because trees are always balanced Height balancing adds no more than a constant factor to the speed of insert and delete 2. Arguments against AVL trees: 1. 2. 3. 4. More difficult to program & debug [but done once in a library!] More space for height field Asymptotically faster but rebalancing takes a little time If amortized (later) logarithmic time is enough, use splay trees (also in the text) Winter 2015 CSE373: Data Structures & Algorithms 39
