程序代写代做代考 data structure algorithm AVL Recursive Version
Recursive Version
Algorithm and Data Structure
Analysis
(ADSA)
AVL-Trees
Algorithm and Data Structure Analysis 1
Overview
AVL-Trees:
• Find, insert, remove
Algorithm and Data Structure Analysis 2
Runtimes for Binary Search Tree
Find, insert, remove:
Worst case:
Best case:
Average case:
Algorithm and Data Structure Analysis
Aim: Time O(log n) in the worst case
3
AVL-Tree
Observation:
• Binary search trees can get imbalanced when
applying insert and/or remove operations.
Idea:
• Whenever a subtree rooted at a node v gets
imbalanced, apply operations that balance it
out in time O(log n).
Algorithm and Data Structure Analysis 4
AVL Tree
Let h(T) be the height of a tree T.
Let v be a node in T and Tl and Tr be the left and
right subtree of v.
We denote by b(v) = h(Tl) – h(Tr) the balance
degree of v.
Definition: A binary search tree T is called an
AVL-tree if for each , holds.
Algorithm and Data Structure Analysis 5
Height of an AVL-tree
Theorem(without proof) Let T be an AVL-tree
consisting of n nodes. Then
We have to consider the operations find, insert, and
delete for AVL-trees.
• Find is as for Binary Search Trees.
• For insert and remove we might have to
rebalance the tree.
Algorithm and Data Structure Analysis 6
Example Insert
Algorithm and Data Structure Analysis
4
5
Balance values
0
-1
Insert 7
7
Example Insert
Algorithm and Data Structure Analysis
4
5
7
Consider path from new leaf
to the root and check balance values
8
Example Insert
Algorithm and Data Structure Analysis
4
5
7
New balance values
-1
-2
0
9
Example Insert
Algorithm and Data Structure Analysis
4
5
7
New balance values
-1
-2
0
AVL-property at node 4 violated
10
Example Insert
Algorithm and Data Structure Analysis
5
7
Rotation establishes
AVL-property again0
0
0
4
11
Insertion
Inserting a new element z can violate the AVL-
property.
Consider path from the newly inserted leaf z to
the root and repair AVL-property.
Algorithm and Data Structure Analysis 12
Rebalancing
Let z be the newly inserted leaf.
Consider the path from z to the root (reverse the
insertion path).
Update the balance values.
Repair AVL-property (if necessary).
Algorithm and Data Structure Analysis 13
Insert
• we insert new node z as for Binary Search
Trees.
• bal(z)=0 holds after insertion.
• bal(v) might change by 1 for a node v on the
path from z to the root.
• If rebalance
Algorithm and Data Structure Analysis 14
Rebalancing
Start examining for v, where v is the parent of z, and continue
with the parent of v (if necessary).
Assume that the right child x of node v is on the path from z to
the root.
Before insertion -> After Insertion:
• bal(v) = 1 -> bal(v)=0 (height of tree rooted at v has not changed,
stop rebalancing)
• bal(v)=0 -> bal(v) = -1 (height of tree rooted at v has increased by
1, stop rebalancing only if v is root, otherwise examine parent of v)
• bal(v)=-1 -> bal(v) = -2 (AVL-property violated, carry out
rotation)
Algorithm and Data Structure Analysis 15
Left Rotation
Assume node v and right child x on the path.
• w is right child of x on the path
-> Left rotation
New balance values: bal(x)=0 and bal(v)=0
Algorithm and Data Structure Analysis
Analogous: Right Rotation
16
Left Rotation
Algorithm and Data Structure Analysis
v
x
h
h-1
h-2
x
h-1h-1
v
h-1
A
B
C
C
BA
Analog: Right Rotation
w
w
17
Right-Left Rotation
w is left child of x on the path
-> Right-Left Rotation.
Algorithm and Data Structure Analysis
v
x
h
h-1
h-2
w
h-1
h-2
v
h-1
A
B
D
CBA
w
C
x
D
h-1
h-1
Analog: Left-Right Rotation
18
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis 19
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis
4
0
20
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis
4
5
0
-1
21
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis
4
5
7
Unbalanced
Left Rotation
0
-1
-2
22
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis
5
74
Balance OK
0
00
23
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis
5
74
2
0
0
1
1
24
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis
5
74
2
1
Unbalanced
Right Rotation0
0
1
2
2
25
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis
5
72
1 4
Balance OK
0 0
0
0
1
26
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis
5
72
1 4
Unbalanced
Left-right Rotation
3
0
0
0 1
2
-1
27
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis
4
52
1 3
Balance OK
7
00
0
0 -1
0
28
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis
4
52
1 3
Unbalanced
Right-left Rotation
7
6
-1
-2
1
0
0 0
0
29
Example Insert
Create AVL-Tree for sequence 4, 5, 7, 2, 1, 3, 6
Algorithm and Data Structure Analysis
4
62
1 3
Balance OK
75
0 0 0 0
0 0
0
30
Time complexity of for insertion
Inserting a node involves:
• Finding the location and adding the node to
the tree
• Moving up the AVL tree see whether AVL
property is violated and perform rotation as
needed
O(log n) + O (log n) + O(1)
Algorithm and Data Structure Analysis 31
Remove – Left Rotation
W.l.o.g. assume that the deleted node was in the left subtree of v and
height of this tree has decrease by 1.
Algorithm and Data Structure Analysis
v
x
h
h-2
x
h-1
v
h-1
A
B
C
C
BA
Analog: Right Rotation
If B had height h-1 before deletion,
the height of the subtree has decreased
32
Right-Left Rotation
Algorithm and Data Structure Analysis
v
x
h-2
w
h-1
h
v
h-1
A
B
D
CBA
w
C
x
D
h-1
h-1
Analog: Left-Right RotationEither B or C might have height h-1
h-1
The height of the subtree has decreased
33
Rebalancing after Deletion
• After having rebalanced for node v the height
of the tree previously rooted at v might have
decreased after deleting and rebalancing.
• If this is the case old parent of v might be
imbalanced.
• We might have to continue rebalancing until
the root has been reached.
Algorithm and Data Structure Analysis 34
Runtime AVL-trees
Theorem: The operations find, insert, and delete
can be implemented for AVL-trees in worst-case
time O(log n).
Algorithm and Data Structure Analysis 35
