一. 基础算法

查找算法

不管是之前学过的数组、链表、队列、还是栈，这些线性结构中，如果想在其中查找一个元素，效率是比较慢的，只有数据结构与算法2 - 图1#card=math&code=O%28N%29&id=JBz49)，因此如果你的需求是实现快速查找，那么就需要新的算法设计，也需要新的数据结构支持。

还记得最先介绍的那个二分查找算法吗？它的查找效率能够达到 数据结构与算法2 - 图2#card=math&code=O%28%5Clog%7BN%7D%29&id=uhX5l)，是不是还不错？不过呢，它需要对数组事先排好序，而排序的成本是比较高的。那么有没有一个折中的办法呢？有，那就是接下来要给大家介绍的二叉搜索树

1. 二叉搜索树

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

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

数据结构与算法2 - 图3

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

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

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

  • 如果这棵树长得还不赖（左右平衡）上图，那么时间复杂度均是 数据结构与算法2 - 图4#card=math&code=O%28%5Clog%7BN%7D%29&id=HxmMf)
  • 当然，这棵树如果长得丑（左右高度相差过大）下图，那么这时是最糟的情况，时间复杂度是 数据结构与算法2 - 图5#card=math&code=O%28N%29&id=A5W1z)

数据结构与算法2 - 图6

注：

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

定义节点

  1. static class BSTNode {
  2.     int key; // 若希望任意类型作为 key, 则后续可以将其设计为 Comparable 接口
  3.     Object value;
  4.     BSTNode left;
  5.     BSTNode right;
  7.     public BSTNode(int key) {
  8.         this.key = key;
  9.         this.value = key;
  10.     }
  12.     public BSTNode(int key, Object value) {
  13.         this.key = key;
  14.         this.value = value;
  15.     }
  17.     public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
  18.         this.key = key;
  19.         this.value = value;
  20.         this.left = left;
  21.         this.right = right;
  22.     }
  23. }

查询

递归实现

  1. public Object get(int key) {
  2.     return doGet(root, key);
  3. }
  5. private Object doGet(BSTNode node, int key) {
  6.     if (node == null) {
  7.         return null; // 没找到
  8.     }
  9.     if (key < node.key) {
  10.         return doGet(node.left, key); // 向左找
  11.     } else if (node.key < key) {
  12.         return doGet(node.right, key); // 向右找
  13.     } else {
  14.         return node.value; // 找到了
  15.     }
  16. }

非递归实现

  1. public Object get(int key) {
  2.     BSTNode node = root;
  3.     while (node != null) {
  4.         if (key < node.key) {
  5.             node = node.left;
  6.         } else if (node.key < key) {
  7.             node = node.right;
  8.         } else {
  9.             return node.value;
  10.         }
  11.     }
  12.     return null;
  13. }

Comparable

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

  1. public class BSTTree2<T extends Comparable<T>> {
  2.     static class BSTNode<T> {
  3.         T key; // 若希望任意类型作为 key, 则后续可以将其设计为 Comparable 接口
  4.         Object value;
  5.         BSTNode<T> left;
  6.         BSTNode<T> right;
  8.         public BSTNode(T key) {
  9.             this.key = key;
  10.             this.value = key;
  11.         }
  13.         public BSTNode(T key, Object value) {
  14.             this.key = key;
  15.             this.value = value;
  16.         }
  18.         public BSTNode(T key, Object value, BSTNode<T> left, BSTNode<T> right) {
  19.             this.key = key;
  20.             this.value = value;
  21.             this.left = left;
  22.             this.right = right;
  23.         }
  24.     }
  26.     BSTNode<T> root;
  28.     public Object get(T key) {
  29.         return doGet(root, key);
  30.     }
  32.     private Object doGet(BSTNode<T> node, T key) {
  33.         if (node == null) {
  34.             return null;
  35.         }
  36.         int result = node.key.compareTo(key);
  37.         if (result > 0) {
  38.             return doGet(node.left, key);
  39.         } else if (result < 0) {
  40.             return doGet(node.right, key);
  41.         } else {
  42.             return node.value;
  43.         }
  44.     }
  46. }

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

最小

递归实现

  1. public Object min() {
  2.     return doMin(root);
  3. }
  5. public Object doMin(BSTNode node) {
  6.     if (node == null) {
  7.         return null;
  8.     }
  9.     // 左边已走到头
  10.     if (node.left == null) { 
  11.         return node.value;
  12.     }
  13.     return doMin(node.left);
  14. }

非递归实现

  1. public Object min() {
  2.     if (root == null) {
  3.         return null;
  4.     }
  5.     BSTNode p = root;
  6.     // 左边未走到头
  7.     while (p.left != null) {
  8.         p = p.left;
  9.     }
  10.     return p.value;
  11. }

最大

递归实现

  1. public Object max() {
  2.     return doMax(root);
  3. }
  5. public Object doMax(BSTNode node) {
  6.     if (node == null) {
  7.         return null;
  8.     }
  9.     // 右边已走到头
  10.     if (node.left == null) { 
  11.         return node.value;
  12.     }
  13.     return doMin(node.right);
  14. }

非递归实现

  1. public Object max() {
  2.     if (root == null) {
  3.         return null;
  4.     }
  5.     BSTNode p = root;
  6.     // 右边未走到头
  7.     while (p.right != null) {
  8.         p = p.right;
  9.     }
  10.     return p.value;
  11. }

新增

递归实现

  1. public void put(int key, Object value) {
  2.     root = doPut(root, key, value);
  3. }
  5. private BSTNode doPut(BSTNode node, int key, Object value) {
  6.     if (node == null) {
  7.         return new BSTNode(key, value);
  8.     }
  9.     if (key < node.key) {
  10.         node.left = doPut(node.left, key, value);
  11.     } else if (node.key < key) {
  12.         node.right = doPut(node.right, key, value);
  13.     } else {
  14.         node.value = value;
  15.     }
  16.     return node;
  17. }
  • 若找到 key，走 else 更新找到节点的值
  • 若没找到 key，走第一个 if，创建并返回新节点
    • 返回的新节点，作为上次递归时 node 的左孩子或右孩子
    • 缺点是，会有很多不必要的赋值操作

非递归实现

  1. public void put(int key, Object value) {
  2.     BSTNode node = root;
  3.     BSTNode parent = null;
  4.     while (node != null) {
  5.         parent = node;
  6.         if (key < node.key) {
  7.             node = node.left;
  8.         } else if (node.key < key) {
  9.             node = node.right;
  10.         } else {
  11.             // 1. key 存在则更新
  12.             node.value = value;
  13.             return;
  14.         }
  15.     }
  16.     // 2. key 不存在则新增
  17.     if (parent == null) {
  18.         root = new BSTNode(key, value);
  19.     } else if (key < parent.key) {
  20.         parent.left = new BSTNode(key, value);
  21.     } else {
  22.         parent.right = new BSTNode(key, value);
  23.     }
  24. }

前驱后继

数据结构与算法2 - 图7

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

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

例如上图中

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

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

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

数据结构与算法2 - 图8

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

找后继也分成 2 种情况

