Introduction
AVL Tree is a kind of binary search tree. Different from binary search tree is, it is self-balanced. The heights of two child subtress of node differ by at most one. Because of this, another name of AVL Tree is height-balanced.
These are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has Theta(lg n) height and hence Theta(lg n) worst case lookup and insertion times. However, ordinary binary search trees have a bad worst case. When sorted data is inserted, the binary search tree is very unbalanced, essentially more of a linear list, with Theta(n) height and thus Theta(n) worst case insertion and lookup times. AVL trees overcome this problem.
The balance factor of a node is the height of its right subtree minus the height of its left subtree.
i.e.
B.F. = rightHeight - leftHeight
An equivalent definition, then, for an AVL tree is that it is a binary search tree in which each node has a balance factor of -1, 0, or +1. Note that a balance factor of -1 means that the subtree is left-heavy, and a balance factor of +1 means that the subtree is right-heavy. For example, in the following AVL tree, note that the root node with balance factor +1 has a right subtree of height 1 more than the height of the left subtree. (The balance factors are shown at the top of each node.)
Operations on AVL tree
Deleting a node from AVL Tree
Deleting the node works the same way, when we delete the node, if it upsets the balance, it will have to re-balance. Eg. Consider the tree
AVL Tree is a kind of binary search tree. Different from binary search tree is, it is self-balanced. The heights of two child subtress of node differ by at most one. Because of this, another name of AVL Tree is height-balanced.
These are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has Theta(lg n) height and hence Theta(lg n) worst case lookup and insertion times. However, ordinary binary search trees have a bad worst case. When sorted data is inserted, the binary search tree is very unbalanced, essentially more of a linear list, with Theta(n) height and thus Theta(n) worst case insertion and lookup times. AVL trees overcome this problem.
Definitions
The height of a binary tree is the maximum path length from the root to a leaf. A single-node binary tree has height 0, and an empty binary tree has height -1. As another example, the following binary tree has height 3.
7
/ \
3 12
/ / \
2 10 20
/ \
9 11
An AVL tree is a binary search tree in which every node is height balanced, that is, the difference in the heights of its two subtrees is at most 1.The balance factor of a node is the height of its right subtree minus the height of its left subtree.
i.e.
B.F. = rightHeight - leftHeight
An equivalent definition, then, for an AVL tree is that it is a binary search tree in which each node has a balance factor of -1, 0, or +1. Note that a balance factor of -1 means that the subtree is left-heavy, and a balance factor of +1 means that the subtree is right-heavy. For example, in the following AVL tree, note that the root node with balance factor +1 has a right subtree of height 1 more than the height of the left subtree. (The balance factors are shown at the top of each node.)
+1 (3-2)
30
/ \
-1 (0-1) 0 (2-2)
22 62
/ / \
0 +1 -1
5 44 95
\ /
0 0
51 77
The idea is that an AVL tree is close to being completely balanced. Hence it should have Theta(lg n) height (it does - always) and so have Theta(lg n) worst case insertion and lookup times. An AVL tree does not have a bad worst case, like a binary search tree which can become very unbalanced and give Theta(n) worst case lookup and insertion times. The following binary search tree is not an AVL tree. Notice the balance factor of -2 at node 70.
-1
100
/ \
-2 -1
70 150
/ \ / \
+1 0 +1 0
30 80 130 180
/ \ \
0 -1 0
10 40 140
/
0
36
Operations on AVL tree
Inserting a New Item
Deleting a node from AVL Tree
Deleting the node works the same way, when we delete the node, if it upsets the balance, it will have to re-balance. Eg. Consider the tree
0 comments:
Post a Comment