1. Balanced Binary Search Tree
Balance: when the number of nodes is fixed, the closer the height of the left and right subtrees is, the more balanced the binary tree is, that is, the lower the height is. The ideal balance is the minimum height like complete binary tree and full binary tree.
Common balanced binary search trees:
- AVL tree
- Red black tree
Improvement plan:
Improve on the basis of binary search tree. After nodes are added and deleted, try to restore the balance of binary tree.
- Before improvement:
- After improvement:
However, if the number of adjustments is too many, it may also increase the time complexity. Therefore, use as few adjustment times as possible to achieve a moderate balance.
2. AVL tree
2.1 AVL concept
- Balance Factor: the height difference (left right) between the left and right subtrees of a node.
- Features: the balance factor of each node can only be 1 0 - 1, otherwise it is called imbalance, that is, the left-right height difference of each node can not exceed 1.
- The time complexity of searching, adding and deleting is O(logn).
2.2 add
2.2.1 imbalance
When adding elements, the worst-case scenario may lead to the imbalance of all ancestor nodes, but it will not lead to the imbalance of non ancestor nodes and parent nodes.
For example, below is a part of a tree:
If you add element 13:
It will cause the imbalance of its ancestor nodes except the parent node to the root node.
2.2.2 LL right rotation (single rotation)
LL: the left child of its left child node causes its imbalance.
As shown in the following figure: before adding, the left and right height t0 of node n = T1, the height T2 of parent node p = t0 + 1, and the height T3 of ancestor node g = T2 + t0 are now in equilibrium.
After adding elements: g right height T3 = T2 + T0 + 1, its balance factor becomes 2, resulting in the imbalance of ancestor node g.
Solution: Let G rotate right once. Let the right child node of P become the left child node of G, change g into the right child node of P, and make p become the root node of this subtree. Modify the parent pointing of nodes, and modify the height of nodes g and P in order. After adjustment, it will not only keep the balance of AVL tree, but also maintain the nature of search tree.
g.left = p.right; p.right = g;
Adjust pointing:
Modify the node structure.
2.2.3 RR right rotation (single rotation)
RR: the right child node of its right child node causes its imbalance.
At this time, it is in equilibrium:
Adding a child node to T3 will cause the balance factor of g to become - 2.
Solution:
g.right = p.left; p.left = g;
Then let p be the root node of the subtree. Then modify the parent attribute and modify the height of g and P in order.
Modify direction:
Structural adjustment:
2.2.4 LR - RR left rotation, LL right rotation (double rotation)
As shown in the following figure, when adding a new node (Red Square), you need to find the left child node first and then the right child node, which is called LR.
After addition, the balance factor of g becomes 2, resulting in imbalance.
Solution:
- Rotate p to the left first
Figure after left rotation: obviously no balance is restored.
- Restore balance after another right rotation:
2.2.5 RL - LL right rotation, RR left rotation (double rotation)
When adding, the case of finding the right child node first and then the left child node is called RL.
Solution:
-
Rotate right first
-
Rotate left again
-
Restore balance
2.2.6 interface design
Because AVL tree is a special branch of BST tree, it can inherit BST tree directly.
- New method of BST tree: implemented by subclasses
/**
* Processing after adding nodes is implemented by subclasses
* @param node
*/
protected void afterAdd(Node<E> node){
}
- In the add() method, middle note is called:
/**
* Add element
* @param e
*/
public void add(E e){
elementNotNullCheck(e);
// Add first node
if (root == null){
root = new Node<>(e,null);
size++;
// Processing after adding nodes
afterAdd(root);
return;
}
// Record parent node
Node<E> parent = root;
// Record the node of the current comparison
Node<E> node = root;
// Record comparison value
int cmp = 0;
while (node != null){
// Gets the comparison value with the current node
cmp = compare(e, node.e);
// Save parent node
parent = node;
if (cmp > 0){ // If it is greater than the value of the current node, find the right child node
node = node.right;
}else if (cmp < 0){ // If it is less than the value of the current node, find the left child node
node = node.left;
}else { // equal
// Overwrite the original value of the node with the passed in value
node.e = e;
return;
}
}
// According to the last comparison value, judge whether to put it on the left child node or the right child node.
Node<E> nowNode = new Node<>(e, parent);
if (cmp > 0){
parent.right = nowNode;
}else {
parent.left = nowNode;
}
// Processing after adding nodes
afterAdd(nowNode);
size++;
}
2.2.6 interface realization
The main implementation here is the afterAdd() method.
2.2.6.1 improve AVL node class
- The attribute of tree height and tree height need not be added and maintained in the binary tree, because the attribute of tree height and tree height are not added here Node.
private static class AVLNode<E> extends Node<E>{
// height
// Each new node is a leaf node, and the height of the leaf node is 1.
int height = 1;
public AVLNode(E e, Node<E> parent) {
super(e, parent);
}
}
- New critenode (E, node < E > parent) interface: because the node in the adding method of BST tree is the node of binary tree, the node of AVL tree cannot be used to maintain the height attribute. Therefore, the new interface in the binary tree is implemented by subclasses.
/**
* Create node interface
* @param e
* @param parent
* @return
*/
protected Node<E> createNode(E e, Node<E> parent){
return new Node<>(e,parent);
}
- Modify add (E): call createNode directly.
/**
* Add element
* @param e
*/
public void add(E e){
elementNotNullCheck(e);
// Add first node
if (root == null){
root = createNode(e,null);
size++;
// Processing after adding nodes
afterAdd(root);
return;
}
// Record parent node
Node<E> parent = root;
// Record the node of the current comparison
Node<E> node = root;
// Record comparison value
int cmp = 0;
while (node != null){
// Gets the comparison value with the current node
cmp = compare(e, node.e);
// Save parent node
parent = node;
if (cmp > 0){ // If it is greater than the value of the current node, find the right child node
node = node.right;
}else if (cmp < 0){ // If it is less than the value of the current node, find the left child node
node = node.left;
}else { // equal
// Overwrite the original value of the node with the passed in value
node.e = e;
return;
}
}
// According to the last comparison value, judge whether to put it on the left child node or the right child node.
Node<E> nowNode = createNode(e,parent);
if (cmp > 0){
parent.right = nowNode;
}else {
parent.left = nowNode;
}
// Processing after adding nodes
afterAdd(nowNode);
size++;
}
- Rewrite interface: Rewrite createNode interface in AVL tree:
@Override
protected Node<E> createNode(E e, Node<E> parent) {
return new AVLNode<E>(e,parent);
}
- Calculate balance factor: add a new method to calculate balance factor in AVL tree.
/**
* Get balance factor
* @return
*/
public int balanceFactor(){
int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
return leftHeight - rightHeight;
}
2.2.6.2 update normal node height
- Analyze the unbalanced nodes. Because the imbalance is caused by adding nodes, find the parent node with the first imbalance to deal with the imbalance. Therefore, you need to go all the way to find the parent node.
- Judge whether it is balanced
/**
* Judge whether it is balanced
* @param node
* @return
*/
private boolean isBalance(Node<E> node){
return Math.abs(((AVLNode<E>)node).balanceFactor()) <= 1;
}
-
Update height:
① Add a height update method in AVLNode node:/** * Update the height of the current node */ private void updateHeight(){ int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height; int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height; height = 1 + Math.max(leftHeight,rightHeight); }② Method of updating height in outer package
/** * Update node height * @param node */ private void updateHeight(Node<E> node){ ((AVLNode<E>)node).updateHeight(); }
2.2.6.3 restore balance
-
Add a new node in the node class of the binary tree to determine whether it is a left child node or a right child node operation:
/** * Determine whether it is the left subtree of the parent node * @return */ public boolean isLeftChild(){ return parent != null && this == parent.left; } /** * Judge whether it is the right subtree of the parent node * @return */ public boolean isRightChild(){ return parent != null && this == parent.right; }
2.2.6.3.1 left rotation
- RR situation:
- Modify direction
Node<E> parent = grand.right;
parent.right = grand.left;
parent.left = grand;
- Modify parent:
// Update the parent of p to make it the root node of the current subtree
parent.parent = grand.parent;
if (grand.isLeftChild()){
grand.parent.left = parent;
}else if (grand.isRightChild()){
grand.parent.right = parent;
}else { // grand is the root node
root = parent;
}
// Update the parent of p.left
if (grand.right != null){
grand.right.parent = grand;
}
// Update g's parent
grand.parent = parent;
- Update height
// Update height
updateHeight(grand);
updateHeight(parent);
2.2.6.3.2 right rotation
- LL condition:
- Modify direction
Node<E> parent = grand.left;
grand.left = parent.right;
parent.right = grand;
- Update parent
// Update the parent of p to make it the root node of the current subtree
parent.parent = grand.parent;
if (grand.isLeftChild()){
grand.parent.left = parent;
}else if (grand.isRightChild()){
grand.parent.right = parent;
}else { // grand is the root node
root = parent;
}
// Update the parent of p.left
if (grand.left != null){
grand.left.parent = grand;
}
// Update g's parent
grand.parent = parent;
- Update height
// Update height
updateHeight(grand);
updateHeight(parent);
2.2.6.3.3 integration
Since the code of the update part in the left rotation and the right rotation is the same (except that the left or right of the update parent is different), it's better to directly encapsulate it into a method.
/**
* Update parent and height after rotation
* @param grand
* @param parent
* @param child
*/
private void afterRotate(Node<E> grand,Node<E> parent,Node<E> child){
// Update parent
// Update the parent of p to make it the root node of the current subtree
parent.parent = grand.parent;
if (grand.isLeftChild()){
grand.parent.left = parent;
}else if (grand.isRightChild()){
grand.parent.right = parent;
}else { // grand is the root node
root = parent;
}
// Update the parent of p.left
if (child != null){
child.parent = grand;
}
// Update g's parent
grand.parent = parent;
// Update height
updateHeight(grand);
updateHeight(parent);
}
- Left rotation:
/**
* Sinistral
* @param grand
*/
private void rotateLeft(Node<E> grand){
Node<E> parent = grand.right;
Node<E> child = parent.left;
grand.right = child;
parent.left = grand;
afterRotate(grand, parent, child);
}
- Right rotation:
/**
* Dextral
* @param grand
*/
private void rotateRight(Node<E> grand){
Node<E> parent = grand.left;
Node<E> child = parent.right;
grand.left = child;
parent.right = grand;
afterRotate(grand, parent, child);
}
- Consolidated recovery balance approach:
/**
* Restore balance
* @param grand The first (lowest, lowest) node
*/
private void reBalance(Node<E> grand){
// Get the child node with higher node
Node<E> parent = ((AVLNode<E>)grand).tallerChild();
Node<E> node = ((AVLNode<E>)parent).tallerChild();
if (parent.isLeftChild()){ // L
if (node.isLeftChild()){ // LL
rotateRight(grand);
}else { // LR
rotateLeft(parent);
rotateRight(grand);
}
}else { // R
if (node.isLeftChild()){ // RL
rotateRight(parent);
rotateLeft(grand);
}else { // RR
rotateLeft(grand);
}
}
}
- Integrate afterAdd() method
@Override
protected void afterAdd(Node<E> node) {
while (( node = node.parent ) != null){
if (isBalance(node)){
// Update height
// The node here is at least the parent node of the new node
updateHeight(node);
}else {
// Restore balance
// Here is the lowest unbalanced node
reBalance(node);
// Exit loop to restore tree balance
break;
}
}
}
2.2.6.4 unified balance restoration method
As can be seen in the figure, because the binary search tree is orderly, if you restore its balance, you can apply a unified template, just pass in the corresponding nodes.
/**
* Unified restore balance
* @param grand
*/
private void reBalancePro(Node<E> grand){
Node<E> parent = ((AVLNode<E>)grand).tallerChild();
Node<E> node = ((AVLNode<E>)parent).tallerChild();
if (parent.isLeftChild()){ // L
if (node.isLeftChild()){ // LL
rotate(grand,
node.left, node, node.right,
parent,
parent.right, grand, grand.right);
}else { // LR
rotate(grand,
parent.left, parent, node.left,
node,
node.right, grand, grand.right);
}
}else { // R
if (node.isLeftChild()){ // RL
rotate(grand,
grand.left, grand, node.left,
node,
node.right, parent, parent.right);
}else { // RR
rotate(grand,
grand.left, grand, parent.left,
parent,
node.left, node, node.right);
}
}
}
/**
* rotate
* @param r Subtree root node
* @param a
* @param b
* @param c
* @param d
* @param e
* @param f
* @param g
*/
private void rotate(
Node<E> r,
Node<E> a, Node<E> b, Node<E> c,
Node<E> d,
Node<E> e, Node<E> f, Node<E> g){
// Let d be the root node of this subtree
d.parent = r.parent;
if (r.isRightChild()){
r.parent.right = d;
}else if (r.isLeftChild()){
r.parent.left = d;
}else {
root = d;
}
// a b c
b.left = a;
if (a != null){
a.parent = b;
}
b.right = c;
if (c != null){
c.parent = b;
}
// Because the left and right subtrees of b are modified, the height needs to be updated
updateHeight(b);
// e f g
f.left = e;
if (e != null){
e.parent = f;
}
f.right = g;
if (g != null){
g.parent = f;
}
// Because the left and right subtrees of f are modified, the height needs to be updated
updateHeight(f);
// b d f
d.left = b;
b.parent = d;
d.right = f;
f.parent = d;
updateHeight(d);
}
2.2.6.5 testing
-
BST
-
AVL
Delete 2.3
When deleting, only the parent node may be deleted, and other nodes will not be affected.
Delete node 16 as shown in the figure:
After deletion: it will only change the balance factor of its parent node 15 and will not change its height (unless there is only one child node of the deleted node, but this situation will not lead to imbalance). Therefore, it will only cause imbalance of one node in its parent node or ancestor node.
The four cases of deletion are the same as those of addition: however, if the height of the subtree is changed in the process of restoring balance, it may lead to the imbalance of the parent node of the subtree, which may last until the root node. At worst, it may lead to the recovery of O (log n) times.
2.3.1 design interface
- Add in binary search tree:
/**
* The processing after deleting nodes is implemented by subclasses
* @param node
*/
protected void afterRemove(Node<E> node){
}
- In the remove() method, calling afterRemove is called.
/**
* Delete based on incoming nodes
* @param node
*/
private void remove(Node<E> node){
if (node == null){
return;
}
size--;
// The judgment degree is 2
if (node.hasTwoChildren()){
// Get successor node
Node<E> s = successor(node);
// The value of the subsequent node overrides the value of the current node
node.e = s.e;
// Point node to s node
node = s;
}
// Obtain the child node of the deleted node. If the left child node is empty, obtain the right child node;
// If all child nodes are empty, it indicates that the node is a leaf node and returns null.
Node<E> relacement = node.left != null ? node.left : node.right;
if (relacement != null){ // Node is a node with a degree of 1
// Change parent
relacement.parent = node.parent;
// Change the direction of the left (right) of the parent
if (node.parent == null){ // Node is the root node with degree 1.
root = relacement;
}else if (node == node.parent.left){ // The deleted node is the left child of the parent node
node.parent.left = relacement;
} else { // The deleted node is the right child node of the parent node
node.parent.right = relacement;
}
// Process after deletion
afterRemove(node);
}else if(node.parent == null){ // Node is a leaf node and a root node
root = null;
// Process after deletion
afterRemove(node);
}else { //Node is an ordinary leaf node
if (node == node.parent.left){ // The current node is the right child of the parent node
node.parent.left = null;
}else { // Is the left child of the parent node
node.parent.right = null;
}
// Process after deletion
afterRemove(node);
}
}
2.3.2 implementation interface
@Override
protected void afterRemove(Node<E> node) {
while (( node = node.parent ) != null){
if (isBalance(node)){
// Update height
// The node here is at least the parent node of the new node
updateHeight(node);
}else {
// Restore balance
// Here is the lowest unbalanced node
reBalancePro(node);
// You cannot exit after recovery because the parent node may also be out of balance
}
}
}
2.4 summary
- Add: all ancestor nodes may be out of balance. As long as their height is balanced, the whole tree can be balanced.
- Delete: it can only lead to the imbalance of the parent node. Restoring the balance may lead to the imbalance of all ancestor nodes.
- Average complexity:
① Search: O(logn);
② Add: O(logn), which requires O(1) rotation operations at most;
③ Delete: O(logn), which requires up to O(logn) rotation operations.