We learned from the previous article, binary Search Trees, that binary search trees don’t meet our query performance requirements in extreme cases.

Some statistical properties of binary trees

  • The maximum number of nodes at layer n is 2n-1
  • A binary tree of height H contains at most 2h-1 nodes, so the minimum height of a binary tree of n nodes is log2n + 1
  • When the search is successful, the search times will not exceed the height h of the tree

Binary tree query performance measurement

Let’s use the A-H character to see the results of the binary search tree constructed in different insertion orders

The average search length in natural order is ASL=(1+ 2 + 3 + 4+ 5+ 6+ 7 +8) / 8 = 4.5

Calculate the average search length ASL=(1 + 2*2 + 3*4 + 4*1) / 8 = 2.6

When we have the same data, but the insertion order is different, so that the average search length is different. So to solve this problem, we first look at the two initializations and the characteristics of the two trees, and we generally find that the tree that is initialized in a particular order, the distribution of nodes in the tree is more balanced. Due to statistical characteristics 3 and 2, we want the binary tree with n nodes to be close to log2n + 1, so that we can maximize the query performance.

So to solve this problem, we introduce a new binary search tree implementation — balanced binary tree.

AVL tree content definition

  • BalanceFactor: height difference between left and right subtrees BF= Hl-hr
  • The absolute value of the difference in height between the left and right subtrees are not more than 1 | BF | 1 or less

Node definition

Add a height attribute to the original node

class AVLNode<T extends Comparable<T>> { private T data; Private AVLNode<T> left; // Private AVLNode<T> left; Private AVLNode<T> right; Private int height; // Private int height; }Copy the code

Height calculation

Since the balance of a balanced binary tree refers to the balance in terms of height, let’s first calculate the height of the tree

Tree height H indicates the maximum height of the left HL and right HR subtrees + 1

int height(AVLNode<T> node){
    if (Objects.isNull(node)) {
        return 0;
    }
    int rHeight = height(node.getRight());
    int lHeight = height(node.getLeft());
    return Math.max(rHeight, lHeight) + 1;
Copy the code

To find the

Because balanced binary tree is also a kind of binary search tree, the query method is the same as binary search tree, so it is not repeated.

Adjust the balance

In order to ensure the left and right balance, a series of operations are performed to maintain the height of the left and right subtrees within the range specified by BF

Insertion sort

When the tree is empty, the root node is initialized directly.

For an insert that is a child node, the insert node can only be the left node B or right node F of the inserted node. The inserted node D can be the left node of its parent G or the right node of its parent A. So we divide all cases into 4 classes: GDB path (LL insert), GDF path (LR insert), ADF path (RR insert), ADB path (RL insert)

So we’re going to deal with all the cases

Insert the RR

When the insert node is on the right node of the right subtree (ADF path)

Operation steps:

  1. Take the right child node D as the root node
  2. The original root node A is the left child node of the new root node D
  3. Example Set the left child node B of node D as the right child node of the original root node A

The implementation code is as follows:

AVLNode<T> singleRightRotation(AVLNode<T> node) {
    AVLNode<T> result = node.getRight();
    AVLNode<T> left = result.getLeft();
    node.setRight(left);
    result.setLeft(node);
    return result;
}
Copy the code

LL insert

When the inserted node is on the left node of the left subtree (GDB path)

Operation steps:

  1. Take the left child node D as the root node
  2. The original root node G is the right child node of the new root node D
  3. Take the right child node F of D node as the left child node of the original node G

Implementation code:

AVLNode<T> singleLeftRotation(AVLNode<T> node) {
    AVLNode<T> result = node.getLeft();
    AVLNode<T> right = result.getRight();
    node.setLeft(right);
    result.setRight(node);
    return result;
Copy the code

RL insert

When the inserted node is on the left node of the right subtree (ADB path)

Operation steps:

  • The right child node D of node A is rotated left
  • Perform A right rotation for node A

Implementation code:

AVLNode<T> doubleRightLeftRotation(AVLNode<T> node){
    AVLNode<T> right = singleLeftRotation(node.getRight());
    node.setRight(right);
    return singleRightRotation(node);
}
Copy the code

LR insert

When the inserted node is on the left node of the right subtree (GDF path)

Operation steps:

  • Do a right rotation for the left child node D of node G
  • Do a left rotation for the G node

Implementation code:

AVLNode<T> doubleLeftRightRotation(AVLNode<T> node) {
    AVLNode<T> left = singleRightRotation(node.getLeft());
    node.setLeft(left);
    return singleLeftRotation(node);
}
Copy the code

Remove nodes

When we delete a node, we think:

  • The leaf node is deleted directly
  • Contains a child node and replaces the child node with the parent node
  • Contains two child nodes, and replaces the deleted node with a successor node, which can be removed in more detail in the binary Search Tree

After a node is deleted, a new node is inserted into a sibling node

The code is as follows:

return null; } T nodeData = node.getData(); int flag = data.compareTo(nodeData); If (flag > 0) {// right subtree AVLNode<T> right = delete(node.getright (), data); node.setRight(right); AVLNode<T> lNode = node.getLeft(); int rHeight = getHeight(right); int lHeight = getHeight(lNode); int bf = lHeight - rHeight; If (bf == 2) {if (bf == 2) {if (bf == 2) {if (bf == 2) { If the left sibling has a right child node whose height is greater than that of the left child node, rotate it left and right (delete case 2) if (getRightNodeHeight(lNode) > getLeftNodeHeight(lNode)) {node = doubleLeftRightRotation(node); } else {// Node = singleLeftRotation(node); // Node = singleLeftRotation(node); }}} else if (flag < 0) {// left subtree AVLNode<T> left = delete(node.getLeft(), data); node.setLeft(left); AVLNode<T> right = node.getRight(); int lHeight = getHeight(node.getLeft()); int rHeight = getHeight(right); int bf = rHeight - lHeight; If (bf == 2) {if (bf == 2) {if (bf == 2) {if (bf == 2) {if (bf == 2) { If (getLeftNodeHeight(right) > getRightNodeHeight(right)) {node = doubleRightLeftRotation(node); } else {// The left subtree height is less than or equal to the right subtree height, node = singleRightRotation(node); }} else {//found if (objects.nonnull (node.getLeft()) && Objects.nonnull (node.getright ())) {// AVLNode<T> rMin = findMin(node.getRight()); // Replace node.setdata (rmin.getData ()) with the subsequent node; delete(node.getRight(), rMin.getData()); } else {node = objects.isNULL (node.getLeft())? node.getRight() : node.getLeft(); } } if (Objects.nonNull(node)) { buildHeight(node); } return node; }Copy the code

Since AVL is a highly strictly balanced binary search tree, the search efficiency is at the log2n level. However, to maintain the node height balance, rotation operation is required (at most two rotations during insertion; When deleting a node, the AVL tree needs to adjust the height balance of the entire query path, which requires log2n rotations at most.

Later, we will introduce another balanced search binary tree (red-black tree)!

A series of

“Programmer inner power center method — Search binary Tree”

Programmer’s Inner power Method — AVL Tree

Welcome to follow the message to share and I communicate!

Take the future of javascript Art one step at a time, a little bit each day, and time will tell you