数据结构与算法2 - 图9

  1. 节点有右子树，此时后继节点即为右子树的最小值，如
    • 2 的后继 3
    • 3 的后继 4
    • 5 的后继 6
    • 7 的后继 8
  2. 节点没有右子树，若离它最近的祖先自从右而来，此祖先即为后继，如
    • 1 的祖先 2 自右而来，后继 2
    • 4 的祖先 5 自右而来，后继 5
    • 6 的祖先 7 自右而来，后继 7
    • 8 没有这样的祖先，后继 null
  1. public Object predecessor(int key) {
  2.     BSTNode ancestorFromLeft = null;
  3.     BSTNode p = root;
  4.     while (p != null) {
  5.         if (key < p.key) {
  6.             p = p.left;
  7.         } else if (p.key < key) {
  8.             ancestorFromLeft = p;
  9.             p = p.right;
  10.         } else {
  11.             break;
  12.         }
  13.     }
  15.     if (p == null) {
  16.         return null;
  17.     }
  18.     // 情况1 - 有左孩子
  19.     if (p.left != null) {
  20.         return max(p.left);
  21.     }
  22.     // 情况2 - 有祖先自左而来
  23.     return ancestorFromLeft != null ? ancestorFromLeft.value : null;
  24. }
  27. public Object successor(int key) {
  28.     BSTNode ancestorFromRight = null;
  29.     BSTNode p = root;
  30.     while (p != null) {
  31.         if (key < p.key) {
  32.             ancestorFromRight = p;
  33.             p = p.left;
  34.         } else if (p.key < key) {
  35.             p = p.right;
  36.         } else {
  37.             break;
  38.         }
  39.     }
  41.     if (p == null) {
  42.         return null;
  43.     }
  44.     // 情况1 - 有右孩子
  45.     if (p.right != null) {
  46.         return min(p.right);
  47.     }
  48.     // 情况2 - 有祖先自右而来
  49.     return ancestorFromRight != null ? ancestorFromRight.value : null;
  50. }

删除

要删除某节点（称为 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

非递归实现

  1. /**
  2.  * <h3>根据关键字删除</h3>
  3.  *
  4.  * @param key 关键字
  5.  * @return 被删除关键字对应值
  6.  */
  7. public Object delete(int key) {
  8.     BSTNode p = root;
  9.     BSTNode parent = null;
  10.     while (p != null) {
  11.         if (key < p.key) {
  12.             parent = p;
  13.             p = p.left;
  14.         } else if (p.key < key) {
  15.             parent = p;
  16.             p = p.right;
  17.         } else {
  18.             break;
  19.         }
  20.     }
  21.     if (p == null) {
  22.         return null;
  23.     }
  24.     // 删除操作
  25.     if (p.left == null) {
  26.         shift(parent, p, p.right); // 情况1
  27.     } else if (p.right == null) {
  28.         shift(parent, p, p.left); // 情况2
  29.     } else {
  30.         // 情况4
  31.         // 4.1 被删除节点找后继
  32.         BSTNode s = p.right;
  33.         BSTNode sParent = p; // 后继父亲
  34.         while (s.left != null) {
  35.             sParent = s;
  36.             s = s.left;
  37.         }
  38.         // 4.2 删除和后继不相邻, 处理后继的后事
  39.         if (sParent != p) {                
  40.             shift(sParent, s, s.right); // 不可能有左孩子
  41.             s.right = p.right;
  42.         }
  43.         // 4.3 后继取代被删除节点
  44.         shift(parent, p, s);
  45.         s.left = p.left;
  46.     }
  47.     return p.value;
  48. }
  50. /**
  51.  * 托孤方法
  52.  *
  53.  * @param parent  被删除节点的父亲
  54.  * @param deleted 被删除节点
  55.  * @param child   被顶上去的节点
  56.  */
  57. // 只考虑让 n1父亲的左或右孩子指向 n2, n1自己的左或右孩子并未在方法内改变
  58. private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
  59.     if (parent == null) {
  60.         root = child;
  61.     } else if (deleted == parent.left) {
  62.         parent.left = child;
  63.     } else {
  64.         parent.right = child;
  65.     }
  66. }

递归实现

  1. public Object delete(int key) {
  2.     ArrayList<Object> result = new ArrayList<>();
  3.     root = doDelete(root, key, result);
  4.     return result.isEmpty() ? null : result.get(0);
  5. }
  7. public BSTNode doDelete(BSTNode node, int key, ArrayList<Object> result) {
  8.     if (node == null) {
  9.         return null;
  10.     }
  11.     if (key < node.key) {
  12.         node.left = doDelete(node.left, key, result);
  13.         return node;
  14.     }
  15.     if (node.key < key) {
  16.         node.right = doDelete(node.right, key, result);
  17.         return node;
  18.     }
  19.     result.add(node.value);
  20.     if (node.left != null && node.right != null) {
  21.         BSTNode s = node.right;
  22.         while (s.left != null) {
  23.             s = s.left;
  24.         }
  25.         s.right = doDelete(node.right, s.key, new ArrayList<>());
  26.         s.left = node.left;
  27.         return s;
  28.     }
  29.     return node.left != null ? node.left : node.right;
  30. }

说明

  1. ArrayList<Object> result 用来保存被删除节点的值
  2. 第二、第三个 if 对应没找到的情况，继续递归查找和删除，注意后续的 doDelete 返回值代表删剩下的，因此需要更新
  3. 最后一个 return 对应删除节点只有一个孩子的情况，返回那个不为空的孩子，待删节点自己因没有返回而被删除
  4. 第四个 if 对应删除节点有两个孩子的情况，此时需要找到后继节点，并在待删除节点的右子树中删掉后继节点，最后用后继节点替代掉待删除节点返回，别忘了改变后继节点的左右指针

找小的

  1. public List<Object> less(int key) {
  2.     ArrayList<Object> result = new ArrayList<>();
  3.     BSTNode p = root;
  4.     LinkedList<BSTNode> stack = new LinkedList<>();
  5.     while (p != null || !stack.isEmpty()) {
  6.         if (p != null) {
  7.             stack.push(p);
  8.             p = p.left;
  9.         } else {
  10.             BSTNode pop = stack.pop();
  11.             if (pop.key < key) {
  12.                 result.add(pop.value);
  13.             } else {
  14.                 break;
  15.             }
  16.             p = pop.right;
  17.         }
  18.     }
  19.     return result;
  20. }

找大的

  1. public List<Object> greater(int key) {
  2.     ArrayList<Object> result = new ArrayList<>();
  3.     BSTNode p = root;
  4.     LinkedList<BSTNode> stack = new LinkedList<>();
  5.     while (p != null || !stack.isEmpty()) {
  6.         if (p != null) {
  7.             stack.push(p);
  8.             p = p.left;
  9.         } else {
  10.             BSTNode pop = stack.pop();
  11.             if (pop.key > key) {
  12.                 result.add(pop.value);
  13.             }
  14.             p = pop.right;
  15.         }
  16.     }
  17.     return result;
  18. }

但这样效率不高，可以用 RNL 遍历

