【数据结构-进阶】二叉搜索树

欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。

• 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
• 导航
  • 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
  • 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
  • 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
  • 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
  • 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。 ✨✨ 欢迎订阅本专栏 ✨✨

博客目录

• • 一.介绍
  • • 1.历史
    • 2.特性
    • 3.定义节点
  • 二.常见方法
  • • 1.查询
    • 2.Comparable
    • 3.最小
    • 4.最大
    • 5.新增
    • 6.前驱后继
    • 7.删除
    • 8.找小的
    • 9.找大的
    • 10.找之间
    • 11.小结
  • 三.题目练习
  • • 1.删除节点-力扣 450 题
    • • 1.递归求解
      • 2.迭代求解
    • 2.新增节点-力扣 701 题
    • • 1.递归
      • 2.迭代
    • 3.查询节点-力扣 700 题
    • • 1.递归
      • 2.迭代
    • 4.验证二叉搜索树-力扣 98 题
    • • 1.中序迭代实现
      • 2.中序递归实现
      • 3.上下限递归
    • 5.求范围和-力扣 938 题
    • • 1.中序递归实现
      • 2.中序非递归实现
      • 3.上下限递归实现
    • 6.根据前序遍历构造二叉搜索树-力扣 1008 题
    • • 1.直接插入
      • 2.上限法
      • 3.分治法
      • 4.前序加中序
    • 7.二叉搜索树的最近公共祖先-力扣 235 题
    • • 1.迭代法 one
      • 2.迭代法 two
      • 3.递归法

一.介绍

1.历史

二叉搜索树最早是由 Bernoulli 兄弟在 18 世纪中提出的，但是真正推广和应用该数据结构的是 1960 年代的 D.L. Gries。他的著作《The Science of Programming》中详细介绍了二叉搜索树的实现和应用。

在计算机科学的发展中，二叉搜索树成为了一种非常基础的数据结构，被广泛应用在各种领域，包括搜索、排序、数据库索引等。随着计算机算力的提升和对数据结构的深入研究，二叉搜索树也不断被优化和扩展，例如 AVL 树、红黑树等。

2.特性

二叉搜索树（也称二叉排序树）是符合下面特征的二叉树：

1. 树节点增加 key 属性，用来比较谁大谁小，key 不可以重复
2. 对于任意一个树节点，它的 key 比左子树的 key 都大，同时也比右子树的 key 都小，例如下图所示

轻易看出要查找 7 （从根开始）自然就可应用二分查找算法，只需三次比较

• 与 4 比，较之大，向右找
• 与 6 比，较之大，继续向右找
• 与 7 比，找到

查找的时间复杂度与树高相关，插入、删除也是如此。

• 如果这棵树长得还不赖（左右平衡）上图，那么时间复杂度均是 $O(\log N)$
• 当然，这棵树如果长得丑（左右高度相差过大）下图，那么这时是最糟的情况，时间复杂度是 $O(N)$

注：

• 二叉搜索树 – 英文 binary search tree，简称 BST
• 二叉排序树 – 英文 binary ordered tree 或 binary sorted tree

3.定义节点

