Recall the properties of binary search tree:
- each node has
- key
- left pointer
- right pointer
- parent pointer
- height of the node = length (number of edges) of longest downward path to a leaf
- BST will do all operations in $O(h)$ time, h = height
- h is between $lg n$ and $n$.
The advantage of balanced tree is that it maintains $h=O(lg n)$, therefore, all operations run in $O(lg n)$ time.
Tree rotation
The operation “rotation” is to make a tree balanced and will be used in fixing the inbalance of AVL tree.
There are two categories: single rotation and two rotations.
Left Rotation
Application scenario: When a node A’s right subtree becomes inbalanced after inserting another new one. Then need to apply the left rotation of that node (A).
After performing the left rotation of node A, A’s right child becomes its parent and A becomes the left child.
Right Rotation
Application scenario: When a node A’s left subtree becomes inbalanced after inserting another new one. Then need to apply the right rotation of that node (A).
After performing the right rotation of the unbalanced node A, it becomes the right child of its original left child.
Left-Right Rotation
Application scenario: When a node A becomes inbalanced after inserting another new one to the right subtree of the left subtree of A.
Steps:
- Perform left rotation to the left subtree of A
- Perform right rotation of the A itself
Right-Left Rotation
Application scenario: When a node A becomes inbalanced after inserting another new one to the left subtree of the right subtree of A.
Steps:
- Perform right rotation to the right subtree of A
- Perform left rotation of the A itself
Implementation:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35def left_rotate(self, x):
y = x.right
y.parent = x.parent
if y.parent is None:
self.root = y
else:
if y.parent.left is x:
y.parent.left = y
elif y.parent.right is x:
y.parent.right = y
x.right = y.left
if x.right is not None:
x.right.parent = x
y.left = x
x.parent = y
update_height(x)
update_height(y)
def right_rotate(self, x):
y = x.left
y.parent = x.parent
if y.parent is None:
self.root = y
else:
if y.parent.left is x:
y.parent.left = y
elif y.parent.right is x:
y.parent.right = y
x.left = y.right
if x.left is not None:
x.left.parent = x
y.right = x
x.parent = y
update_height(x)
update_height(y)
Here is a very nice illustration: https://wiki2.org/en/Tree_rotation#/media/File:Tree_Rebalancing.gif
AVL tree
- named by the author.
- for every node, require height of left & right children to differ by at most 1
- nil tree as height -1
- each node stores its height (using data structure augmentation)
AVL Insert
- Perform the normal BST insertion.
- The current node must be one of the ancestors of the newly inserted node. Update the height of the current node.
- Get the balance factor (left subtree height – right subtree height) of the current node.
- If balance factor is greater than 1, then the current node is unbalanced and we are either in Left Left case or left Right case. To check whether it is left left case or not, compare the newly inserted key with the key in left subtree root.
- If balance factor is less than -1, then the current node is unbalanced and we are either in Right Right case or Right-Left case. To check whether it is Right Right case or not, compare the newly inserted key with the key in right subtree root.
- Time: $\theta (nlg n)$
Code of rebalance the tree:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def rebalance(self, node):
while node is not None:
update_height(node)
if height(node.left) >= 2 + height(node.right):
if height(node.left.left) >= height(node.left.right):
self.right_rotate(node)
else:
self.left_rotate(node.left)
self.right_rotate(node)
elif height(node.right) >= 2 + height(node.left):
if height(node.right.right) >= height(node.right.left):
self.left_rotate(node)
else:
self.right_rotate(node.right)
self.left_rotate(node)
node = node.parent
General
Other balanced trees:
- B-Trees/2-3-4 Trees
- BB[α] Trees
- Red-black Trees
- (A) — Splay-Trees
- (R) — Skip Lists
- (A) — Scapegoat Trees
- (R) — Treaps
(R) = use random numbers to make decisions fast with high probability
(A) = “amortized”: adding up costs for several operations =⇒ fast on average
Data Structure (DS) vs Abstract Data Type (ADT)
- ADT is a logical description and data structure is concrete.
- ADT is the logical picture of the data and the operations to manipulate the component elements of the data.
- Data structure is the actual representation of the data during the implementation and the algorithms to manipulate the data elements.
- ADT is in the logical level and data structure is in the implementation level.
There are many possible DSs for one ADT.
Some common ADTs:
- stack, queue, priority queue, dictionary, sequence, set
Some common DSs used to implement the above ADTS:
- array, linked list, hash table (open, closed, circular hashing)
- trees (binary search trees, heaps, AVL trees, 2-3 trees, tries, red/black trees, B-trees)
Reference:
https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm
https://www.geeksforgeeks.org/avl-tree-set-1-insertion/