注：

  • Pre-order, NLR
  • In-order, LNR
  • Post-order, LRN
  • Reverse pre-order, NRL
  • Reverse in-order, RNL
  • Reverse post-order, RLN
  1. public List<Object> greater(int key) {
  2.     ArrayList<Object> result = new ArrayList<>();
  3.     BSTNode p = root;
  4.     LinkedList<BSTNode> stack = new LinkedList<>();
  5.     while (p != null || !stack.isEmpty()) {
  6.         if (p != null) {
  7.             stack.push(p);
  8.             p = p.right;
  9.         } else {
  10.             BSTNode pop = stack.pop();
  11.             if (pop.key > key) {
  12.                 result.add(pop.value);
  13.             } else {
  14.                 break;
  15.             }
  16.             p = pop.left;
  17.         }
  18.     }
  19.     return result;
  20. }

找之间

  1. public List<Object> between(int key1, int key2) {
  2.     ArrayList<Object> result = new ArrayList<>();
  3.     BSTNode p = root;
  4.     LinkedList<BSTNode> stack = new LinkedList<>();
  5.     while (p != null || !stack.isEmpty()) {
  6.         if (p != null) {
  7.             stack.push(p);
  8.             p = p.left;
  9.         } else {
  10.             BSTNode pop = stack.pop();
  11.             if (pop.key >= key1 && pop.key <= key2) {
  12.                 result.add(pop.value);
  13.             } else if (pop.key > key2) {
  14.                 break;
  15.             }
  16.             p = pop.right;
  17.         }
  18.     }
  19.     return result;
  20. }

2. AVL 树

前面介绍过，如果一棵二叉搜索树长的不平衡，那么查询的效率会受到影响，如下图

数据结构与算法2 - 图10

通过旋转可以让树重新变得平衡，并且不会改变二叉搜索树的性质（即左边仍然小，右边仍然大）

数据结构与算法2 - 图11

如何判断失衡？

如果一个节点的左右孩子，高度差超过 1，则此节点失衡，才需要旋转

处理高度

如何得到节点高度？一种方式之前做过的一道题目：E05. 求二叉树的最大深度（高度），但由于求高度是一个非常频繁的操作，因此将高度作为节点的一个属性，将来新增或删除时及时更新，默认为 1（按力扣说法）

  1. static class AVLNode {
  2.     int height = 1;
  3.     int key;
  4.     Object value;
  5.     AVLNode left;
  6.     AVLNode right;
  7.     // ...
  8. }

求高度代码

这里加入了 height 函数方便求节点为 null 时的高度

  1. private int height(AVLNode node) {
  2.     return node == null ? 0 : node.height;
  3. }

更新高度代码

将来新增、删除、旋转时，高度都可能发生变化，需要更新。下面是更新高度的代码

  1. private void updateHeight(AVLNode node) {
  2.     node.height = Integer.max(height(node.left), height(node.right)) + 1;
  3. }

何时触发失衡判断？

定义平衡因子（balance factor）如下

数据结构与算法2 - 图12

当平衡因子

  • bf = 0，1，-1 时，表示左右平衡
  • bf > 1 时，表示左边太高
  • bf < -1 时，表示右边太高

对应代码

  1. private int bf(AVLNode node) {
  2.     return height(node.left) - height(node.right);
  3. }

当插入新节点，或删除节点时，引起高度变化时，例如

数据结构与算法2 - 图13

目前此树平衡，当再插入一个 4 时，节点们的高度都产生了相应的变化，8 节点失衡了

数据结构与算法2 - 图14

在比如说，下面这棵树一开始也是平衡的

数据结构与算法2 - 图15

当删除节点 8 时，节点们的高度都产生了相应的变化，6 节点失衡了

数据结构与算法2 - 图16

失衡的四种情况

LL

数据结构与算法2 - 图17

  • 失衡节点（图中 8 红色）的 bf > 1，即左边更高
  • 失衡节点的左孩子（图中 6）的 bf >= 0 即左孩子这边也是左边更高或等高

LR

数据结构与算法2 - 图18

  • 失衡节点（图中 8）的 bf > 1，即左边更高
  • 失衡节点的左孩子（图中 6 红色）的 bf < 0 即左孩子这边是右边更高

对称的还有两种情况

RL

数据结构与算法2 - 图19

  • 失衡节点（图中 3）的 bf <-1，即右边更高
  • 失衡节点的右孩子（图中 6 红色）的 bf > 0，即右孩子这边左边更高

RR

数据结构与算法2 - 图20

  • 失衡节点（图中 3）的 bf <-1，即右边更高
  • 失衡节点的右孩子（图中 6 红色）的 bf <= 0，即右孩子这边右边更高或等高

解决失衡

失衡可以通过树的旋转解决。什么是树的旋转呢？它是在不干扰元素顺序的情况下更改结构，通常用来让树的高度变得平衡。

观察下面一棵二叉搜索树，可以看到，旋转后，并未改变树的左小右大特性，但根、父、孩子节点都发生了变化

  1.       4                                   2
  2.      / \             4 right             / \
  3.     2   5      -------------------->    1   4
  4.    / \         <--------------------       / \
  5.   1   3              2 left               3   5

右旋

旋转前

数据结构与算法2 - 图21

  • 红色节点，旧根（失衡节点）
  • 黄色节点，旧根的左孩子，将来作为新根，旧根是它右孩子
  • 绿色节点，新根的右孩子，将来要换爹作为旧根的左孩子

旋转后

数据结构与算法2 - 图22

代码

  1. private AVLNode rightRotate(AVLNode red) {
  2.     AVLNode yellow = red.left;
  3.     AVLNode green = yellow.right;
  4.     yellow.right = red;
  5.     red.left = green;
  6.     return yellow;
  7. }

左旋

旋转前

数据结构与算法2 - 图23

  • 红色节点，旧根（失衡节点）
  • 黄色节点，旧根的右孩子，将来作为新根，旧根是它左孩子
  • 绿色节点，新根的左孩子，将来要换爹作为旧根的右孩子

旋转后

数据结构与算法2 - 图24

代码

  1. private AVLNode leftRotate(AVLNode red) {
  2.     AVLNode yellow = red.right;
  3.     AVLNode green = yellow.left;
  4.     yellow.left = red;
  5.     red.right = green;
  6.     return yellow;
  7. }

左右旋

指先左旋左子树，再右旋根节点（失衡），这时一次旋转并不能解决失衡

数据结构与算法2 - 图25

左子树旋转后

数据结构与算法2 - 图26

根右旋前

数据结构与算法2 - 图27

根右旋后

数据结构与算法2 - 图28

代码

  1. private AVLNode leftRightRotate(AVLNode root) {
  2.     root.left = leftRotate(root.left);
  3.     return rightRotate(root);
  4. }

右左旋

指先右旋右子树，再左旋根节点（失衡）

数据结构与算法2 - 图29

右子树右旋后

数据结构与算法2 - 图30

根左旋前

数据结构与算法2 - 图31

根左旋后

数据结构与算法2 - 图32

代码

  1. private AVLNode rightLeftRotate(AVLNode root) {
  2.     root.right = rightRotate(root.right);
  3.     return leftRotate(root);
  4. }

