首页 计算机学科 java 数据结构与算法 二叉搜索树

# 二叉搜索树的实现

创建二叉搜索树的结构：

可以把 BSTree1 看作为 java 中的 map 集合他们做的事情都是类似的

// Binary Search Tree 二叉搜索树
public class BSTree1 {
    // 根节点
    BSTNode root;
    // 节点类
    static class BSTNode {
        int key;
        Object value;
        BSTNode left;
        BSTNode right;
        // 根据 key 创建节点的
        public BSTNode(int key) {
            this.key = key;
        }
        // 根据 key-value 创建节点的
        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }
        // 根据 key-value，还有 左右孩子 创建节点的
        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}
# 分析 Get 方法的实现：
# 分析：
image-20240202191145907
通过上图进行分析，通过 根节点 来跟 待查找的 key 进行比较
三成了三种情况：
  1. 如果待查找的 key 小，那就应该从根节点开始向左找
  2. 如果待查找的 key 大，那就应该从根节点开始向右找
  3. 如果 两个 key 相等就是找到了不用找了
# 代码实现：
// 查找关键字对应值
public Object get(int key) {
   // 通过调用该函数使用递归的方式实现的
   // doGet(root, key);
   // 使用非递归的方式实现的
   doGet1(key);
   return null;
}
// 内部使用的 不用暴露给外界 使用递归实现
private Object doGet(BSTNode node, int key) {
   if(node == null) return null;// 没找到
   if(key < node.key)
      return doGet(node.left, key); // 向左找
   else if(node.key < key)
      return doGet(node.right, key); // 向右找
   else
      return node.value; // 找到了
}
// 使用非递归方式实现
private Object doGet1(int key) {
   BSTNode node = root;
   while(node != null) {
      if(key < node.key)
         node = node.left;
      else if(node.key < key)
         node = node.right;
      else
         return node.value;
   }
   return null;
}
# 扩展 key 的类型
我们在实现二叉搜索树的时候他的属性 key 我们采用了 int 类型，为什么使用 int 呢？
就是因为 key 与 key 之间可以进行大小比较，因此我们选择了 int 因为 int 做大小比较非常简单。
那我希望对 key 进行扩展，我希望除了 int 类型意外更多的类型能够作为 key 的类型。
答案是可以的，那我们第一个能想到的就是 泛型了
# 代码实现：
// 二叉搜索树 泛型 key 版本 实现可以大小比较的版本
// 泛型：定义的泛型必须是 Comparable 的 子类型
public class BSTree2<T extends Comparable<T>, V> {
    BSTNode<T, V> root;
    static class BSTNode<T, V> {
        T key;
        V value;
        BSTNode<T, V> left;
        BSTNode<T, V> right;
        public BSTNode(T key) {
            this.key = key;
        }
        public BSTNode(T key, V value) {
            this.key = key;
            this.value = value;
        }
        public BSTNode(T key, V value, BSTNode<T, V> left, BSTNode<T, V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    public Object get(T key) {
        BSTNode<T, V> p = root;
        int result = key.compareTo(p.key);
        if(result < 0)
            p = p.left;
        else if(result > 0)
            p = p.right;
        else
            return p.value;
        return p;
    }
}
# 实现 min 查找最小值 的函数：
# 分析：
我们要找最小关键字，就从 根节点开始 不断向左找，一直走到头那么就是他最小关键字了
image-20240202192500425
image-20240202192624315
# 代码实现：
// 查找最小关键字对应的值
public Object min() {
   return doMin(root);
}
public Object doMin(BSTNode node) {
   if(node == null) return null;// 如果节点为 null 就返回 null
   if(node.left == null) return node.value;// 向左走 知道 节点为 null 说明就是最小值了，因为越往左边的值就越小
   return doMin(node.left);// 不断向左递归
}
# 实现 max 查找最大值的函数：
# 分析：
不断的向右走，走到头就是最大值了
# 代码实现：
// 查找最大关键字对应的值
public Object max() {
   if(root == null) return null;// 如果节点为 null 直接返回 null
   BSTNode p = root;// 定义辅助指针
   while(p.right != null) p = p.right;// 不断向右循环，知道为 null 就停止
   return p.value;// 返回最右边的值 就是 最大值
}
# 实现添加元素 put 函数：
# 分析：
这个 put 函数的功能跟我们已经熟知的 map 中的 put 函数是相似的。
添加时分为两种情况：
  1. 当前的 key 在整个树中已经存在了，有了我们不会新增而是只做一个更新操作。
  2. 当前的 key 在整个树中不存在，那么就新增，找到他合适的位置添加即可
添加流程分析：
image-20240202194010543
比如说，我要添加一个 key 为 1 的节点，先让 1 跟 根节点 进行比较，结果 比 1 根节点 的 key 小
所以继续向左找，让 2 跟 1 作比较，结果 1 还是小
image-20240202194142015
所以继续向左找，让 1 跟 1 比较发现是相同的 ，这表示 这个树中 已经存在 1 了 那么就更新 1 的 value 值即可
image-20240202194219324
如果是 整个树中 不存在 添加 key 的值的情况如下：比如我要添加一个 key 为 9 的值
image-20240202194427098
跟 根节点 比较发现 大了，向右找，跟 8 比较 发现还是大了继续 向右找，8 的右边没有值了 是 null 那么就将 9 添加到 8 节点的 右边即可。
image-20240202194539235
# 代码实现：
// 存储关键字和对应值
public void put(int key, Object value) {
   BSTNode node = root;
   BSTNode parent = null;
   // 经过查找，找到 二叉搜索树中 对应 key　然后修改 key 对应的 value
   while(node != null) {
      parent = node;// 将上次 更新的父节点 存储到 parent 变量中进行保存
      if(key < node.key)// 值小了 向左找
         node = node.left;
      else if(node.key < key)// 值大了 向右找
         node = node.right;
      else {
         // 更新 value
         node.value = value;
         return;
      }
   }
   // 2. key 不存在，需要新增，创建一个新节点，但是考虑二叉搜索树是空的所以我们需要加一条判断
   // new BSTNode(key, value);
   if(parent == null) {
      root = new BSTNode(key, value);
      return;
   }
   // 如果 二叉搜索树不是空的那么就让 新节点找到 适合自己的位置
   if(key < parent.key)// 如果 新节点的 key 比 父节点的 key 小那么就是 父节点的左孩子
      parent = new BSTNode(key, value);
   else if(key > parent.key)// 如果 新节点的 key 比 父节点的 key 大那么就是 父节点的右孩子
      parent = new BSTNode(key, value);
}
# 实现 successor 查找前任值函数：
# 分析：
image-20240203115103106
可以先把二叉搜索树中的所有的 key 排个序，比如说 上图二叉搜索树中 排好序就是：1，2，3，4，5，6，7，8 这样的，排好序后 比如说我要找 4 这个节点的 前任节点，4 前一个 肯定是 3 后一个 肯定是 5
排好序就很容易知道 4 的前任是谁 后任是谁了，那我们这颗 二叉搜索树 怎么排序呢？
其实有一个最简单的方式就是：中序遍历，你可以看下 二叉搜索树 进行中序遍历后的结果就是 升序元素
但是我们实际解决这个问题的时候并不会采用中序遍历，因为中序遍历 性能并不高
我们可以根据下面的规则来高效的找到前任 和 后任：
  1. 节点有左子树，此时前驱节点就是左子树的最大值，图中属于这种情况的有
    1. 2 的前驱是 1
    2. 4 的前驱是 3
    3. 6 的前驱是 5
    4. 7 的前驱是 6
  2. 节点没有左子树，若离它最近的的祖先来从左而来，此祖先即为前驱，如
    1. 3 的祖先 2 自左而来，前驱 2
    2. 5 的祖先 4 自左而来，前驱 4
    3. 8 的祖先 7 自左而来，前驱 7
    4. 1 没有这样的祖先，前驱 null
# 代码实现：
// 查找关键字的前驱值 也就是前任值 比如说 4 那就找 比 4 小 而且有比 其它节点值大的 3 ，如果是 7 那就找 6
public Object successor(int key) {
   BSTNode p = root;
   BSTNode toFrom = null;
   while(p != null) {
      if(key < p.key)
      {
         toFrom = p;
         p = p.left;
      }
      else if(p.key < key)
         p = p.right;
      else
         break;
   }
   // 没找到节点
   if(p == null)
      return null;
   // 找到节点
   if(p.right != null)
      return max(p.right);
   return toFrom != null ? toFrom.value : null;
}
// 查找关键字的后继值 有前任就有后任了 原理与前任是相反的
public Object predecessor(int key) {
   BSTNode p = root;
   while(p != null) {
      if(key < p.key)
         p = p.left;
      else if(p.key < key)
         p = p.right;
      else
         break;
   }
   // 没找到节点
   if(p == null)
      return null;
   // 找到节点
   if(p.left != null)
      return max(p.left);
   return null;
}
# 实现 delete 删除函数：
# 分析：
  1. 删除节点没有左孩子，将右孩子托付给 Parent
  2. 删除节点没有右孩子，将左孩子托付给 Parent
  3. 删除节点左右孩子都没有，已经被涵盖在情况 1，情况 2 当中，把 null 托付给 Parent
  4. 删除节点左右孩子都有，可以将它的后续节点 (称为 S) 托付给 Parent，再称 S 的父亲为 SP，有分两种情况
    1. SP 就是被删除节点，此时 D 与 S 紧邻，只需将 S 托付给 Parent
    2. SP 不是被删除节点，此时 D 与 S 不相邻，此时需要将 S 的后代托付给 SP，再将 S 托付给 Parent
# 代码实现：
// 根据关键字删除
public Object delete(int key) {
   BSTNode p = root;
   BSTNode parent = null;
   while (p != null) {
      if (key < p.key) {
         parent = p;
         p = p.left;
      }else if (p.key < key) {
         parent = p;
         p = p.right;
      }else {
         break;
      }
   }
   if (p == null) {
      return null;
   }
   if (p.left == null) {
      // 情况 1
      shift(parent, p, p.right);
   }else if (p.right == null) {
      // 情况 2
      shift(parent, p, p.left);
   }else {
      // 情况 4
      BSTNode s = p.right;
      BSTNode sParent = p;
      while (s.left != null) {
         sParent = s;
         s = s.left;
      }
      if (sParent != p) {
         shift(sParent, s, s.right);
      }
      shift(parent, p, s);
      s.left = p.left;
   }
   return p.value;
}
// 托付方法
private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
   if (parent == null) {
      root = child;
   }else if (deleted == parent.left) {
      parent.left = child;
   }else {
      parent.right = child;
   }
}
# 递归版：
private BSTNode doDelete(BSTNode node, int key, ArrayList<Object> arrayList) {
   if (node == null) {
      return null;
   }
   if (key < node.key) {
      node.left = doDelete(node.left, key, arrayList);
      return node;
   }
   if (node.key < key) {
      node.right  = doDelete(node.right, key, arrayList);
      return node;
   }
   arrayList.add(node.value);
   if (node.left == null) {
      return node.right;
   }
   if (node.right == null) {
      return node.left;
   }
   BSTNode s = node.right;
   while (s.left != null) {
      s = s.left;
   }
   s.right = doDelete(node.right, key, arrayList);
   s.left = node.left;
   return s;
}
public Object delete1(int key) {
   ArrayList<Object> arrayList = new ArrayList<>();// 保存被删除节点的值
   root = doDelete(root, key, arrayList);
   return arrayList.isEmpty() ? null : arrayList.get(0);
}
# 实现 范围 查询函数：
# 分析：
三个函数，第一个 给一个 key 返回 比这个 key 小的值，第二个 给一个 key 返回 比这个 key 大的值，第三个 给两个 key 返回 这两个 key 区间的值
对于二叉搜索树来讲，中序遍历就能得到 升序 结果，我们在中序遍历的过程中，加入一些条件
# 实现 小于 key 的查找函数：
public List<Object> less(int key) {
   ArrayList<Object> result = new ArrayList<>();
   BSTNode p = root;
   LinkedList<BSTNode> stack = new LinkedList<>();
   while (p != null || !stack.isEmpty()) {
      if (p != null) {
         stack.push(p);
         p = p.left;
      }else {
         BSTNode pop = stack.pop();
         if (pop.key < key) {
            result.add(pop.value);
         }else {
            break;
         }
         p = pop.right;
      }
   }
   return result;
}
# 实现 大于 key 的查找函数：
public List<Object> greater(int key) {
   ArrayList<Object> result = new ArrayList<>();
   BSTNode p = root;
   LinkedList<BSTNode> stack = new LinkedList<>();
   while (p != null || !stack.isEmpty()) {
      if (p != null) {
         stack.push(p);
         p = p.left;
      }else {
         BSTNode pop = stack.pop();
         if (pop.key > key) {
            result.add(pop.value);
         }else {
            break;
         }
         p = pop.right;
      }
   }
   return result;
}
# 实现 查找 key1 到 key2 之间的值函数：
public List<Object> between(int key1, int key2) {
   ArrayList<Object> result = new ArrayList<>();
   BSTNode p = root;
   LinkedList<BSTNode> stack = new LinkedList<>();
   while (p != null || !stack.isEmpty()) {
      if (p != null) {
         stack.push(p);
         p = p.left;
      }else {
         BSTNode pop = stack.pop();
         if (pop.key > key1 && pop.key <= key2) {
            result.add(pop.value);
         }else if (pop.key > key2) {
            break;
         }
         p = pop.right;
      }
   }
   return result;
}