算法学习——二叉搜索树基础

这是我参与更文挑战的第27天，活动详情查看：更文挑战

二叉搜索树简介

二叉搜索树（BST）是二叉树的一种特殊表示形式，它满足如下特性：

• 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
• 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

二叉搜索树中的搜索操作

根据BST的特性，对于每个节点

• 如果目标值与节点的值相等，则返回该节点
• 如果目标值小于节点的值，则继续搜索节点的左子树
• 如果目标值大于节点的值，则继续搜索节点的右子树
• 搜索过程类似于二分查找，时间复杂度为O(n)，n为树的高度

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || val == root.val) return root;
        return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
    }
}
复制代码

二叉搜索树中的插入操作

经典算法（最简单的算法，不考虑树的高度，只考虑节点的位置是否符合二叉搜索树的特性）

• 根据节点值与目标节点值的关系，搜索左子树或右子树；
• 重复步骤 1 直到到达外部节点；
• 根据节点的值与目标节点的值的关系，将新节点添加为其左侧或右侧的子节点。
• 时间复杂度分析，如果插入过程是插入有序的队列，整棵树会退化为列表（每个节点都只有左子树或都只有右子树），每一次插入复杂度为O(n),n为当前树的高度。插入n个数的时间复杂度为O(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;
                }
            }
        }
        return root;
    }
}
复制代码

二叉搜索树的删除操作

经典算法

• 如果目标节点没有子节点，我们可以直接移除该目标节点。
• 如果目标节只有一个子节点，我们可以用其子节点作为替换。
• 如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。

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);
      }
    }
    return root;
  }
}
复制代码