This is the 27th day of my participation in Gwen Challenge

An introduction to binary search trees

Binary search tree (BST) is a special representation of binary tree, which meets the following characteristics:

  • The value in each node must be greater than (or equal to) any value stored in its left subtree.
  • The value in each node must be less than (or equal to) any value stored in its right subtree.

Search operations in a binary search tree

According to the BST nature, for each node

  • Returns the node if the target value is equal to its value
  • If the target value is less than the value of the node, the search continues for the left subtree of the node
  • If the target value is greater than the value of the node, the search continues for the right subtree of the node
  • The search process is similar to binary search and the time complexity is O(n), where n is the height of the tree
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || val == root.val) return root;
        returnval < root.val ? searchBST(root.left, val) : searchBST(root.right, val); }}Copy the code

Insert operations in binary search trees

Classical algorithm (the simplest algorithm, not considering the height of the tree, only consider whether the position of the node is consistent with the characteristics of binary search tree)

  • Search left or right subtree according to the relationship between node value and target node value.
  • Repeat Step 1 until the external node is reached;
  • Add a new node as a child node to its left or right, depending on the relationship between the node’s value and the target node’s value.
  • Time complexity analysis shows that if the insertion process is to insert an ordered queue, the whole tree will degenerate into a list (each node has only a left subtree or a right subtree), and the complexity of each insertion is O(n), where n is the height of the current tree. The time for inserting n numbers is order n log n.
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while(pos ! =null) {
            if (val < pos.val) {
                if (pos.left == null) {
                    pos.left = new TreeNode(val);
                    break;
                } else{ pos = pos.left; }}else {
                if (pos.right == null) {
                    pos.right = new TreeNode(val);
                    break;
                } else{ pos = pos.right; }}}returnroot; }}Copy the code

Delete operation of binary search tree

Classic algorithms

  • If the target node has no children, we can simply remove the target node.
  • If the target section has only one child node, we can substitute the child node.
  • If the target node has two child nodes, we need to replace them with sequential successor nodes or precursor nodes and then delete the target node.

class Solution {

  public int successor(TreeNode root) {
    root = root.right;
    while(root.left ! =null) root = root.left;
    return root.val;
  }

  public int predecessor(TreeNode root) {
    root = root.left;
    while(root.right ! =null) root = root.right;
    return root.val;
  }

  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
      return null;
    }
    
    if (key > root.val) {
      root.right = deleteNode(root.right, key);
    }else if (key < root.val) {
      root.left = deleteNode(root.left, key);
    }else {
      if (root.left == null && root.right == null) {
        root = null;
      }else if(root.right ! =null) {
        root.val = successor(root);
        root.right = deleteNode(root.right, root.val);
      }else{ root.val = predecessor(root); root.left = deleteNode(root.left, root.val); }}returnroot; }}Copy the code