Please enable JavaScript.
Coggle requires JavaScript to display documents.
AVL Tree (What is an AVL Tree? (Motivation for being Balanced: Since most…
AVL Tree
What is an AVL Tree?
-
To achieve its property of being balanced,
it keeps track of a variable called balance factor
- A balance factor (bf) is
calculated for each node in the AVL Tree
- bf = height of left-subtree - height of right-subtree
- A bf of any node in an AVL Tree strictly only has
a value 0, 1 or -1.
- |bf| <= 1
- To calculate height of a subtree, count edges, not the nodes
When there is a node that has a |bf| > 1, it needs to be rotated
-
Motivation for being Balanced: Since most Binary Search Tree operations are directly proportional to height, we want to reduce height as far as possible for sake of efficiency
-
-
Since height in balanced tree is closed to log n, it is c log n, therefore all operations in a balanced BST, that had O(h) can now be O( log n)
Implementation:
AVLTree Class
AVLTreeVertex root
- Therefore height of AVLTree = root.height;
- Size of AVLTree = root.size;
AVLTreeVertex
- int height (i.e. number of edges from this vertex to deepest leaf) // Why? To calculate balance factor for each vertex after a Dynamic Operation)
- Height is -1 if tree is empty (i.e. null Vertex)
- height of current vertex x = max(x.left.height, x.right.height) + 1
- int size (i.e. total number of vertices in the subtree of this vertex + 1) // Why? for Select Operation
- x.size = 0 (if x is an empty tree, i.e. x is null)
- x.size = x.left.size + x.right.size + 1
-
- AVLTreeVertex parent, left, right
-
-