preface
The complexity of binary search trees
For the binary search tree in Figure 1, the complexity of adding, deleting and querying is as follows:O(h).hIs the height of the binary tree, which is also equal toO(logn).nIs the number of nodes in the binary tree. Relatively high efficiency. It takes three times to find element 10.
However, if the element in the figure above is a node added from small to large, the binary tree will degenerate into a linked list as shown in Figure 2. At this time, the same search for element 10 will be required for 7 times.
When the node N is relatively large, the efficiency difference between the above two cases is very large.
The complexity of binary search tree is related to its height. To ensure high efficiency, it is necessary to reduce the height of binary search tree. Balanced binary search trees (AVL) can be used to efficiently use binary search books, prevent them from degenerate into linked lists and keep their complexity at O(logn).
Balance: When the number of nodes is fixed, the closer the height of the left and right subtrees are, the more balanced (the lower the height) the binary tree will be.
Optimal equilibrium, full binary tree, minimum height (minimum height difference).
Balanced binary search tree
Balanced binary search tree, abbreviated as balanced binary tree, English name AVL tree. Balance factor: the height difference between the left and right subtrees of a node. Characteristics of balanced binary trees:
- The balance factor of each node can only be 1, 0, -1 (absolute value ≤ 1, if more than 1, it is called “imbalance”)
- The height difference between the left and right subtrees of each node is no more than 1
- Search, add, delete time order (logn)
The left side of the following figure shows an AVL tree. After the addition of element 11 to it, the balance factor of node 6 becomes -2, and then it becomes an unbalanced binary tree, that is, the tree is unbalanced.
Adding elements can cause the AVL tree to be out of balance and, in the worst case, all the ancestors of the added node (excluding the parent of the added node).
The parent or non-ancestor of the added node cannot be out of balance.
When the AVL tree is out of balance due to the addition of elements, we need to rotate it properly to bring it back to balance.
Minimum imbalance subtree: Look up the newly inserted node. The subtree rooted in the node whose absolute value of the first balance factor exceeds 1 is called the minimum imbalance subtree. As shown in the figure above (non-AVL tree on the right), the tree with node 6 as the parent is called the minimum imbalance subtree.
When the addition of nodes leads to multiple unbalanced subtrees in the balanced binary tree, the smallest unbalanced subtree can be restored to the balanced tree by adjusting it.
When the insertion of new nodes leads to imbalance, we need to find the nearest unbalanced node as the axis to rotate the AVL tree to achieve equilibrium.
LL – Rotate right
For LL type, right rotation is required
LL is the node guiding the imbalance of the grandparent node is the left subtree of the grandparent node’s left subtree (left -> left).
The idea of right-handed operation is as follows: 1) The newly inserted node searches for the first unbalanced node (let’s call it G), and the subtree with this node as the root node is the least unbalanced subtree; 2) Change the right subtree of the left child of the unbalanced node into the left subtree of the node (G.eft = g.eft.right); 3) Take the unbalanced node as the right subtree of the left child node (g.eft. right = g); 4) The left child of the imbalanced node is the root node of the minimum imbalanced subtree (imbalanced node root = g.eft).
You also need to pay attention to the maintenance of the parent property and height of the relevant nodes.
As shown in the figure below, after the addition of element 4 to the previous AVL tree, the grandfather node (root node here) 8 is unbalanced, and the node causing 8 imbalance is the left subtree of the left subtree of 8 (i.e., LL-type).
For LL type, right rotation is required to restore its balance, as shown below:
RR – Turn left
For the RR, a left rotation is required to restore balance.
RR is the subordinate subtree (right -> right) of the node that causes the imbalance of the grandparent.
The idea of left-rotation operation is as follows: 1) The newly inserted node searches for the first unbalanced node (let’s call it G), and the subtree with this node as the root node is the least unbalanced subtree; 2) Change the left subtree of the right child of the unbalanced node into the right subtree of the node (G.ight = g.ight. Left); 3) Take the unbalanced node as the left subtree of the right child node (g.light.left = G); 4) The right child of the unbalanced node is the root node of the minimum unbalanced subtree (the unbalanced node root = g.light).
As shown in the figure below, after the addition of element 9 to the previous AVL tree, the grandfather node (root node here) 5 is unbalanced, and the node causing 5 imbalance is the right subtree of the right subtree of 5 (i.eRRType).
Turn left to restore balance:
LR – Left rotation, right rotation
LR is the node guiding the imbalance of the grandparent node. It is the right subtree of the left subtree of the grandparent node (left -> right).
For LR type, left-rotation and right-rotation operations need to be performed successively as follows: 1) Search for the newly inserted node and hit the first unbalanced node (let’s call it G); 2) Left-rotation operation is performed on the left child of the unbalanced node, which is then transformed into RR – left rotation; 3) Perform dextral rotation on the unbalanced node, and then transform to LL-right rotation.
As shown in the figure below, after node 7 is added to the balanced binary tree, the grandfather node 8 is unbalanced, namely: LR (the new node added is the right subtree of the left subtree of the unbalanced node).
First, the left child 5 of the unbalanced node 8 is left-handed, and then the left child 5 of the unbalanced node 8 is right-handed, as shown in the figure below:
RL – Right rotation, left rotation
For type RL, the left rotation operation is required
RL is the right -> left subtree of the left subtree of the grandfather node.
For the RL type, the right and left rotation operations need to be performed. The operation idea is as follows: 1) Search up the newly inserted node to find the first unbalanced node (let’s call it G); 2) Perform dextral rotation on the right child of the unbalanced node, which is then transformed into LL-right rotation; 3) Perform left-rotation on the unbalanced node again, and then transform to RR – left rotation.
As shown in the figure below, after node 6 is added to the balanced binary tree, the grandfather node 5 is unbalanced, namely: RL type (the new node added is the left subtree of the right subtree of the unbalanced node).
First, the right child 8 of the unbalanced node 5 is right-handed, and then the left-handed child 8 of the unbalanced node 5 is left-handed, as shown in the figure below:
Code implementation
AVL tree node structure
/** * AVL tree node class *@param< E > generic * /
private static class AVLNode<E> {
E element; // Node data
AVLNode<E> left; / / the left node
AVLNode<E> right; / / right node
AVLNode<E> parent; / / the parent node
int height; // Node height
public AVLNode(E element, AVLNode<E> parent) {
this.element = element;
this.parent = parent;
}
public boolean hasTwoChildren(a) {
returnleft ! =null&& right ! =null;
}
/** * is the left child node */
public boolean isLeftChild(a) {
return(parent ! =null && this == parent.left);
}
/** * is the right child node */
public boolean isRightChild(a) {
return(parent ! =null && this == parent.right);
}
/** * get the balance factor of the node */
public int balanceFactor(a) {
int leftHeight = left == null ? 0 : left.height;
int rightHeight = right == null ? 0 : right.height;
return leftHeight - rightHeight;
}
/** * Updates the node height */
public void updateHeight(a) {
int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
height = Math.max(leftHeight, rightHeight) + 1;
}
public AVLNode<E> tallerChildNode(a) {
int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
if (leftHeight > rightHeight) return left;
if (leftHeight < rightHeight) return right;
returnleft; }}Copy the codeAVL tree is similar to binary search tree
public class AVLTree<E> {
private int size; // Tree element size
private AVLNode<E> root; / / the root node
private Comparator<E> comparator; // Comparator rules can be externally controlled
// If no comparator rules are passed in externally, the default comparison rules implemented by objects stored in the node are used
public AVLTree(a) {
this(null);
}
// If a comparator rule is passed in externally, the comparison rule passed in is used
public AVLTree(Comparator<E> comparator) {
this.comparator = comparator;
}
// The number of elements
public int size(a) {
return size;
}
// Whether it is empty
public boolean isEmpty(a) {
return size == 0; }}Copy the codeElement to add
/** * add element * compare binary search tree, after adding nodes, need to restore the balance of tree */
public void add(E element) {
elementNotNullCheck(element);
// Add the root node
if (root == null) {
root = new AVLNode<>(element, null);
size++;
// After the element is added, the balance needs to be restored
balanceAfterAdd(root);
return;
}
// Add not the first node
1. Find the parent node
AVLNode<E> parent = root;
AVLNode<E> node = root;
int cmp = 0;
while(node ! =null) {
// Save the parent node. If not, break out of the while loop when it finds node == null
parent = node;
cmp = compare(element, node.element);
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else { / / equal
node.element = element;
return; }}// 2. See where the parent node is inserted
AVLNode<E> newNode = new AVLNode<>(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
// After the element is added, the balance needs to be restored
balanceAfterAdd(newNode);
}
/** * After adding elements, restore balance */
private void balanceAfterAdd(AVLNode<E> node) {
while((node = node.parent) ! =null) {
// Whether the node is balanced
if (isBalance(node)) {
// Update the node height
node.updateHeight();
} else {
// If the node is unbalanced, it needs to be restored to equilibrium
rebalance(node);
// If the least unbalanced tree returns to balance, the whole tree returns to balance and jumps out of the loop
break; }}}/** * restore balance */
private void rebalance(AVLNode<E> node) {
AVLNode<E> subNode = node.tallerChildNode();
AVLNode<E> subSubNode = subNode.tallerChildNode();
if (subNode.isLeftChild()) { // L
if (subSubNode.isLeftChild()) { // LL - left rotation
rotateRight(node);
} else { // LR - The child rotates left, then the unbalanced node rotates rightrotateLeft(subNode); rotateRight(node); }}else { // R
if (subSubNode.isLeftChild()) { // RL
rotateRight(subNode);
rotateLeft(node);
} else { // RRrotateLeft(node); }}}/** * left rotation - RR */
private void rotateLeft(AVLNode<E> node) {
AVLNode<E> subNode = node.right;
AVLNode<E> subSubNode = subNode.left;
node.right = subSubNode;
subNode.left = node;
// Make the subNode the root of the least unbalanced subtree
subNode.parent = node.parent;
if (node.isLeftChild()) {
node.parent.left = subNode;
} else if (node.isRightChild()) {
node.parent.right = subNode;
} else {
root = subNode;
}
// Update the parent node of subSubNode
if(subSubNode ! =null) {
subSubNode.parent = node;
}
// Update the parent node
node.parent = subNode;
// Update the height of the node
node.updateHeight();
subNode.updateHeight();
}
/** * rotate right - LL type */
private void rotateRight(AVLNode<E> node) {
AVLNode<E> subNode = node.left;
AVLNode<E> subSubNode = subNode.right;
node.left = subSubNode;
subNode.right = node;
// Make the subNode the root of the least unbalanced subtree
subNode.parent = node.parent;
if (node.isLeftChild()) {
node.parent.left = subNode;
} else if (node.isRightChild()) {
node.parent.right = subNode;
} else {
root = subNode;
}
// Update the parent node of subSubNode
if(subSubNode ! =null) {
subSubNode.parent = node;
}
// Update the parent node
node.parent = subNode;
// Update the height of the node
node.updateHeight();
subNode.updateHeight();
}
/** * Whether the node is balanced */
private boolean isBalance(AVLNode<E> node) {
return Math.abs(node.balanceFactor()) <= 1;
}
/ * * * * * * * * * * * * * * * * * * * * I'm divider (below is relevant methods of auxiliary) * * * * * * * * * * * * * * * * * * * * /
/** * element null checks *@param* / element element
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null"); }}/** * The node value is compared with *@param e1
* @param e2
* @returnThe return value is 0, indicating e1 == e2; If the return value is greater than 0, e1 > E2. If the return value is less than 0, e1 < E2; * /
private int compare(E e1, E e2) {
// If the external comparator is passed in, the external comparator is used
if (this.comparator ! =null) {
return comparator.compare(e1, e2);
}
Comparable is used by e1's Comparable class because nodes in the binary search tree must hold Comparable object elements
return ((Comparable<E>)e1).compareTo(e2);
}
Copy the codeElement to delete
Deleting a node in the AVL tree may result in deleting a parent node above the node (or the parent’s parent…). Out of balance, so you need to re-check the balance and bring it back to balance after removing the node.
Only the parent node or grandparent node may be out of balance (but only one node is out of balance). Restoring the parent node to balance may cause higher level ancestor nodes to be out of balance (at most O(logn) adjustments).
/** * delete element */
public void remove(E element) {
// Find nodes by element values
AVLNode<E> node = node(element);
if (node == null) return;
size--;
if (node.hasTwoChildren()) { // Node with degree 2
// Find the successor
AVLNode<E> s = successor(node);
// Overwrite the value of the node read 2 with the value of the successor node
node.element = s.element;
// Delete the successor node, just point node to s
node = s;
}
// Delete node (node degree must be 0 or 1, because node degree is less than 2)AVLNode<E> replaceNode = node.left ! =null ? node.left : node.right;
if(replaceNode ! =null) { // node is a node of degree 1. Use child nodes instead of replaceNode to replaceNode positions
/ / change the parent
replaceNode.parent = node.parent;
if (node.parent == null) { // Delete the root node
root = replaceNode;
}
// Change the left and right direction of the parent
if (node == node.parent.left) {
node.parent.left = replaceNode;
} else if (node == node.parent.right) {
node.parent.right = replaceNode;
}
// Restore balance after node deletion
balanceAfterRemove(node);
} else if(node.parent == null) { // Node is a leaf node and a root node
root = null;
// Restore balance after node deletion
balanceAfterRemove(node);
} else { // Node is a leaf node but not a root node
if (node == node.parent.right) {
node.parent.right = null;
} else {
node.parent.left = null;
}
// Restore balance after node deletionbalanceAfterRemove(node); }}/** * Restore balance after deleting nodes * Note: After deleting nodes, you need to restore all unbalanced nodes */
private void balanceAfterRemove(AVLNode<E> node) {
while((node = node.parent) ! =null) {
if (isBalance(node)) {
node.updateHeight();
} else {
// We need to restore all the unbalanced nodesrebalance(node); }}}/** * find node */ by value
private AVLNode<E> node(E element) {
AVLNode<E> node = root;
while(node ! =null) {
int cmp = compare(element, node.element);
// Return equal (find) directly
if (cmp == 0) return node;
// If the query element is larger than the value of the node, continue to look for the right subtree of the node
if (cmp > 0) {
node = node.right;
} else{ node = node.left; }}// While loop ends, no corresponding node is found
return null;
}
/** * gets the successor of a node */
private AVLNode<E> successor(AVLNode<E> node) {
if (node == null) return null;
// The right subtree is not empty, the precursor is in the right subtree (right.left.left...
if(node.right ! =null) {
AVLNode<E> p = node.right;
while(p.left ! =null) {
p = p.left;
}
return p;
}
// The right subtree is empty, from the parent node, the grandfather node.. Find the precursor node in
while(node.parent ! =null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
Copy the codeAt this point, the AVL tree interface has been basically implemented.