Balanced binary sort tree

Binary sort tree

Binary sorting tree is also called binary search tree, binary search tree properties: 1, the left subtree is smaller than the root node 2, the right subtree is larger than the root node Purpose: to solve the search requirements related to ranking

Binary sort tree delete operation

  • Leaf node: can be deleted directly
  • If the output degree is 1, the unique subtree of the node is promoted after deletion
  • The degree is 2: find the precursor or successor of the deleted node, and the degree of the precursor or successor node must be 1 or 0. Assign the precursor or successor node to the deleted node, and then delete the precursor or successor node to convert the problem into the above two problems

Balanced binary sort tree

In order to prevent the binary sorting tree from degenerated into a linked list, the search efficiency directly changes to O(n), so the balance nature of the left and right subtrees of the binary sorting tree should be maintained: the height difference between the left and right subtrees is no more than 1. LL type, left subtree height imbalance, left subtree height greater than right subtree RR type, right subtree height imbalance, right subtree height greater than left subtree LR type, left subtree height imbalance, right subtree height greater than left subtree RL type, right subtree height imbalance, The left subtree of the right subtree is higher than the right subtree of the right subtree

Balance scheme: LL type, large dextral rotation


LR, a little left rotation, turn the problem into LL, then a big right rotation

RL and RR imbalance can be adjusted symmetrically

Handrip balanced binary sort tree

// Set up virtual nodes, which can easily handle boundary cases
let NIL = {left: null.right: null.h: 0}
class Node {
    constructor(val) {
        this.val = val
        this.left = this.right = NIL
        this.h = 1}}// Insert operations
function insert(root, val) {
    if (root == NIL) return new Node(val)
    if (val < root.val) {
        root.left = insert(root.left, val)
    } else {
        root.right = insert(root.right, val)
    }
    update_height(root)
    root = maintain(root)
    return root
}
// Delete operation
function delNode(root, val) {
    if (root == NIL) return root
    if (val < root.val) root.left = delNode(root.left, val)
    else if (val > root.val) root.right = delNode(root.right, val)
    else {
        if (root.left == NIL || root.right == NIL) {
            let temp = root.left == NIL ? root.right : root.left
            delete root
            return temp
        } else {
            let temp = getPreNode(root)
            root.val = temp.val
            root.left = delNode(root.left, temp.val)
        }
    }
    update_height(root)
    root = maintain(root)
    return root
}
// Get the precursor node
function getPreNode(root) {
    let temp = root.left
    while(temp.right ! = NIL) temp = temp.rightreturn temp
}
// Update the node height
function update_height(root) {
    if (root.left == NIL || root.right == NIL) {
        let temp = root.left == NIL ? root.right : root.left
        root.h = temp.h + 1
    } else {
        root.h = Math.max(root.left.h, root.right.h) + 1}}// Balance adjustment
function maintain(root) {
    if (Math.abs(root.left.h - root.right.h) < 2) return root
    if (root.left.h > root.right.h) { / / L
        if (root.left.right.h > root.left.left.h) { / / LR type
            root.left = left_rotate(root.left)
        }
        root = right_rotate(root) / / LL type
    } else {   / / R type
        if (root.right.left.h > root.right.right.h) { / / RL type
            root.right = right_rotate(root.right)
        }
        root = left_rotate(root) / / RR type
    }
    return root
}
/ / left
function left_rotate(root) {
    let new_root = root.right
    root.right = new_root.left
    new_root.left = root
    update_height(root)
    update_height(new_root)
    return new_root
}
/ / right
function right_rotate(root) {
    let new_root = root.left
    root.left = new_root.right
    new_root.right = root
    update_height(root)
    update_height(new_root)
    return new_root
}
// middle order traversal
function in_order(root, buff) {
    if (root == NIL) return
    in_order(root.left, buff)
    buff.push(root.val)
    in_order(root.right, buff)
}
Copy the code

LeetCode liver problem

  1. Interview question 04.06. Successors
