Binary tree Sort tree (binary search tree)

  • The left subtrees are all less than the root value
  • The right subnumber is greater than the root value
  • The middle-order traversal is an ascending sort

operation

add

23 -> 10 -> 17

delete

  • Delete controller 6 whose degree is 0

  • Delete controller 10 whose degree is 1

    Hand over the child node to the parent node

  • 💖 Delete a node whose degree is 2
    1. Find the precursor or successor of the current node (the previous or previous node in the middle traversal)
    2. Swap it with the current node value
    3. Delete the precursor node (convert to a node with a deletion degree of 0 or 1)

const Node = function(key) {
  this.key = key
  this.left = null
  this.right = null
}

class BinarySortTree {
  constructor() {
    this.root = null
  }

  preDeccessor(node) {
    let temp = node.left
    while(temp.right) temp = temp.right
    return temp
  }

  inorder(node) {
    if(! node)return
    this.inorder(node.left)
    console.log(node.key)
    this.inorder(node.right)
  }

  output() {
    this.inorder(this.root)
  }

  insertNode(root, key) {
    if(! root) {const newNode = new Node(key)
      return newNode
    }
    if (root.key === key) return root
    if (root.key > key) root.left = this.insertNode(root.left, key)
    else root.right = this.insertNode(root.right, key)
    return root
  }

  deleteNode(root, key) {
    if(! root)return null
    if (root.key > key) {
      root.left = this.deleteNode(root.left, key)
    } else if (root.key < key) {
      root.right = this.deleteNode(root.right, key)
    } else {
      // Degree is 0 or degree is 1
      if(! root.left || ! root.right) {const child = root.left ? root.left : root.right
        return child
      } else {
        const prev = this.preDeccessor(root)
        root.key = prev.key
        root.left = this.deleteNode(root.left, prev.key)
      }
    }
    return root
  }

  add(key) {
    this.root = this.insertNode(this.root, key)
  }

  delete(key) {
    this.root = this.deleteNode(this.root, key)
  }

}
Copy the code

AVL tree

When the left and right subtrees are unbalanced (the height difference between them is greater than 1) when backtracking, adjust

🐱 🐉Examples: 5 9 8 3 2 4 1 7

  • Insert 5,9,8

  • At node 5, RL type imbalance occurs. First, drag 9 for small dextral rotation, and then drag 5 for large left rotation

  • Insert 3,2

  • LL imbalance at node 5, drag 5 to make a big right rotation

  • Insert the 4

  • LR type imbalance at node 8, dragging 3 for small left rotation, and then dragging 8 for large right rotation

  • Insert 1,7