判断及调整平衡代码

  1. private AVLNode balance(AVLNode node) {
  2.     if (node == null) {
  3.         return null;
  4.     }
  5.     int bf = bf(node);
  6.     if (bf > 1 && bf(node.left) >= 0) {
  7.         return rightRotate(node);
  8.     } else if (bf > 1 && bf(node.left) < 0) {
  9.         return rightLeftRotate(node);
  10.     } else if (bf < -1 && bf(node.right) > 0) {
  11.         return leftRightRotate(node);
  12.     } else if (bf < -1 && bf(node.right) <= 0) {
  13.         return rightRotate(node);
  14.     }
  15.     return node;
  16. }

以上四种旋转代码里，都需要更新高度，需要更新的节点是红色、黄色，而绿色节点高度不变

新增

  1. public void put(int key, Object value) {
  2.     root = doPut(root, key, value);
  3. }
  5. private AVLNode doPut(AVLNode node, int key, Object value) {
  6.     if (node == null) {
  7.         return new AVLNode(key, value);
  8.     }
  9.     if (key == node.key) {
  10.         node.value = value;
  11.         return node;
  12.     }
  13.     if (key < node.key) {
  14.         node.left = doPut(node.left, key, value);
  15.     } else {
  16.         node.right = doPut(node.right, key, value);
  17.     }
  18.     updateHeight(node);
  19.     return balance(node);
  20. }

删除

  1. public void remove(int key) {
  2.     root = doRemove(root, key);
  3. }
  5. private AVLNode doRemove(AVLNode node, int key) {
  6.     if (node == null) {
  7.         return null;
  8.     }
  9.     if (key < node.key) {
  10.         node.left = doRemove(node.left, key);
  11.     } else if (node.key < key) {
  12.         node.right = doRemove(node.right, key);
  13.     } else {
  14.         if (node.left == null) {
  15.             node = node.right;
  16.         } else if (node.right == null) {
  17.             node = node.left;
  18.         } else {
  19.             AVLNode s = node.right;
  20.             while (s.left != null) {
  21.                 s = s.left;
  22.             }
  23.             s.right = doRemove(node.right, s.key);
  24.             s.left = node.left;
  25.             node = s;
  26.         }
  27.     }
  28.     if (node == null) {
  29.         return null;
  30.     }
  31.     updateHeight(node);
  32.     return balance(node);
  33. }

完整代码备份

  1. public class AVLTree {
  2.     static class AVLNode {
  3.         int height = 1;
  4.         int key;
  5.         Object value;
  6.         AVLNode left;
  7.         AVLNode right;
  9.         public AVLNode(int key) {
  10.             this.key = key;
  11.         }
  13.         public AVLNode(int key, Object value) {
  14.             this.key = key;
  15.             this.value = value;
  16.         }
  18.         public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
  19.             this.key = key;
  20.             this.value = value;
  21.             this.left = left;
  22.             this.right = right;
  23.         }
  24.     }
  26.     AVLNode root;
  28.     private AVLNode leftRotate(AVLNode p) {
  29.         AVLNode r = p.right;
  30.         AVLNode b = r.left;
  31.         r.left = p;
  32.         p.right = b;
  33.         updateHeight(p);
  34.         updateHeight(r);
  35.         return r;
  36.     }
  38.     private void updateHeight(AVLNode node) {
  39.         node.height = Integer.max(height(node.left), height(node.right)) + 1;
  40.     }
  42.     private AVLNode rightRotate(AVLNode r) {
  43.         AVLNode a = r.left;
  44.         AVLNode b = a.right;
  45.         a.right = r;
  46.         r.left = b;
  47.         updateHeight(r);
  48.         updateHeight(a);
  49.         return a;
  50.     }
  52.     private AVLNode leftRightRotate(AVLNode p) {
  53.         AVLNode r = p.left;
  54.         p.left = leftRotate(r);
  55.         return rightRotate(p);
  56.     }
  58.     private AVLNode rightLeftRotate(AVLNode p) {
  59.         AVLNode r = p.right;
  60.         p.right = rightRotate(r);
  61.         return leftRotate(p);
  62.     }
  64.     private int height(AVLNode node) {
  65.         return node == null ? 0 : node.height;
  66.     }
  70.     public void remove(int key) {
  71.         root = doRemove(root, key);
  72.     }
  74.     private AVLNode doRemove(AVLNode node, int key) {
  75.         if (node == null) {
  76.             return null;
  77.         }
  78.         if (key < node.key) {
  79.             node.left = doRemove(node.left, key);
  80.         } else if (node.key < key) {
  81.             node.right = doRemove(node.right, key);
  82.         } else {
  83.             if (node.left == null) {
  84.                 node = node.right;
  85.             } else if (node.right == null) {
  86.                 node = node.left;
  87.             } else {
  88.                 AVLNode s = node.right;
  89.                 while (s.left != null) {
  90.                     s = s.left;
  91.                 }
  92.                 s.right = doRemove(node.right, s.key);
  93.                 s.left = node.left;
  94.                 node = s;
  95.             }
  96.         }
  97.         if (node == null) {
  98.             return null;
  99.         }
  100.         updateHeight(node);
  101.         return balance(node);
  102.     }
  104.     public void put(int key, Object value) {
  105.         root = doPut(root, key, value);
  106.     }
  108.     private AVLNode doPut(AVLNode node, int key, Object value) {
  109.         if (node == null) {
  110.             return new AVLNode(key, value);
  111.         }
  112.         if (key == node.key) {
  113.             node.value = value;
  114.             return node;
  115.         }
  116.         if (key < node.key) {
  117.             node.left = doPut(node.left, key, value);
  118.         } else {
  119.             node.right = doPut(node.right, key, value);
  120.         }
  121.         updateHeight(node);
  122.         return balance(node);
  123.     }
  125.     private int bf(AVLNode node) {
  126.         return height(node.left) - height(node.right);
  127.     }
  129.     private AVLNode balance(AVLNode node) {
  130.         if (node == null) {
  131.             return null;
  132.         }
  133.         int bf = bf(node);
  134.         if (bf > 1 && bf(node.left) >= 0) {
  135.             return rightRotate(node);
  136.         } else if (bf > 1 && bf(node.left) < 0) {
  137.             return rightLeftRotate(node);
  138.         } else if (bf < -1 && bf(node.right) > 0) {
  139.             return leftRightRotate(node);
  140.         } else if (bf < -1 && bf(node.right) <= 0) {
  141.             return rightRotate(node);
  142.         }
  143.         return node;
  144.     }
  145. }

3. 红黑树

红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少

红黑树特性

  1. 所有节点都有两种颜色：红与黑
  2. 所有 null 视为黑色
  3. 红色节点不能相邻
  4. 根节点是黑色
  5. 从根到任意一个叶子节点，路径中的黑色节点数一样（黑色完美平衡）

插入情况

插入节点均视为红色数据结构与算法2 - 图33

case 1：插入节点为根节点，将根节点变黑数据结构与算法2 - 图34

case 2：插入节点的父亲若为黑色数据结构与算法2 - 图35，树的红黑性质不变，无需调整

