- Home
- Documents
*Binary Search Tree (Part 2 The AVL-tree) taoyf/course/2100/20-fall/lec/bst...¢ 2020. 11....*

prev

next

out of 34

View

0Download

0

Embed Size (px)

1/34

Binary Search Tree (Part 2 – The AVL-tree)

Yufei Tao

Department of Computer Science and Engineering Chinese University of Hong Kong

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

2/34

We have already learned a static version of the BST. In this lecture, we will make the structure dynamic, namely, allowing it to support updates (i.e., insertions and deletions). The dynamic version we will learn is called the AVL-tree.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

3/34

Recall:

Binary Search Tree (BST)

A BST on a set S of n integers is a binary tree T satisfying all the following requirements:

T has n nodes.

Each node u in T stores a distinct integer in S , which is called the key of u.

For every internal u:

– its key is larger than all the keys in the left subtree; – its key is smaller than all the keys in the right subtree.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

4/34

Recall:

Balanced Binary Tree

A binary tree T is balanced if the following holds on every internal node u of T :

The left and right subtrees of u differ by at most 1 in height.

If u violates the above requirement, we say that u is imbalanced.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

5/34

AVL-Tree

An AVL-tree on a set S of n integers is a balanced binary search tree T where the following holds on every internal node u

u stores the heights of its left and right subtrees.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

6/34

Example

An AVL-tree on S = {3, 10, 15, 20, 30, 40, 60, 73, 80}

40

15 73

3010 60 80

3 20

3 2

2 2

1 0 1 0

1 1

For example, the numbers 3 and 2 near node 40 indicate that its left subtree has height 3, and its right subtree has height 2.

By storing the subtree heights, an internal node knows whether it has become imbalanced.

The left subtree height of an internal node can be obtained in O(1) time from its left child (how?). Similarly for the right.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

7/34

Next, we will explain how to perform updates. The most crucial step is to remedy a node u when it becomes imbalanced.

It suffices to consider a scenario called 2-level imbalance. In this situation, two conditions apply:

There is a difference of 2 in the heights of the left and right subtrees of u.

All the proper descendants of u are balanced.

Before delving into the insertion and deletion algorithms, we will first explain how to rebalance u in the above situation.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

8/34

2-Level Imbalance

There are two cases:

h + 2hh + 2 h

Due to symmetry, it suffices to explain only the left case, which can be

further divided into a left-left and a left-right case, as shown next.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

9/34

2-Level Imbalance

h + 1

h

h + 1

h

h or h + 1 h

Left-left Left-Right

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

10/34

Rebalancing Left-Left

By a rotation:

h + 1

h

b

C

CB BA

A

b

a

a

⇒h + 1 x

h + 2 h h + 1

hx

x + 1

Only 3 pointers to change (the red ones). The cost is O(1).

Recall x = h or h + 1.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

11/34

Rebalancing Left-Right

By a double rotation:

⇒ h b

c

h+ 1

h

a

b

A

C

⇒

c

b

A

B

B

a

C

D

D

a hh+ 2

h+ 1h

hh+ 2

h+ 1h

x y

x yh h

h+ 1h+ 1

Only 5 pointers to change (see above). Hence, the cost is O(1).

Note that x and y must be h or h − 1. Furthermore, at least one of them must be h (why?).

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

12/34

We are now to explain the insertion algorithm

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

13/34

Insertion

Suppose that we need to insert a new integer e. First create a new leaf z storing the key e. This can be done by descending a root-to-leaf path:

1 Set u ← the root of T 2 If e < the key of u

2.1 If u has a left child, then set u to the left child. 2.2 Otherwise, make z the left child of u, and done.

3 Otherwise:

3.1 If u has a right child, then set u to the right child 3.2 Otherwise, make z the right child of u, and done.

4 Repeat from Line 2.

Finally, update the subtree height values on the nodes of the root-to-z

path in the bottom-up order. The total cost is proportional to the height

of T , i.e., O(log n).

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

14/34

Example

Inserting 35:

40

15 73

3010 60 80

353 20

1

22

3

1

The red height values are modified by this insertion.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

15/34

Example

An insertion may cause the tree to become imbalanced!

40

15 73

3010 60 80

35

40

15 73

3010 60 80

3 35

361

203 20

In the left tree, nodes 10 and 40 become imbalanced, whereas in the

right, node 40 is now imbalanced.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

16/34

Imbalance in an Insertion

...

Only the nodes along the path from the insertion path (from the root to

the newly added leaf) can become imbalanced. It suffices remedy only

the lowest imbalanced node.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

17/34

Left-Left Example

h + 1

h

b

C

CB BA

A

b

a

a

⇒h + 1 x

h + 2 h h + 1

hx

x + 1

⇒

3 20

40

15 73

60 8030

35

1

10

20

40

15 73

60 803 30

35101

2 0

1 0

1 1

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

18/34

Left-Right Example

⇒ h b

c

h+ 1

h

a

b

A

C

⇒

c

b

A

B

B

a

C

D

D

a hh+ 2

h+ 1h

hh+ 2

h+ 1h

x y

x yh h

h+ 1h+ 1

40

73

60 80 ⇒

30

73

60 80

40

30

36

35 36

35

15

3

15

10

3 20

2010

4 2

2 3

1 2

3 3

222 1

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

19/34

Insertion Time

...

It will be left as an exercise for you to prove:

Only 2-level imbalance can occur in an insertion.

Once we have remedied the lowest imbalanced node, all the nodes in the tree will become balanced again.

The total insertion time is therefore O(log n).

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

20/34

We now proceed to explain the deletion algorithm.

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

21/34

Deletion

Suppose that we want to delete an integer e. First, find the node u whose key equals e in O(log n) time (through a predecessor query).

Case 1: If u is a leaf node, simply remove it from (the AVL-tree) T .

Case 1 Example

Remove 60:

30

4015

3

2010 35

36

73

60

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

22/34

Deletion

Now suppose that node u (containing the integer e to be deleted) is not a leaf node. We proceed as follows:

Case 2: If u has a right subtree:

Find the node v storing the successor s of e. Set the key of u to s Case 2.1: If v is a leaf node, then remove it from T . Case 2.2: Otherwise, it must hold that v has a right child w , which is a leaf (why?), but not left child. Set the key of v to that of w , and remove w from T .

Case 3: If u has no right subtree:

It must hold that u has a left child v , which is a leaf. (why?) Set the key of u to that of v , and remove v from T .

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

23/34

Case 2.1 Example

Delete 40:

30

4015

3

2010 35

36

30

15

3

2010 35

36

73

60

73

60 ⇒

Yufei Tao Binary Search Tree (Part 2 – The AVL-tree)

24/34

Case 2.2 Example

Delete 30:

30

4015

3

2010 35

36

35