// Define a pre node to hold the previous value. If pre == p, root is the required successor node
var inorderSuccessor = function(root, p) {
    let pre = new TreeNode(null), ans = null
    let inorder = function(root) {
        if(! root)return root
        inorder(root.left)
        if (pre.val == p.val) {
            ans = root
            pre = root
            return
        }
        pre = root
        inorder(root.right)
    }
    inorder(root)
    return ans
};
Copy the code
    1. Delete a node in the binary search tree
If the node has only one subtree or no subtree, delete the current node and return the subtree
// If there are two subtrees, you need to find the precursor or successor of the node, change the value of the node to the value of the precursor, and then go to the left subtree to delete the precursor node
var getPreNode = function(root) {
    let temp = root.left
    while(temp.right) temp = temp.right
    return temp
}
var deleteNode = function(root, key) {
    if(! root)return root
    if (key < root.val) root.left = deleteNode(root.left, key)
    else if (key > root.val) root.right = deleteNode(root.right, key)
    else {
        if(! root.left || ! root.right) {let temp = root.left ? root.left : root.right
            delete root
            return temp
        } else {
            let temp = getPreNode(root)
            root.val = temp.val
            root.left = deleteNode(root.left, root.val)
        }
    }
    return root
};
Copy the code
    1. The binary search tree is balanced
// The binary search tree is a balanced binary sort tree by traversing the order into a sorted array and assembling the number as close as possible to the middle node as the root node
var balanceBST = function(root) {
    let arr = []
    let inorder = (root) = > {
        if(! root)return root
        inorder(root.left)
        arr.push(root)
        inorder(root.right)
    }
    let buildTree = (arr, i, j) = > {
        if (i > j) return null
        let mid = (i + j) >> 1
        let root = arr[mid]
        root.left = buildTree(arr, i, mid - 1)
        root.right = buildTree(arr, mid + 1, j)
        return root
    }
    inorder(root)
    return buildTree(arr, 0, arr.length - 1)};Copy the code
    1. Converts an ordered array to a binary search tree
// As above, use the median as the root node
var sortedArrayToBST = function(nums) {
    let buildTree = (nums, i, j) = > {
        if (i > j) return null
        let mid = (i + j) >> 1
        let root = new TreeNode(nums[mid])
        root.left = buildTree(nums, i, mid - 1)
        root.right = buildTree(nums, mid + 1, j)
        return root
    }
    return buildTree(nums, 0, nums.length - 1)};Copy the code
    1. Verify the binary search tree
// The middle order is traversed to see if it is ascending
var isValidBST = function(root) {
    let pre, flag = true
    let inorder = (root) = > {
        if(! root)return root
        inorder(root.left)
        if (pre && pre.val >= root.val) {
            flag = false
            return
        }
        pre = root
        inorder(root.right)
    }
    inorder(root)
    return flag
};
// Structured thinking
var isValidBST = function(root) {
    let pre
    let inorder = (root) = > {
        if(! root)return true
        if(! inorder(root.left))return false
        if (pre && pre.val >= root.val) return false
        pre = root
        if(! inorder(root.right))return false
        return true
    }
    return inorder(root)
};
Copy the code
    1. Mode in a binary search tree