插入节点的父亲为红色数据结构与算法2 - 图36，触发红红相邻

case 3：叔叔为红色数据结构与算法2 - 图37

  • 父亲变为黑色数据结构与算法2 - 图38，为了保证黑色平衡，连带的叔叔也变为黑色数据结构与算法2 - 图39
  • 祖父如果是黑色不变，会造成这颗子树黑色过多，因此祖父节点变为红色数据结构与算法2 - 图40
  • 祖父如果变成红色，可能会接着触发红红相邻，因此对将祖父进行递归调整

case 4：叔叔为黑色数据结构与算法2 - 图41

  1. 父亲为左孩子，插入节点也是左孩子，此时即 LL 不平衡
    • 让父亲变黑数据结构与算法2 - 图42，为了保证这颗子树黑色不变，将祖父变成红数据结构与算法2 - 图43，但叔叔子树少了一个黑色
    • 祖父右旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
  2. 父亲为左孩子，插入节点是右孩子，此时即 LR 不平衡
    • 父亲左旋，变成 LL 情况，按 1. 来后续处理
  3. 父亲为右孩子，插入节点也是右孩子，此时即 RR 不平衡
    • 让父亲变黑数据结构与算法2 - 图44，为了保证这颗子树黑色不变，将祖父变成红数据结构与算法2 - 图45，但叔叔子树少了一个黑色
    • 祖父左旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
  4. 父亲为右孩子，插入节点是左孩子，此时即 RL 不平衡
    • 父亲右旋，变成 RR 情况，按 3. 来后续处理

删除情况

case0：如果删除节点有两个孩子

  • 交换删除节点和后继节点的 key，value，递归删除后继节点，直到该节点没有孩子或只剩一个孩子

如果删除节点没有孩子或只剩一个孩子

case 1：删的是根节点

  • 删完了，直接将 root = null
  • 用剩余节点替换了根节点的 key，value，根节点孩子 = null，颜色保持黑色数据结构与算法2 - 图46不变

删黑色会失衡，删红色不会失衡，但删黑色有一种简单情况

case 2：删的是黑数据结构与算法2 - 图47，剩下的是红数据结构与算法2 - 图48，剩下这个红节点变黑数据结构与算法2 - 图49

删除节点和剩下节点都是黑数据结构与算法2 - 图50，触发双黑，双黑意思是，少了一个黑

case 3：被调整节点的兄弟为红数据结构与算法2 - 图51，此时两个侄子定为黑 数据结构与算法2 - 图52

  • 删除节点是左孩子，父亲左旋
  • 删除节点是右孩子，父亲右旋
  • 父亲和兄弟要变色，保证旋转后颜色平衡
  • 旋转的目的是让黑侄子变为删除节点的黑兄弟，对删除节点再次递归，进入 case 4 或 case 5

case 4：被调整节点的兄弟为黑数据结构与算法2 - 图53，两个侄子都为黑 数据结构与算法2 - 图54

  • 将兄弟变红数据结构与算法2 - 图55，目的是将删除节点和兄弟那边的黑色高度同时减少 1
  • 如果父亲是红数据结构与算法2 - 图56，则需将父亲变为黑，避免红红，此时路径黑节点数目不变
  • 如果父亲是黑数据结构与算法2 - 图57，说明这条路径还是少黑，再次让父节点触发双黑

case 5：被调整节点的兄弟为黑 数据结构与算法2 - 图58，至少一个红数据结构与算法2 - 图59侄子

  • 如果兄弟是左孩子，左侄子是红数据结构与算法2 - 图60，LL 不平衡
    • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑数据结构与算法2 - 图61，平衡起见，左侄子也是黑数据结构与算法2 - 图62
    • 原来兄弟要成为父亲，需要保留父亲颜色
  • 如果兄弟是左孩子，右侄子是红数据结构与算法2 - 图63，LR 不平衡
    • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑数据结构与算法2 - 图64
    • 右侄子会取代原来父亲，因此它保留父亲颜色
    • 兄弟已经是黑了数据结构与算法2 - 图65，无需改变
  • 如果兄弟是右孩子，右侄子是红数据结构与算法2 - 图66，RR 不平衡
    • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑数据结构与算法2 - 图67，平衡起见，右侄子也是黑数据结构与算法2 - 图68
    • 原来兄弟要成为父亲，需要保留父亲颜色
  • 如果兄弟是右孩子，左侄子是红数据结构与算法2 - 图69，RL 不平衡
    • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑数据结构与算法2 - 图70
    • 左侄子会取代原来父亲，因此它保留父亲颜色
    • 兄弟已经是黑了数据结构与算法2 - 图71，无需改变

