In computer science, AVL tree is the first self-balanced binary search tree invented. The maximum difference in height between two subtrees of any node in an AVL tree is 1, so it is also called a height balanced tree. Additions and deletions may require one or more tree rotations to rebalance the tree. The AVL tree takes its name from its inventors g. M. Adelson-Velsky and E. M. Landis, who published it in their 1962 paper An Algorithm for the Organization of Information.

preface

The front-end algorithm series is a record of my algorithm learning, which mainly analyzes the learning algorithm knowledge from common algorithms, data structure, algorithm thinking and common skills. It realizes deliberate practice through LeetCode platform, and practices Feynman learning method through digging gold and the output of STATION B. I will update the quality content and synchronously update it to Nuggets, B station and Github in the future, so as to record the complete process of learning algorithm. Welcome to communicate, like and collect more, let us make progress together, daydayUp 👊

Directory address: directory section

Code address: Github

Bilibili – 100 days algorithm series

(1) AVL tree – Foundation

Previous: [Luffy] front-end algorithm – data structure (three, tree): binary search tree

One, the origin

In the last section we learned about binary search trees and learned that their main properties are:

• The left subtree is always smaller than the root node
• The right subtree is always larger than the root

So let’s see what a binary search tree looks like if we initialize it with the following data.

// [1, 2, 3, 4, 5]
Copy the code

We know that binary search tree has two important functions, one of which is that it can reduce the time complexity of our search to O(logn). However, when our initial object is an ordered array, the binary search tree degrades to the state of linked list and loses its O(logn) time complexity

In order to prevent binary search tree from degenerating into linked list state, AVL tree was born

The AVL tree itself is still a binary search tree, but it will be adjusted every time the insertion operation is performed, so that the height difference between the left and right subtrees is no more than 1, that is to say, the AVL tree is a binary search tree with balanced function

Second, the nature of the

1. Left subtree < root node

2. Right subtree > root node

3, | left subtree is highly – right subtree is highly | < = 1 ❗ ️ ❗ ️ ❗ ️

Three advantages,

In addition to the advantages of binary trees, the biggest advantage of AVL trees is that the height of the tree is limited, so that it will not degrade the linked list

Fourth, adjust the

1. AVL tree – left-handed

2. AVL tree – Dextral

3. AVL tree – imbalance type

Red triangles represent subtrees whose height exceeds the limit

(2) AVL tree – implementation

/ / left
function rotateLeft(root) {
    let temp = root.right
    root.right = temp.left
    temp.left = root
    updateHeight(root)
    updateHeight(temp)
    return temp
}

/ / right
function rotateRight(root) {
    let temp = root.left
    root.left = temp.right
    temp.right = root
    updateHeight(root)
    updateHeight(temp)
    return temp
}

function maintain(root) {
    // No need to adjust
    if (Math.abs(root.left.h - root.right.h) <= 1) return root
    if (root.left.h > root.right) {
        // The left subtree is higher and the imbalance condition is L
        if (root.left.right.h > root.left.left.h) {
            // LR imbalance, first left, then right
            root.left = rotateLeft(root.right)
        }
        // LL imbalance, dextral
        root = rotateRight(root)
    } else {
        // The right subtree is higher, and the imbalance condition is R
        if (root.right.left.h > root.right.right.h) {
            // RL imbalance, first right, then left
            root.right = rotateRight(root.right)
        }
        // RR imbalance, left rotation
        root = rotateLeft(root)
    }
    return root
}

// Then you need to modify the root returned on insert and delete in the original binary tree code as follows
Copy the code

This is the binary search tree code from our previous chapter

// constructor
function Node(val, left, right) {
    this.val = val || 0
    this.left = left || null
    this.right = right || null
    this.height = 0 / / tree height
}

/ / create
Node.prototype.getNewNode = function (val) {
    let p = new Node(val)
    p.height = 1
    return p
}

/ / insert
Node.prototype.insert = function (root, target) {
    if (root === null) return this.getNewNode(target)
    if (root.val === target) return root
    if (root.val > target) {
        root.left = this.insert(root.left, target)
    } else {
        root.right = this.insert(root.right, target)
    }
    updateHeight(root)
    // return root
    // This is modified
    return maintain(root)
}

/ / delete
Node.prototype.earse = function (root, target) {
    if (root === null) return root
    if (root.val > target) {
        root.left = this.earse(root.left, target)
    } else if (root.val < target) {
        root.right = this.earse(root.right, target)
    } else {
        if(! root.left && ! root.right) {// The output degree is 0
            return null
        } else if(! root.left || ! root.right) {// The output degree is 1
            return root.left || root.right
        } else { // The output degree is 2
            // Get the precursor, replace it, delete it
            let pre = this.getPre(root.left)
            root.val = pre.val
            // fix: Delete the precursor node in the left subtree
            root.left = this.earse(root.left, root.val)
        }
    }
    // return root
    // This is modified
    return maintain(root)
}

/ / clean up
Node.prototype.clear = function (root) {
    if (root === null) return
    this.clear(root.left)
    this.clear(root.right)
    return
}

// Get the precursor
Node.prototype.getPre = function (root) {
    let temp = root
    while(temp.right) {
        temp = temp.right
    }
    return temp
}

// Update the tree height
function updateHeight(root) {
    root.height = Math.max(root.left.height, root.right.height) + 1
}
Copy the code