Personal blog: Shimeng.info

background

I have studied binary search tree BST before. When sequential data is inserted, BST is reduced to a linked list. Therefore, in order to prevent such a situation, some mechanism needs to be introduced, that is, balanced tree. The mechanism of balance gives rise to the concept of balance factor, which is used to represent the balance of a node. For example, if the balance factor of a node is 1, it means that the height difference between the left and right subtrees of the node is 1. The equilibrium factor is defined here as the difference between left and right subtrees.

By definition, if an equilibrium factor is an integer, it means that the left subtree is higher than the right subtree, that is, there are more nodes under the left subtree than the right subtree, because for a balanced subtree, its height is logN of the number of nodes, so it means that the subtree under that node is shifted to the left.

Naturally we know the definition of a balanced tree: a binary tree, for any node, the height difference between the left subtree and the right subtree cannot be more than 1.

The following figure is a balanced tree. Parentheses represent the height value of the node. The height value of the node: the height of the leaf node is 1, and the height of the non-leaf node is the maximum height of the left and right subtrees + 1

                                 (4)15
                                /      \
                            (3)6     (2)18
                             /   \     /
                        (2)2   (1)8  (1)12
                           /
                       (1)1
Copy the code

Therefore, I created a binary tree, and then introduced the balancing mechanism, so I re-implemented a binary tree

Defining a Node object

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null; }}Copy the code

Define the BST constructor

class BST {
  constructor() {
    this.root = null;
    this.size = 0; }}Copy the code

Add a node

push(key, value) {
  this.root = this.insert(this.root, key, value);
}

insert(node, key, value) {
  if(! node) {this.size++;
    return new Node(key, value);
  }

  if (key > node.key) {
    node.right = this.insert(node.right, key, value);
  } else if (key < node.key) {
    node.left = this.insert(node.left, key, value);
  } else {
    node.value = value;
  }

  return node;
}
Copy the code

Find nodes

find(key) {
  const node = this.get(this.root, key);
  return node;
}

get(node, key) {
  if(! node) {return null;
  }

  if (node.key > key) {
    return this.get(node.left, key);
  } else if (node.key < key) {
    return this.get(node.right, key);
  }

  return node;
}
Copy the code

Delete the largest node in a subtree

deleteMax() {
  let max;
  this.root = this._deleteMax(this.root, (node) => max = node);
  return max;
}

_deleteMax(node, cb = (a)= >{{})if(! node) { cb(node);return null;
  }

  if(! node.right) {this.size--;
    cb(node);
    return node.left;
  }

  node.right = this._deleteMax(node.right, cb);
  return node;
}
Copy the code

Delete any node

delete(key) {
  this.root = this._delete(this.root, key);
}
_delete(node, key) {
  if(! node) {return null;
  }

  if (node.key > key) {
    node.left = this._delete(node.left, key);
  } else if (node.key < key) {
    node.right = this._delete(node.right, key);
  } else {
    if(! node.left) {this.size--;
      node = node.right;
    } else if(! node.right) {this.size--;
      node = node.left;
    } else {
      let successor;
      node.left = this.deleteMax(node.left, (node) => { successor = node; }); successor.left = node.left; successor.right = node.right; node = successor; }}return node;
}
Copy the code

For a binary tree, by our definition, it starts out balanced, because there are no left and right children when there is only one node, and the balance factor is 0. Then it goes from equilibrium to imbalance by adding nodes. Knowing this reason, only by enumerating several conditions for the occurrence of this result, can we know specifically how to maintain the balance of a tree.

Unbalance condition

The first kind of

The first one, which is the easiest to understand, is to keep adding nodes to the left subtree, and when you add nodes to the third subtree it’s not balanced

8/4/1Copy the code

At this point, the height of the left subtree of node 8 is 2 and the height of the right subtree is 0, so the balance factor of node 8 is 2

The second,

The second, in contrast, adds nodes all the way to the right of the subtree, which is also unbalanced when added to the third node

8\10\12Copy the code

At this point, the height of the left and right subtrees of node 8 is 2, and the balance factor of node 8 is -2

The third kind of

The third case, slightly different from the first, is in the right subtree of the second node when adding to the third node, as shown in the example

8/4 times 5Copy the code

In this case, the balance factor of node 8 is 2, the difference is that the balance factor of node 4 is -1

A fourth