完整代码

  1. package com.itheima.datastructure.redblacktree;
  3. import static com.itheima.datastructure.redblacktree.RedBlackTree.Color.BLACK;
  4. import static com.itheima.datastructure.redblacktree.RedBlackTree.Color.RED;
  6. /**
  7.  * <h3>红黑树</h3>
  8.  */
  9. public class RedBlackTree {
  11.     enum Color {
  12.         RED, BLACK;
  13.     }
  15.     Node root;
  17.     static class Node {
  18.         int key;
  19.         Object value;
  20.         Node left;
  21.         Node right;
  22.         Node parent;        // 父节点
  23.         Color color = RED;  // 颜色
  25.         public Node(int key, Object value) {
  26.             this.key = key;
  27.             this.value = value;
  28.         }
  30.         public Node(int key) {
  31.             this.key = key;
  32.         }
  34.         public Node(int key, Color color) {
  35.             this.key = key;
  36.             this.color = color;
  37.         }
  39.         public Node(int key, Color color, Node left, Node right) {
  40.             this.key = key;
  41.             this.color = color;
  42.             this.left = left;
  43.             this.right = right;
  44.             if (left != null) {
  45.                 left.parent = this;
  46.             }
  47.             if (right != null) {
  48.                 right.parent = this;
  49.             }
  50.         }
  52.         // 是否是左孩子
  53.         boolean isLeftChild() {
  54.             return parent != null && parent.left == this;
  55.         }
  57.         // 叔叔
  58.         Node uncle() {
  59.             if (parent == null || parent.parent == null) {
  60.                 return null;
  61.             }
  62.             if (parent.isLeftChild()) {
  63.                 return parent.parent.right;
  64.             } else {
  65.                 return parent.parent.left;
  66.             }
  67.         }
  69.         // 兄弟
  70.         Node sibling() {
  71.             if (parent == null) {
  72.                 return null;
  73.             }
  74.             if (this.isLeftChild()) {
  75.                 return parent.right;
  76.             } else {
  77.                 return parent.left;
  78.             }
  79.         }
  80.     }
  82.     // 判断红
  83.     boolean isRed(Node node) {
  84.         return node != null && node.color == RED;
  85.     }
  87.     // 判断黑
  88.     boolean isBlack(Node node) {
  89. //        return !isRed(node);
  90.         return node == null || node.color == BLACK;
  91.     }
  93.     // 右旋 1. parent 的处理 2. 旋转后新根的父子关系
  94.     private void rightRotate(Node pink) {
  95.         Node parent = pink.parent;
  96.         Node yellow = pink.left;
  97.         Node green = yellow.right;
  98.         if (green != null) {
  99.             green.parent = pink;
  100.         }
  101.         yellow.right = pink;
  102.         yellow.parent = parent;
  103.         pink.left = green;
  104.         pink.parent = yellow;
  105.         if (parent == null) {
  106.             root = yellow;
  107.         } else if (parent.left == pink) {
  108.             parent.left = yellow;
  109.         } else {
  110.             parent.right = yellow;
  111.         }
  112.     }
  114.     // 左旋
  115.     private void leftRotate(Node pink) {
  116.         Node parent = pink.parent;
  117.         Node yellow = pink.right;
  118.         Node green = yellow.left;
  119.         if (green != null) {
  120.             green.parent = pink;
  121.         }
  122.         yellow.left = pink;
  123.         yellow.parent = parent;
  124.         pink.right = green;
  125.         pink.parent = yellow;
  126.         if (parent == null) {
  127.             root = yellow;
  128.         } else if (parent.left == pink) {
  129.             parent.left = yellow;
  130.         } else {
  131.             parent.right = yellow;
  132.         }
  133.     }
  135.     /**
  136.      * 新增或更新
  137.      * <br>
  138.      * 正常增、遇到红红不平衡进行调整
  139.      *
  140.      * @param key   键
  141.      * @param value 值
  142.      */
  143.     public void put(int key, Object value) {
  144.         Node p = root;
  145.         Node parent = null;
  146.         while (p != null) {
  147.             parent = p;
  148.             if (key < p.key) {
  149.                 p = p.left;
  150.             } else if (p.key < key) {
  151.                 p = p.right;
  152.             } else {
  153.                 p.value = value; // 更新
  154.                 return;
  155.             }
  156.         }
  157.         Node inserted = new Node(key, value);
  158.         if (parent == null) {
  159.             root = inserted;
  160.         } else if (key < parent.key) {
  161.             parent.left = inserted;
  162.             inserted.parent = parent;
  163.         } else {
  164.             parent.right = inserted;
  165.             inserted.parent = parent;
  166.         }
  167.         fixRedRed(inserted);
  168.     }
  170.     void fixRedRed(Node x) {
  171.         // case 1 插入节点是根节点，变黑即可
  172.         if (x == root) {
  173.             x.color = BLACK;
  174.             return;
  175.         }
  176.         // case 2 插入节点父亲是黑色，无需调整
  177.         if (isBlack(x.parent)) {
  178.             return;
  179.         }
  180.         /* case 3 当红红相邻，叔叔为红时
  181.             需要将父亲、叔叔变黑、祖父变红，然后对祖父做递归处理
  182.         */
  183.         Node parent = x.parent;
  184.         Node uncle = x.uncle();
  185.         Node grandparent = parent.parent;
  186.         if (isRed(uncle)) {
  187.             parent.color = BLACK;
  188.             uncle.color = BLACK;
  189.             grandparent.color = RED;
  190.             fixRedRed(grandparent);
  191.             return;
  192.         }
  194.         // case 4 当红红相邻，叔叔为黑时
  195.         if (parent.isLeftChild() && x.isLeftChild()) { // LL
  196.             parent.color = BLACK;
  197.             grandparent.color = RED;
  198.             rightRotate(grandparent);
  199.         } else if (parent.isLeftChild()) { // LR
  200.             leftRotate(parent);
  201.             x.color = BLACK;
  202.             grandparent.color = RED;
  203.             rightRotate(grandparent);
  204.         } else if (!x.isLeftChild()) { // RR
  205.             parent.color = BLACK;
  206.             grandparent.color = RED;
  207.             leftRotate(grandparent);
  208.         } else { // RL
  209.             rightRotate(parent);
  210.             x.color = BLACK;
  211.             grandparent.color = RED;
  212.             leftRotate(grandparent);
  213.         }
  214.     }
  216.     /**
  217.      * 删除
  218.      * <br>
  219.      * 正常删、会用到李代桃僵技巧、遇到黑黑不平衡进行调整
  220.      *
  221.      * @param key 键
  222.      */
  223.     public void remove(int key) {
  224.         Node deleted = find(key);
  225.         if (deleted == null) {
  226.             return;
  227.         }
  228.         doRemove(deleted);
  229.     }
  231.     public boolean contains(int key) {
  232.         return find(key) != null;
  233.     }
  235.     // 查找删除节点
  236.     private Node find(int key) {
  237.         Node p = root;
  238.         while (p != null) {
  239.             if (key < p.key) {
  240.                 p = p.left;
  241.             } else if (p.key < key) {
  242.                 p = p.right;
  243.             } else {
  244.                 return p;
  245.             }
  246.         }
  247.         return null;
  248.     }
  250.     // 查找剩余节点
  251.     private Node findReplaced(Node deleted) {
  252.         if (deleted.left == null && deleted.right == null) {
  253.             return null;
  254.         }
  255.         if (deleted.left == null) {
  256.             return deleted.right;
  257.         }
  258.         if (deleted.right == null) {
  259.             return deleted.left;
  260.         }
  261.         Node s = deleted.right;
  262.         while (s.left != null) {
  263.             s = s.left;
  264.         }
  265.         return s;
  266.     }
  268.     // 处理双黑 (case3、case4、case5)
  269.     private void fixDoubleBlack(Node x) {
  270.         if (x == root) {
  271.             return;
  272.         }
  273.         Node parent = x.parent;
  274.         Node sibling = x.sibling();
  275.         // case 3 兄弟节点是红色
  276.         if (isRed(sibling)) {
  277.             if (x.isLeftChild()) {
  278.                 leftRotate(parent);
  279.             } else {
  280.                 rightRotate(parent);
  281.             }
  282.             parent.color = RED;
  283.             sibling.color = BLACK;
  284.             fixDoubleBlack(x);
  285.             return;
  286.         }
  287.         if (sibling != null) {
  288.             // case 4 兄弟是黑色, 两个侄子也是黑色
  289.             if (isBlack(sibling.left) && isBlack(sibling.right)) {
  290.                 sibling.color = RED;
  291.                 if (isRed(parent)) {
  292.                     parent.color = BLACK;
  293.                 } else {
  294.                     fixDoubleBlack(parent);
  295.                 }
  296.             }
  297.             // case 5 兄弟是黑色, 侄子有红色
  298.             else {
  299.                 // LL
  300.                 if (sibling.isLeftChild() && isRed(sibling.left)) {
  301.                     rightRotate(parent);
  302.                     sibling.left.color = BLACK;
  303.                     sibling.color = parent.color;
  304.                 }
  305.                 // LR
  306.                 else if (sibling.isLeftChild() && isRed(sibling.right)) {
  307.                     sibling.right.color = parent.color;
  308.                     leftRotate(sibling);
  309.                     rightRotate(parent);
  310.                 }
  311.                 // RL
  312.                 else if (!sibling.isLeftChild() && isRed(sibling.left)) {
  313.                     sibling.left.color = parent.color;
  314.                     rightRotate(sibling);
  315.                     leftRotate(parent);
  316.                 }
  317.                 // RR
  318.                 else {
  319.                     leftRotate(parent);
  320.                     sibling.right.color = BLACK;
  321.                     sibling.color = parent.color;
  322.                 }
  323.                 parent.color = BLACK;
  324.             }
  325.         } else {
  326.             // @TODO 实际也不会出现，触发双黑后，兄弟节点不会为 null
  327.             fixDoubleBlack(parent);
  328.         }
  329.     }
  331.     private void doRemove(Node deleted) {
  332.         Node replaced = findReplaced(deleted);
  333.         Node parent = deleted.parent;
  334.         // 没有孩子
  335.         if (replaced == null) {
  336.             // case 1 删除的是根节点
  337.             if (deleted == root) {
  338.                 root = null;
  339.             } else {
  340.                 if (isBlack(deleted)) {
  341.                     // 双黑调整
  342.                     fixDoubleBlack(deleted);
  343.                 } else {
  344.                     // 红色叶子, 无需任何处理
  345.                 }
  346.                 if (deleted.isLeftChild()) {
  347.                     parent.left = null;
  348.                 } else {
  349.                     parent.right = null;
  350.                 }
  351.                 deleted.parent = null;
  352.             }
  353.             return;
  354.         }
  355.         // 有一个孩子
  356.         if (deleted.left == null || deleted.right == null) {
  357.             // case 1 删除的是根节点
  358.             if (deleted == root) {
  359.                 root.key = replaced.key;
  360.                 root.value = replaced.value;
  361.                 root.left = root.right = null;
  362.             } else {
  363.                 if (deleted.isLeftChild()) {
  364.                     parent.left = replaced;
  365.                 } else {
  366.                     parent.right = replaced;
  367.                 }
  368.                 replaced.parent = parent;
  369.                 deleted.left = deleted.right = deleted.parent = null;
  370.                 if (isBlack(deleted) && isBlack(replaced)) {
  371.                     // @TODO 实际不会有这种情况 因为只有一个孩子时 被删除节点是黑色 那么剩余节点只能是红色不会触发双黑
  372.                     fixDoubleBlack(replaced);
  373.                 } else {
  374.                     // case 2 删除是黑，剩下是红
  375.                     replaced.color = BLACK;
  376.                 }
  377.             }
  378.             return;
  379.         }
  380.         // case 0 有两个孩子 => 有一个孩子 或 没有孩子
  381.         int t = deleted.key;
  382.         deleted.key = replaced.key;
  383.         replaced.key = t;
  385.         Object v = deleted.value;
  386.         deleted.value = replaced.value;
  387.         replaced.value = v;
  388.         doRemove(replaced);
  389.     }
  390. }
  • 以上代码中的 TODO 未作改正

