A type of Self-Balancing Binary Search Tree (平衡二叉搜索树). Basiclly, an optimised Binary Search Tree (二叉搜索树) that is either empty OR with all nodes that are Height-Balanced
Self-Balancing
When we insert or delete a node and the binary tree becomes unbalanced, AVL tree will use AVL Tree Rotation to auto-adjust the structure of the binary tree, ensuring that the tree remains height-balanced.
Always efficient searching, deletion and insertion operations
The self-balancing property guarantees that the Tree Height of an AVL tree with n nodes is always around O(logn). This means operations like searching, insertion, and deletion take a maximum of O(logn) time, making them very efficient.
The node should have a piece of information that describes its current Node Height, so its parent node is able to calculate the AVL Tree Balance Factor to see if re-balancing is needed, saving the computation to re-calculate the node height when parent node needs the information
Below shows the codes for AVL tree node definition
/* AVL Tree Node Definition */class TreeNode { public int val; // Node value public int height; // Node height, default 0 public TreeNode left; // left child node, default null node public TreeNode right; // right child node, default null node public TreeNode(int x) { val = x; }}
These rotations are performed to restore the balance whenever the Balance Factor of a node becomes greater than 1 or less than −1
AVL Tree Right Rotation
When the Balance Factor of a node(parent node) is bigger than 1 - skewed to the left. We right rotate the parent node to its left child node. So the left child node becomes the parent node and the parent node becomes the child node
What if the left child node has a node as its right node?
In this case, the right node of the left child node is a grandchild node to the parent node. We simply place the grandchild node as the left child of the parent node, as shown in the diagram below.
Code
/* Right Rotation */TreeNode rightRotate(TreeNode node) { TreeNode child = node.left; TreeNode grandChild = child.right; // Right rotate the node to its right child node child.right = node; node.left = grandChild; // Update the height of the node and the child node(the parent node after right rotation) updateHeight(node); updateHeight(child); // Return the child node return child;}
AVL Tree Left Rotation
When the Balance Factor of a node(parent node) is smaller than −1 - skewed to the right. We left rotate the parent node to its right child node. So the right child node becomes the parent node and the parent node becomes the child node
What if the right child node has a node as its left node?
In this case, the left node of the right child node is a grandchild node to the parent node. We simply place the grandchild node as the right child of the parent node, as shown in the diagram below.
Code
/* Left Rotation */TreeNode leftRotate(TreeNode node) { TreeNode child = node.right; TreeNode grandChild = child.left; // Left rotate the node to its left child node child.left = node; node.right = grandChild; // Update the height of the node and the child node(the parent node after left rotation) updateHeight(node); updateHeight(child); // Return the child node return child;}
AVL Tree Left-Right Rotation
The AVL Tree is skewed to the left side, so we should perform AVL Tree Right Rotation on the parent node. However, the child node has a Balance Factor that is <0. This means the child node’s right side is one level deeper(there is no way to be deeper because in that case, we will perform self-balancing on the child node already). If we perform a right rotation, the parent node will be added to the child node as the right node, the −1 to the parent’s left hand side is offset by addition of parent node to the child node. Thus, the AVL Tree remains NOTHeight-Balanced
The way to handle this is to perform AVL Tree Left Rotation on the child node first, so the left hand side of the child node is one level deeper than the right side. Now if we perform right rotation on the parent node, the child node will become the new parent node, and its left hand side−1 and right side+1, so from left−right=2 to (left−1)−(right+1)=left−right−1−1=2−2=0
The AVL Tree is skewed to the right side, so we should perform AVL Tree Left Rotation on the parent node. However, the child node has a Balance Factor that is >0. This means the child node’s left side is one level deeper(there is no way to be deeper because in that case, we will perform self-balancing on the child node already). If we perform a left rotation, the parent node will be added to the child node as the left node, the −1 to the parent’s right hand side is offset by addition of parent node to the child node. Thus, the AVL Tree remains NOTHeight-Balanced
The way to handle this is to perform AVL Tree Right Rotation on the child node first, so the right hand side of the child node is one level deeper than the left side. Now if we perform left rotation on the parent node, the child node will become the new parent node, and its right hand side−1 and left side+1, so from left−right=−2 to (left+1)−(right−1)=left−right+1+1=−2+2=0
/* Node Insertion */void insert(int val) { root = insertHelper(root, val);}/* Node Insertion using recursion(dfs helper) */TreeNode insertHelper(TreeNode node, int val) { if (node == null) return new TreeNode(val); /* Find the insertion point - a null node, and replace it with the new Node to perform node insertion */ if (val < node.val) node.left = insertHelper(node.left, val); else if (val > node.val) node.right = insertHelper(node.right, val); else return node; // Abort the node insertion if it is a duplicated node updateHeight(node); // Update the height of node all the way back to the root node /* AVL Tree rotation for self-balancing */ node = rotate(node); // Return the root node of the subtree return node;}
AVL Tree Deletion
Similar to BST Node Deletion, but we need to perform self-balancing after the deletion which can be conveniently performed using Recursion. We are using recursion to find the deleted node, so we don’t need to keep track of the previous node manually
/* Node Deletion */void remove(int val) { root = removeHelper(root, val);}/* Node Deletion using recursion(dfs helper) */TreeNode removeHelper(TreeNode node, int val) { if (node == null) return null; /* 1. Find node that is the desired node */ if (val < node.val) // Since the value of deleted node is smaller, go to left subtree to find the deleted node node.left = removeHelper(node.left, val); else if (val > node.val) // Since the value of deleted node is bigger, go to right subtree to find the deleted node node.right = removeHelper(node.right, val); else { // deleted node found! // The degree of deleted node is 0 or 1 if (node.left == null || node.right == null) { TreeNode child = node.left != null ? node.left : node.right; // when degree is 0 ,delete current node and return null node if (child == null) return null; // when degree is 1, replace current node with its child node else node = child; } else { // The degree of deleted node is 2 TreeNode temp = node.right; while (temp.left != null) { temp = temp.left; } // replace the current node with the smallest node from its right subtree node.right = removeHelper(node.right, temp.val); node.val = temp.val; } } updateHeight(node); // update the node height recursively /* AVL Tree rotation for self-balancing */ node = rotate(node); return node; // return the root node of the subtree}
Red-black Tree
Like AVL Tree, red-black tree is a type of self-balancing binary tree, but with more relaxing balancing requirement, this means less AVL Tree Rotation needed, thus better efficiency for node insertion and deletion