static class BSTNode {int key; // 若希望任意类型作为 key, 则后续可以将其设计为 Comparable 接口Object value;BSTNode left;BSTNode right;public BSTNode(int key) {this.key = key;this.value = key;}public BSTNode(int key, Object value) {this.key = key;this.value = value;}public BSTNode(int key, Object value, BSTNode left, BSTNode right) {this.key = key;this.value = value;this.left = left;this.right = right;}}

二.常见方法

1.查询

递归实现

public Object get(int key) {return doGet(root, key);}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; // 找到了}}

非递归实现

public Object get(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;}

2.Comparable

如果希望让除 int 外更多的类型能够作为 key，一种方式是 key 必须实现 Comparable 接口。

public class BSTTree2<T extends Comparable<T>> {static class BSTNode<T> {T key; // 若希望任意类型作为 key, 则后续可以将其设计为 Comparable 接口Object value;BSTNode<T> left;BSTNode<T> right;public BSTNode(T key) {this.key = key;this.value = key;}public BSTNode(T key, Object value) {this.key = key;this.value = value;}public BSTNode(T key, Object value, BSTNode<T> left, BSTNode<T> right) {this.key = key;this.value = value;this.left = left;this.right = right;}}BSTNode<T> root;public Object get(T key) {return doGet(root, key);}private Object doGet(BSTNode<T> node, T key) {if (node == null) {return null;}int result = node.key.compareTo(key);if (result > 0) {return doGet(node.left, key);} else if (result < 0) {return doGet(node.right, key);} else {return node.value;}}}

还有一种做法不要求 key 实现 Comparable 接口，而是在构造 Tree 时把比较规则作为 Comparator 传入，将来比较 key 大小时都调用此 Comparator 进行比较，这种做法可以参考 Java 中的 java.util.TreeMap

3.最小

递归实现

public Object min() {return doMin(root);}public Object doMin(BSTNode node) {if (node == null) {return null;}// 左边已走到头if (node.left == null) {return node.value;}return doMin(node.left);}

非递归实现

public Object min() {if (root == null) {return null;}BSTNode p = root;// 左边未走到头while (p.left != null) {p = p.left;}return p.value;}

4.最大

递归实现

public Object max() {return doMax(root);}public Object doMax(BSTNode node) {if (node == null) {return null;}// 右边已走到头if (node.left == null) {return node.value;}return doMin(node.right);}

非递归实现

public Object max() {if (root == null) {return null;}BSTNode p = root;// 右边未走到头while (p.right != null) {p = p.right;}return p.value;}

5.新增

递归实现

public void put(int key, Object value) {root = doPut(root, key, value);}private BSTNode doPut(BSTNode node, int key, Object value) {if (node == null) {return new BSTNode(key, value);}if (key < node.key) {node.left = doPut(node.left, key, value);} else if (node.key < key) {node.right = doPut(node.right, key, value);} else {node.value = value;}return node;}

• 若找到 key，走 else 更新找到节点的值
• 若没找到 key，走第一个 if，创建并返回新节点
  • 返回的新节点，作为上次递归时 node 的左孩子或右孩子
  • 缺点是，会有很多不必要的赋值操作

非递归实现

public void put(int key, Object value) {BSTNode node = root;BSTNode parent = null;while (node != null) {parent = node;if (key < node.key) {node = node.left;} else if (node.key < key) {node = node.right;} else {// 1. key 存在则更新node.value = value;return;}}// 2. key 不存在则新增if (parent == null) {root = new BSTNode(key, value);} else if (key < parent.key) {parent.left = new BSTNode(key, value);} else {parent.right = new BSTNode(key, value);}}

6.前驱后继

一个节点的前驱（前任）节点是指比它小的节点中，最大的那个

一个节点的后继（后任）节点是指比它大的节点中，最小的那个

例如上图中

• 1 没有前驱，后继是 2
• 2 前驱是 1，后继是 3
• 3 前驱是 2，后继是 4
• …

简单的办法是中序遍历，即可获得排序结果，此时很容易找到前驱后继

要效率更高，需要研究一下规律，找前驱分成 2 种情况：

1. 节点有左子树，此时前驱节点就是左子树的最大值，图中属于这种情况的有
   • 2 的前驱是 1
   • 4 的前驱是 3
   • 6 的前驱是 5
   • 7 的前驱是 6
2. 节点没有左子树，若离它最近的祖先自从左而来，此祖先即为前驱，如
   • 3 的祖先 2 自左而来，前驱 2
   • 5 的祖先 4 自左而来，前驱 4
   • 8 的祖先 7 自左而来，前驱 7
   • 1 没有这样的祖先，前驱 null

找后继也分成 2 种情况

1. 节点有右子树，此时后继节点即为右子树的最小值，如
   • 2 的后继 3
   • 3 的后继 4
   • 5 的后继 6
   • 7 的后继 8
2. 节点没有右子树，若离它最近的祖先自从右而来，此祖先即为后继，如
   • 1 的祖先 2 自右而来，后继 2
   • 4 的祖先 5 自右而来，后继 5
   • 6 的祖先 7 自右而来，后继 7
   • 8 没有这样的祖先，后继 null

public Object predecessor(int key) {BSTNode ancestorFromLeft = null;BSTNode p = root;while (p != null) {if (key < p.key) {p = p.left;} else if (p.key < key) {ancestorFromLeft = p;p = p.right;} else {break;}}if (p == null) {return null;}// 情况1 - 有左孩子if (p.left != null) {return max(p.left);}// 情况2 - 有祖先自左而来return ancestorFromLeft != null " />.value : null;}public Object successor(int key) {BSTNode ancestorFromRight = null;BSTNode p = root;while (p != null) {if (key < p.key) {ancestorFromRight = p;p = p.left;} else if (p.key < key) {p = p.right;} else {break;}}if (p == null) {return null;}// 情况1 - 有右孩子if (p.right != null) {return min(p.right);}// 情况2 - 有祖先自右而来return ancestorFromRight != null ? ancestorFromRight.value : null;}

7.删除

要删除某节点（称为 D），必须先找到被删除节点的父节点，这里称为 Parent

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

非递归实现

/** * 
根据关键字删除
 * * @param key 关键字 * @return 被删除关键字对应值 */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) {shift(parent, p, p.right); // 情况1} else if (p.right == null) {shift(parent, p, p.left); // 情况2} else {// 情况4// 4.1 被删除节点找后继BSTNode s = p.right;BSTNode sParent = p; // 后继父亲while (s.left != null) {sParent = s;s = s.left;}// 4.2 删除和后继不相邻, 处理后继的后事if (sParent != p) {shift(sParent, s, s.right); // 不可能有左孩子s.right = p.right;}// 4.3 后继取代被删除节点shift(parent, p, s);s.left = p.left;}return p.value;}/** * 托孤方法 * * @param parent被删除节点的父亲 * @param deleted 被删除节点 * @param child 被顶上去的节点 */// 只考虑让 n1父亲的左或右孩子指向 n2, n1自己的左或右孩子并未在方法内改变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;}}

递归实现

public Object delete(int key) {ArrayList<Object> result = new ArrayList<>();root = doDelete(root, key, result);return result.isEmpty() ? null : result.get(0);}public BSTNode doDelete(BSTNode node, int key, ArrayList<Object> result) {if (node == null) {return null;}if (key < node.key) {node.left = doDelete(node.left, key, result);return node;}if (node.key < key) {node.right = doDelete(node.right, key, result);return node;}result.add(node.value);if (node.left != null && node.right != null) {BSTNode s = node.right;while (s.left != null) {s = s.left;}s.right = doDelete(node.right, s.key, new ArrayList<>());s.left = node.left;return s;}return node.left != null ? node.left : node.right;}

说明

1. ArrayList