Java Reference
In-Depth Information
25
25
10
LL rotation
at node 25
10
34
10
5
25
5
20
30
50
5
20
20
(a) Delete 34, 30, 50
(b) After 34, 30, 50 are deleted
(c) Balanced
10
20
RL rotation at 10
25
10
25
20
(d) After 5 is deleted
(e) Balanced
F
IGURE
26.11
The tree evolves as elements are deleted from the tree.
Since the height of an AVL tree is O(log n), the time complexity of the
search
,
insert
, and
delete
methods in
AVLTree
is O(log n).
Key
Point
The time complexity of the
search
,
insert
, and
delete
methods in
AVLTree
depends on
the height of the tree. We can prove that the height of the tree is
O
(log
n
).
Let
G
(
h
) denote the minimum number of the nodes in an AVL tree with height
h
. Obvi-
ously,
G
(1) is 1 and
G
(2) is 2. The minimum number of nodes in an AVL tree with height
h
tree height
Ú
-
3 must have two minimum subtrees: one with height
h
1 and the other with height
h
-
2. Thus,
G
(
h
)
=
G
(
h
-
1)
+
G
(
h
-
2)
+
1
Recall that a Fibonacci number at index
i
can be described using the recurrence relation
F
(
i
)
=
F
(
i
-
1)
+
F
(
i
-
2). Therefore, the function
G
(
h
) is essentially the same as
F
(
i
). It
can be proven that
h
6
1.4405 log(
n
+
2)
-
1.3277
where
n
is the number of nodes in the tree. Hence, the height of an AVL tree is
O
(log
n
).
The
search
,
insert
, and
delete
methods involve only the nodes along a path in the tree.
The
updateHeight
and
balanceFactor
methods are executed in a constant time for each
node in the path. The
balancePath
method is executed in a constant time for a node in the
path. Thus, the time complexity for the
search
,
insert
, and
delete
methods is
O
(log
n
).
26.22
What is the maximum/minimum height for an AVL tree of 3 nodes, 5 nodes, and 7
nodes?
26.23
If an AVL tree has a height of 3, what maximum number of nodes can the tree have?
What minimum number of nodes can the tree have?
26.24
If an AVL tree has a height of 4, what maximum number of nodes can the tree have?
What minimum number of nodes can the tree have?
✓
✓
Check
Point
Search WWH ::
Custom Search