If the value is equal to, add the node to the ANS array. If the value is greater than, empty the ANS array. Add the node value and update the maximum number
var findMode = function(root) {
    let ans = [], cut = 0, vis = {}, dfs = (root) = > {
        if(! root)return
        vis[root.val] = vis[root.val] ? vis[root.val] + 1 : 1
        if (vis[root.val] == cut) ans.push(root.val)
        if (vis[root.val] > cut) {
            ans.length = 0
            cut = vis[root.val]
            ans.push(root.val)
        }
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    return ans
};
Copy the code
  1. Question 17.12. BiNode
// Change the right pointer from the leftmost node and set left to NULL
var convertBiNode = function(root) {
    if(! root)return root
    let pre, head, inorder = (root) = > {
        if(! root)return root
        inorder(root.left)
        if (pre) {
            pre.right = root
        } else head = root
        root.left = null
        pre = root
        inorder(root.right)
    }
    inorder(root)
    return head
};
Copy the code
  1. Offer 33. Post-order traversal sequence of binary search tree
// The following traversal sequence is regarded as a binary search tree, and the interval of the left and right subtrees can be recursively traversed to obtain the middle-order traversal result, and the r position is the root node position
var verifyPostorder = function(postorder) {
    let pre = -1, inorder = (nums, l, r) = > {
        if (l > r) return true
        let ind = l
        while(nums[ind] < nums[r]) ind++
        if(! inorder(nums, l, ind -1)) return false
        if(pre ! = -1 && nums[r] < nums[pre]) return false
        pre = r
        if(! inorder(nums, ind, r -1)) return false
        return true
    }
    return inorder(postorder, 0, postorder.length - 1)};Copy the code
    1. Foreorder traversal constructs binary search tree
// Binary search tree construction process, smaller values in the left subtree, larger values in the right subtree
let insert = (root, val) = > {
    if(! root)return new TreeNode(val)
    if (val < root.val) root.left = insert(root.left, val)
    else root.right = insert(root.right, val)
    return root
}
var bstFromPreorder = function(preorder) {
    let root = null
    for(let i = 0; i < preorder.length; i++) {
        root = insert(root, preorder[i])
    }
    return root
};
Copy the code
    1. The number of nodes in a complete binary tree
// Give the recursive function an explicit meaning: query the number of nodes in the complete binary tree
var countNodes = function(root) {
    if(! root)return 0
    // Number of nodes = number of left subtrees + number of right subtrees + 1
    return countNodes(root.left) + countNodes(root.right) + 1
};
Copy the code
  1. The value of the right subtree is always greater than the root node, and the value of the left subtree is always less than the root node. Therefore, the middle-order traversal result of the binary search tree is an ordered array
// Get the result of the preceding traversal
var inorder = function(root, ans) {
    if(! root)return
    root.left && inorder(root.left,ans)
    ans.push(root.val)
    root.right && inorder(root.right,ans)
}
var kthLargest = function(root, k) {
    let ans = []
    inorder(root, ans)
    return ans[ans.length -k]
};
Copy the code
  1. Offer 26. Substructure of tree
// Give recursive functions an explicit meaning: are trees A and B exactly the same
var is_match = function(A, B) {
    if (B == null) return true  // If the B tree is empty, it means the same
    if (A == null) return false  // If A tree is empty, it is not the same
    if(A.val ! = B.val)return false  // If the values are not equal, they are not the same
    return is_match(A.left, B.left) && is_match(A.right, B.right)    // Compare the left and right subtrees
}
// Give the recursive function an explicit meaning: is B tree A subtree
var isSubStructure = function(A, B) {
    if (A == null) return false
    if (B == null) return false
    if (A.val == B.val && is_match(A, B)) return true    // If the current values are equal and both trees are the same, return true
    return isSubStructure(A.left, B) || isSubStructure(A.right, B)    Otherwise, compare the left subtree of A with B or the right subtree of A with B recursively
};
Copy the code
    1. Maximum width of binary tree
The root node is I, the left subtree is 2i, and the right subtree is 2i+1
var widthOfBinaryTree = function(root) {
    if(! root)return 0
    // Define a maximum value and a two-dimensional array that holds the numbers and nodes of each layer
    let max = 1, que = [[0, root]]
    while(que.length) {
        let smaller = que[0] [0], bigger = que[que.length - 1] [0]
        max = Math.max(max, bigger - smaller + 1)
        let arr = []
        for (const [index, item] of que) {
            // The ordinal of the left subtree can be equivalent to (ordinal of the parent node - minimum ordinal of the parent node layer) *2
            // The ordinal of the right subtree can be equivalent to (ordinal of the parent node - minimum ordinal of the parent node layer) *2 + 1
            item.left && arr.push([2*(index - smaller), item.left])
            item.right && arr.push([2*(index - smaller)+1, item.right])
        }
        que = arr
    }
    return max
};
Copy the code