排序算法

二. 题目

1. 二叉搜索树

E01. 删除节点-力扣 450 题

例题已经讲过，用非递归和递归均可实现，这里只给出递归参考代码

  1. public TreeNode deleteNode(TreeNode node, int key) {
  2.     if (node == null) {
  3.         return null;
  4.     }
  5.     if (key < node.val) {
  6.         node.left = deleteNode(node.left, key);
  7.         return node;
  8.     }
  9.     if (node.val < key) {
  10.         node.right = deleteNode(node.right, key);
  11.         return node;
  12.     }
  13.     if (node.left == null) { // 情况1 - 只有右孩子
  14.         return node.right;
  15.     }
  16.     if (node.right == null) { // 情况2 - 只有左孩子
  17.         return node.left;
  18.     }
  19.     TreeNode s = node.right; // 情况3 - 有两个孩子
  20.     while (s.left != null) {
  21.         s = s.left;
  22.     }
  23.     s.right = deleteNode(node.right, s.val);
  24.     s.left = node.left;
  25.     return s;
  26. }
  • 树节点 TreeNode 相当于例题中的 BSTNode
    • TreeNode 有属性：val, left, right，并未区分键值
    • BSTNode 有属性：key, value, left, right，区分了键值
  • 它的 TreeNode 没有 key，比较用的是 TreeNode.val 属性与待删除 key 进行比较

E02. 新增节点-力扣 701 题

例题也讲过了（put），下面给出递归实现

  1. public TreeNode insertIntoBST(TreeNode node, int val) {
  2.     if(node == null) {
  3.         return new TreeNode(val);
  4.     }
  5.     if(val < node.val) {
  6.         node.left = insertIntoBST(node.left, val);
  7.     } else if(node.val < val) {
  8.         node.right = insertIntoBST(node.right, val);
  9.     }
  10.     return node;
  11. }
  • 注意事项与上题相同，不再赘述
  • 题目提示输入的 val 一定与树中节点不同，因此只需考虑新增情况，不会出现更新情况

E03. 查询节点-力扣 700 题

例题讲过，下面给出递归实现

  1. public TreeNode searchBST(TreeNode node, int val) {
  2.     if(node == null) {
  3.         return null;
  4.     }
  5.     if(val < node.val) {
  6.         return searchBST(node.left, val);
  7.     } else if(node.val < val) {
  8.         return searchBST(node.right, val);
  9.     } else {
  10.         return node;
  11.     }
  12. }

E04. 验证二叉搜索树-力扣 98 题

中序非递归实现

  1. public boolean isValidBST(TreeNode root) {
  2.     TreeNode p = root;
  3.     LinkedList<TreeNode> stack = new LinkedList<>();
  4.     long prev = Long.MIN_VALUE;
  5.     while (p != null || !stack.isEmpty()) {
  6.         if (p != null) {
  7.             stack.push(p);
  8.             p = p.left;
  9.         } else {
  10.             TreeNode pop = stack.pop();
  11.             if (prev >= pop.val) {
  12.                 return false;
  13.             }
  14.             prev = pop.val;
  15.             p = pop.right;
  16.         }
  17.     }
  18.     return true;
  19. }
  • 记录 prev 需要用 long，否则若测试用例中最小的节点为 Integer.MIN_VALUE 则测试会失败
  • 注意，如果相邻两个节点相等，也不应当通过测试，例如，下面的树也是不合法的
  1.     2
  2.    / 
  3.   2

中序递归实现

  1. public boolean isValidBST(TreeNode root) {
  2.     if (root == null) {
  3.         return true;
  4.     }
  5.     return doValid(new AtomicLong(Long.MIN_VALUE),root);
  6. }
  8. public boolean doValid(AtomicLong prev, TreeNode node) {
  9.     if (node == null) {
  10.         return true;
  11.     }
  12.     boolean a = doValid(prev, node.left);
  13.     if (prev.get() >= node.val) {
  14.         return false;
  15.     }
  16.     prev.set(node.val);
  17.     boolean b = doValid(prev, node.right);
  18.     return a && b;
  19. }
  • 为何不能用 Long 或 long？因为它们都是局部变量且不可变，因此每次赋值时，并不会改变其它方法调用时的 prev
  • 要么把 prev 设置为 AtomicLong，要么把 prev 设置为全局变量，而不要采用方法参数这样的局部变量
  • 上述代码并不是最有效率的，分析过程见视频讲解

