AVL TREE java dalam penerapannya dan aplikasinya

avl tree

1. AVL Tree

2. AVL Trees
•Unbalanced Binary Search Trees are bad. Worst
case: operations take O(n).
•AVL (Adelson-Velskii& Landis) trees maintain
balance.
•For each node in tree, height of left subtreeand
height of right subtreediffer by a maximum of 1.
X X
H
H-1
H-2

3. AVL Trees
10
5
3
20
2
1 3
10
5
3
20
1
43
5

4. AVL Trees
12
8 16
4 10
2 6
14

5. Insertion for AVL Tree
•After insert 1
12
8 16
4 10
2 6
14
1

6. Insertion for AVL Tree
•To ensure balance condition for AVL-tree, after
insertion of a new node, we back up the path
from the inserted node to root and check the
balance condition for each node.
•If after insertion, the balance condition does
not hold in a certain node, we do one of the
following rotations:
–Single rotation
–Double rotation

7. Insertions Causing Imbalance
•An insertion into the
subtree:
–P (outside) -case 1
–Q (inside) -case 2
•An insertion into the
subtree:
–Q (inside) -case 3
–R (outside) -case 4
R
P
Q
k
1
k
2
Q
k
2
P
k
1
R
H
P=H
Q=H
R

8. Single Rotation (case 1)
A
k
2
B
k
1
C
CB
A
k
1
k
2
H
A=H
B+1
H
B=H
C

9. Single Rotation (case 4)
C
k
1
B
k
2
A
A B
C
k
2
k
1
H
A=H
B
H
C=H
B+1

10. Problem with Single Rotation
•Single rotation does not work for case 2 and 3
(inside case)
Q
k
2
P
k
1
R
R
P
Q
k
1
k
2
H
Q=H
P+1
H
P=H
R

11. Double Rotation: Step
C
k
3
A
k
1
D
B
k
2
C
k
3
A
k
1
D
B
k
2
H
A=H
B=H
C=H
D

12. Double Rotation: Step
C
k
3
A
k
1
DB
k
2

13. Double Rotation
C
k
3
A
k
1
D
B
k
2
C
k
3
A
k
1
DB
k
2
H
A=H
B=H
C=H
D

14. Double Rotation
B
k
1
D
k
3
A
C
k
2
B
k
1
D
k
3
A C
k
2
H
A=H
B=H
C=H
D

15. Example
•Insert 3 into the AVL tree
3
11
8
20
4
16 27
8
8
11
4 20
3 16 27

16. Example
•Insert 5 into the AVL tree
5
11
8
20
4
16 27
8
11
5 20
4 16 27
8

17. AVL Trees: Exercise
•Insertion order:
–10, 85, 15, 70, 20, 60, 30, 50, 65, 80, 90, 40, 5, 55

18. Remove Operation in AVL Tree
•Removing a node from an AVL Tree is the
same as removing from a binary search tree.
However, it may unbalancethe tree.
•Similar to insertion, starting from the removed
node we check all the nodes in the path up to
the root for the first unbalance node.
•Use the appropriate single or double rotation
to balance the tree.
•May need to continue searching for
unbalanced nodes all the way to the root.

19. Deletion X in AVL Trees
•Deletion:
–Case 1: if X is a leaf, delete X
–Case 2: if X has 1 child, use it to replace X
–Case 3: if X has 2 children, replace X with its
inorder predecessor(and recursively delete it)
•Rebalancing

20. Delete 55 (case 1)
60
20 70
10 40 65 85
5 15 30 50
80 90
55

21. Delete 55 (case 1)
60
20 70
10 40 65 85
5 15 30 50
80 90
55

22. Delete 50 (case 2)
60
20 70
10 40 65 85
5 15 30 50
80 90
55

23. Delete 50 (case 2)
60
20 70
10 40 65 85
5 15 30
50
80 90
55

24. Delete 60 (case 3)
60
20 70
10 40 65 85
5 15 30 50
80 90
55
prev

25. Delete 60 (case 3)
55
20 70
10 40 65 85
5 15 30 50
80 90

26. Delete 55 (case 3)
55
20 70
10 40 65 85
5 15 30 50
80 90
prev

27. Delete 55 (case 3)
50
20 70
10 40 65 85
5 15 30
80 90

28. Delete 50 (case 3)
50
20 70
10 40 65 85
5 15 30
80 90
prev

29. Delete 50 (case 3)
40
20 70
10 30 65 85
5 15
80 90

30. Delete 40 (case 3)
40
20 70
10 30 65 85
5 15
80 90
prev

31. Delete 40 : Rebalancing
30
20 70
10 65 85
5 15
80 90
Case ?

32. Delete 40: after rebalancing
30
7010
20 65 855
15
80 90
Single rotation is preferred!

33. Minimum Element in AVL Tree
•An AVL Tree of height Hhas at least F
H+3-1
nodes, where F
iis the i-th fibonacci number
•S
0= 1
•S
1= 2
•S
H= S
H-1+ S
H-2+ 1
S
H-1
S
H-2
H
H-1
H-2

34. AVL Tree: analysis (1)328.1)2log(44.1
5/φ
)(
618.12/)5(1φ
5/φ
3H
i




NH
roughlyleastathasHheightofTreeAVL
F
i

35. AVL Tree: analysis (2)
•The depth of AVL Trees is at most logarithmic.
•So, all of the operations on AVL trees are also
logarithmic.
•The worst-case height is at most 44 percent
more than the minimum possible for binary
trees.

36. Summary
•Find element, insert element, and remove
element operations all have complexity
O(log n) for worst case
•Insert operation: top-down insertion and
bottom up balancing