程序代写代做代考 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