The fourth case is only slightly different from the second, when the third node is added, in the left subtree of the second node

8\10/9Copy the code

In this case, the balance factor of node 8 is -2 as in the second one, but the difference is that the balance factor of node 10 is 1

Now let’s put all four together

/ \ / \ 4 10 10 / \ / 1 12 2 3 3Copy the code
  • In the case of (1) and (3), the balance factor of node 8 is 2
  • In the case of (2) and (4), the balance factor of node 8 is -2.

That’s just one of the differences, but let’s look at their child nodes.

  • The equilibrium factor of node 4 in (I) is 1
  • The equilibrium factor of node 10 in (2) is -1
  • The balance factor of node 4 in (3) is -1
  • The equilibrium factor of node 10 in (4) is 1.

So these are just the four cases that we found, so there’s one thing that we don’t care about is the children of the root node, which in our case is node 10 and node 4, is it possible that their equilibrium factor is 0?

That’s not even possible here.

Take (1) for example:

If the balance factor of node 4 is 0, it means that the height of the left and right subtrees is equal. In other words, there is a right node before the insertion of left node 1, which is impossible, because if there is a right node, the tree 8 is out of balance at this point, and it will not wait until the insertion of node 1 to maintain the balance

Conclusion is

The serial number The equilibrium factor of the root node The balance factor of the children of the root node
(一) 2 1
(二) 2 – – 1
(三) 2 – 1
(四) 2 – 1

The above is the case where the root node has only one child node. If two children of the same root node exist, are there four other cases that are not considered?

The fifth

8 8 / \ / \ 4 10 => 4 10 / / 2 2/1Copy the code

In this case, we’re going all the way to the left subtree, except that the right node of the root node also exists. At this point, the balance factor of root node 8 is 2, and that of left node 4 is 2

6 kinds of

      8              8/ \ \4   10= >4    10
          \               \
           12             12
                            \
                             14
Copy the code

In this case, you keep adding nodes to the right subtree, and again, root node 8 has a left node. At this time, the balance factor of root node 8 is -2, and that of right node 4 is -2

The 7th kind of

      8              8/ \ \4   10= >4    10
   /                \
  2                  5
                      \
                       7
Copy the code

In this case, nodes are added to the left subtree first and then to the right subtree. At this point, the balance factor of root node 8 is 2, and that of left node 4 is -2

8 kinds of

8 8 / \ / \ 4 11 => 4 11 / / 10 10/9Copy the code

In this case, nodes are added to the right subtree and then to the left subtree. At this time, the balance factor of root node 8 is -2, and that of right node 11 is 2

The four cases from (5) to (8) can be summarized as follows:

The serial number The equilibrium factor of the root node The balance factor of the children of the root node
(五) 2 2
(六) 2 – 2 –
(七) 2 2 –
(八) 2 – 2

It’s also possible that the absolute value of the balance factor of the children of the root node is less than 2

  • (5) Yes, the balance factor of node 4 can also be 1. At this point, node 4 also has two child nodes, which does not affect the balance factor of root node 8.
  • The child node of the root node of (6) can also be -1,
  • The child node of the root node of (7) can be -1,
  • The child node of the root node of (8) can be 1

Now let’s put all eight together

The serial number The equilibrium factor of the root node The balance factor of the children of the root node
(一) 2 1
(二) 2 – – 1
(三) 2 – 1
(四) 2 – 1
(五) 2 2 or 1
(六) 2 – – 2 or 1
(七) 2 – 2 or 1
(八) 2 – 2 or 1

(1) is a special case of (5), (2) is a special case of (6), (3) is a special case of (7), (4) is a special case of (8)

Therefore, we can divide the unbalanced conditions of binary trees into four kinds

  1. The balance factor of the root node is 2, and the balance factor of the children of the root node is > 0
  2. The balance factor of the root node is -2, and the balance factor of the children of the root node is < 0
  3. The balance factor of the root node is 2, and that of the children of the root node is < 0
  4. The balance factor of the root node is -2, and that of the children of the root node is > 0

The operation of maintaining balance

The balance is determined by the balance factor, which is calculated by the height of the Node, so the Node constructor needs to be modified to default height to 1

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1; }}Copy the code

Two more methods are needed, which are to calculate the height of a node and the balance factor

getHeight(node) {
  if(! node)return 0;

  return node.height
}

