621 words - 2 pages

Red-Black Trees 4/10/2002 11:1

AVL Trees 1

AVL Trees 6

3 8

4

v

z

AVL Trees 2

AVL Tree Definition

Š AVL trees are balanced. Š An AVL Tree is a

binary search tree such that for every internal node v of T, the heights of the children of v can differ by at most 1.

88

44

17 78

32 50

48 62

2

4

1

1

2

3

1

1

An example of an AVL tree where the heights are shown next to the nodes:

AVL Trees 3

Height of an AVL Tree Š Fact: The height of an AVL tree storing n keys is O(log n). Š Proof: Let us bound n(h): the minimum number of internal

nodes of an AVL tree of height h. Š We easily see that n(1) = 1 and n(2) = 2 Š For n > 2, an AVL tree of height h contains the root node,

one AVL subtree of height n-1 and another of height n-2. Š That is, n(h) = 1 + n(h-1) + n(h-2) Š Knowing n(h-1) > n(h-2), we get n(h) > 2n(h-2). So

n(h) > 2n(h-2), n(h) > 4n(h-4), n(h) > 8n(n-6), … (by induction), n(h) > 2in(h-2i)

Š Solving the base case we get: n(h) > 2 h/2-1 Š Taking logarithms: h < 2log n(h) +2 Š Thus the height of an AVL tree is O(log n)

3

4 n(1)

n(2)

AVL Trees 4

Insertion in an AVL Tree Š Insertion is as in a binary search tree Š Always done by expanding an external node. Š Example: 44

17 78

32 50 88

48 62

54 w

b=x

a=y

c=z

44

17 78

32 50 88

48 62

before insertion after insertion

AVL Trees 5

Trinode Restructuring Š let (a,b,c) be an inorder listing of x, y, z Š perform the rotations needed to make b the topmost node of

the three

b=y

a=z

c=x

T0

T1

T2 T3

b=y

a=z c=x

T0 T1 T2 T3

c=y

b=x

a=z

T0

T1 T2

T3 b=x

c=ya=z

T0 T1 T2 T3 case 1: single rotation (a left rotation about a)

case 2: double rotation (a right rotation about c, then a left rotation about a)

(other two cases are symmetrical)

AVL Trees 6

Insertion Example, continued

88

44

17 78...

Get inspired and start your paper now!