上下限递归

  1. public boolean isValidBST(TreeNode node) {
  2.     return doValid(node, Long.MIN_VALUE, Long.MAX_VALUE);
  3. }
  5. private boolean doValid(TreeNode node, long min, long max) {
  6.     if (node == null) {
  7.         return true;
  8.     }
  9.     if (node.val <= min || node.val >= max) {
  10.         return false;
  11.     }
  12.     return doValid(node.left, min, node.val) && doValid(node.right, node.val, max);
  13. }
  • 设每个节点必须在一个范围内：数据结构与算法2 - 图72#card=math&code=%28min%2C%20max%29&id=QojZn)，不包含边界，若节点值超过这个范围，则返回 false
  • 对于 node.left 范围肯定是 数据结构与算法2 - 图73#card=math&code=%28min%2C%20node.val%29&id=AUzOu)
  • 对于 node.right 范围肯定是 数据结构与算法2 - 图74#card=math&code=%28node.val%2C%20max%29&id=Yjvp8)
  • 一开始不知道 min，max 则取 java 中长整数的最小、最大值
  • 本质是前序遍历 + 剪枝

E05. 求范围和-力扣 938 题

中序递归实现

  1. public int rangeSumBST(TreeNode node, int low, int high) {
  2.     if (node == null) {
  3.         return 0;
  4.     }
  5.     int a = rangeSumBST(node.left, low, high);
  6.     int b = 0;
  7.     if (node.val >= low && node.val <= high) {
  8.         b = node.val;
  9.     }
  10.     return a + b + rangeSumBST(node.right, low, high);
  11. }

中序非递归实现

  1. public int rangeSumBST(TreeNode node, int low, int high) {
  2.     TreeNode p = node;
  3.     LinkedList<TreeNode> stack = new LinkedList<>();
  4.     int sum = 0;
  5.     while(p != null || !stack.isEmpty()) {
  6.         if (p != null) {
  7.             stack.push(p);
  8.             p = p.left;
  9.         } else {
  10.             TreeNode pop = stack.pop();
  11.             if (pop.val > high) {
  12.                 break;
  13.             }
  14.             if (pop.val >= low) {
  15.                 sum += pop.val;
  16.             }
  17.             p = pop.right;
  18.         }
  19.     }
  20.     return sum;
  21. }
  • leedcode 执行耗时 4ms

上下限递归实现

  1. public int rangeSumBST(TreeNode node, int low, int high) {
  2.     if (node == null) {
  3.         return 0;
  4.     }
  5.     if (node.val < low) {
  6.         return rangeSumBST(node.right, low, high);
  7.     } 
  8.     if (node.val > high) {
  9.         return rangeSumBST(node.left, low, high);
  10.     }
  11.     return node.val + 
  12.         rangeSumBST(node.left, low, high) + 
  13.         rangeSumBST(node.right, low, high);
  14. }
  • leetcode 执行耗时 0 ms
  • node.val < low 只需考虑它右子树的累加结果
  • node.val > high 只需考虑它左子树的累加结果
  • node.val 在范围内，需要把当前节点的值加上其左右子树的累加结果

E06. 根据前序遍历结果构造二叉搜索树-力扣 1008 题

直接插入

注意：根据前序遍历的结果，可以唯一地构造出一个二叉搜索树

  1. public TreeNode bstFromPreorder(int[] preorder) {
  2.     TreeNode root = insert(null, preorder[0]);
  3.     for (int i = 1; i < preorder.length; i++) {
  4.         insert(root, preorder[i]);
  5.     }
  6.     return root;
  7. }
  9. private TreeNode insert(TreeNode node, int val) {
  10.     if (node == null) {
  11.         return new TreeNode(val);
  12.     }
  13.     if(val < node.val) {
  14.         node.left = insert(node.left, val);
  15.     } else if(node.val < val){
  16.         node.right = insert(node.right, val);
  17.     }
  18.     return node;
  19. }

上限法

  1. public TreeNode bstFromPreorder(int[] preorder) {
  2.     return insert(preorder, Integer.MAX_VALUE);
  3. }
  5. int i = 0;
  6. private TreeNode insert(int[] preorder, int max) {
  7.     if (i == preorder.length) {
  8.         return null;
  9.     }
  10.     int val = preorder[i];
  11.     System.out.println(val + String.format("[%d]", max));
  12.     if (val > max) {
  13.         return null;
  14.     }
  15.     TreeNode node = new TreeNode(val);
  16.     i++;
  17.     node.left = insert(preorder, node.val); 
  18.     node.right = insert(preorder, max);     
  19.     return node;
  20. }

依次处理 prevorder 中每个值, 返回创建好的节点或 null 作为上个节点的孩子

  1. 如果超过上限, 返回 null
  2. 如果没超过上限, 创建节点, 并将其左右孩子设置完整后返回
    • i++ 需要放在设置左右孩子之前，意思是从剩下的元素中挑选左右孩子

分治法

  1. public TreeNode bstFromPreorder(int[] preorder) {
  2.     return partition(preorder, 0, preorder.length - 1);
  3. }
  5. private TreeNode partition(int[] preorder, int start, int end) {
  6.     if (start > end) {
  7.         return null;
  8.     }
  9.     TreeNode root = new TreeNode(preorder[start]);
  10.     int index = start + 1;
  11.     while (index <= end) {
  12.         if (preorder[index] > preorder[start]) {
  13.             break;
  14.         }
  15.         index++;
  16.     }
  17.     // index 就是右子树的起点
  18.     root.left = partition(preorder, start + 1, index - 1);
  19.     root.right = partition(preorder, index, end);
  20.     return root;
  21. }
  • 刚开始 8, 5, 1, 7, 10, 12，方法每次执行，确定本次的根节点和左右子树的分界线
  • 第一次确定根节点为 8，左子树 5, 1, 7，右子树 10, 12
  • 对 5, 1, 7 做递归操作，确定根节点是 5， 左子树是 1， 右子树是 7
  • 对 1 做递归操作，确定根节点是 1，左右子树为 null
  • 对 7 做递归操作，确定根节点是 7，左右子树为 null
  • 对 10, 12 做递归操作，确定根节点是 10，左子树为 null，右子树为 12
  • 对 12 做递归操作，确定根节点是 12，左右子树为 null
  • 递归结束，返回本范围内的根节点

E07. 二叉搜索树的最近公共祖先-力扣 235 题

要点：若 p，q 在 ancestor 的两侧，则 ancestor 就是它们的最近公共祖先

  1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  2.     TreeNode ancestor = root;
  3.     while (ancestor.val > p.val && ancestor.val > q.val || 
  4.            ancestor.val < p.val && ancestor.val < q.val) {
  5.         if (ancestor.val > p.val) {
  6.             ancestor = ancestor.left;
  7.         } else {
  8.             ancestor = ancestor.right;
  9.         }
  10.     }
  11.     return ancestor;
  12. }

二叉树的最近公共祖先-力扣 236 题

二叉树展开为链表-力扣 114 题

有序数组构造平衡二叉搜索树-力扣 108 题

二叉搜索树变为平衡-力扣 1382 题