getBalanceFactory(node) {
  if(! node)return 0;

  return this.getHeight(node.left) - this.getHeight(node.right);
}
Copy the code

According to the above four conditions of imbalance, there are four different ways of maintaining equilibrium

Right rotation RR

At this point, the balance factor of the root node is 2, and the balance factor of the child nodes of the root node is > 0

rightRotate(node) {
  const child = node.left;
  const child_right = child.right;
    
  child.right = node;
  node.left = child_right;
    
  return child;
}

/ / RR right-handed
if (balanceFactory > 1 && this.getBalanceFactory(node.left) > 0) {
  return this.rightRotate(node);
}
Copy the code

Left rotating LL

At this point, the balance factor of the root node is -2, and the balance factor of the child nodes of the root node is < 0

leftRotate(node) {
  const child = node.right;
  const child_left = child.left;

  child.left = node;
  node.right = child_left;

  return child;
}
  
/ / LR left-handed
if (balanceFactory < - 1 && this.getBalanceFactory(node.right) < 0) {
  return this.leftRotate(node);
} 
Copy the code

LRR

At this point, the balance factor of the root node is 2, and the balance factor of the child nodes of the root node is < 0

// LRR left/right rotation
if (balanceFactory > 1 && this.getBalanceFactory(node.left) < 0) {
  node.left = this.leftRotate(node.left);
  return this.rightRotate(node);
}
Copy the code

RLR

// RLR rotates right and left
if (balanceFactory < - 1 && this.getBalanceFactory(node.right) > 0) {
  node.right = this.rightRotate(node.right);
  return this.leftRotate(node);
}
Copy the code

So these are the four ways to maintain balance, which we encapsulate into one

keepBalance(node) {
  if(! node)return node;

  // The balance factor of the current node
  const balanceFactory = this.getBalanceFactory(node);
  
  // The balance factor of the left node
  const leftChildBalanceFactory = this.getBalanceFactory(node.left);
  
  // Balance factor for the right node
  const rightChildBalanceFactory = this.getBalanceFactory(node.right);

  if (Math.abs(balanceFactory) > 1) {
    console.log(`balanceFactory: ${balanceFactory}`);
  }


  / / RR right-handed
  if (balanceFactory > 1 && leftChildBalanceFactory > 0) {
    return this.rightRotate(node);
  }

  / / LR left-handed
  if (balanceFactory < - 1 && rightChildBalanceFactory < 0) {
    return this.leftRotate(node);
  } 

  // LRR left/right rotation
  if (balanceFactory > 1 && leftChildBalanceFactory < 0) {
    node.left = this.leftRotate(node.left);
    return this.rightRotate(node);
  }

  // RLR rotates right and left
  if (balanceFactory < - 1 && rightChildBalanceFactory > 0) {
    node.right = this.rightRotate(node.right);
    return this.leftRotate(node);
  }

  return node;
}
Copy the code

So the add node operation needs to be changed to:

insert(node, key, value) {
  if(! node) {this.size++;
    return new Node(key, value);
  }

  if (key > node.key) {
    node.right = this.insert(node.right, key, value);
  } else if (key < node.key) {
    node.left = this.insert(node.left, key, value);
  } else {
    node.value = value;
  }

  node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;

  return this.keepBalance(node)
}
Copy the code

The delete operation also needs to be modified

_delete(node, key) {
  if(! node) {return null;
  }

  if (node.key > key) {
    node.left = this._delete(node.left, key);
  } else if (node.key < key) {
    node.right = this._delete(node.right, key);
  } else {
    if(! node.left) {this.size--;
      node = node.right;
    } else if(! node.right) {this.size--;
      node = node.left;
    } else {
      let successor;
      node.left = this._deleteMax(node.left, (node) => { successor = node; }); successor.left = node.left; successor.right = node.right; node = successor; }}return this.keepBalance(node);
}

// Delete the maximum value of the subtree
_deleteMax(node, cb = (a)= >{{})if(! node) { cb(node);return null;
  }

  if(! node.right) {this.size--;
    cb(node);
    return node.left;
  }

  node.right = this._deleteMax(node.right, cb);
  return this.keepBalance(node);
}
Copy the code

The above is the content of the entire AVL tree, from the above can also see that the AVL tree is a binary tree, its search, add, delete, in the worst case is O(logN), so more balanced and stable