一. 基础算法

查找算法

不管是之前学过的数组、链表、队列、还是栈,这些线性结构中,如果想在其中查找一个元素,效率是比较慢的,只有数据结构与算法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;
  6. public BSTNode(int key) {
  7. this.key = key;
  8. this.value = key;
  9. }
  10. public BSTNode(int key, Object value) {
  11. this.key = key;
  12. this.value = value;
  13. }
  14. public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
  15. this.key = key;
  16. this.value = value;
  17. this.left = left;
  18. this.right = right;
  19. }
  20. }

查询

递归实现

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

非递归实现

  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;
  7. public BSTNode(T key) {
  8. this.key = key;
  9. this.value = key;
  10. }
  11. public BSTNode(T key, Object value) {
  12. this.key = key;
  13. this.value = value;
  14. }
  15. public BSTNode(T key, Object value, BSTNode<T> left, BSTNode<T> right) {
  16. this.key = key;
  17. this.value = value;
  18. this.left = left;
  19. this.right = right;
  20. }
  21. }
  22. BSTNode<T> root;
  23. public Object get(T key) {
  24. return doGet(root, key);
  25. }
  26. private Object doGet(BSTNode<T> node, T key) {
  27. if (node == null) {
  28. return null;
  29. }
  30. int result = node.key.compareTo(key);
  31. if (result > 0) {
  32. return doGet(node.left, key);
  33. } else if (result < 0) {
  34. return doGet(node.right, key);
  35. } else {
  36. return node.value;
  37. }
  38. }
  39. }

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

最小

递归实现

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

非递归实现

  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. }
  4. public Object doMax(BSTNode node) {
  5. if (node == null) {
  6. return null;
  7. }
  8. // 右边已走到头
  9. if (node.left == null) {
  10. return node.value;
  11. }
  12. return doMin(node.right);
  13. }

非递归实现

  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. }
  4. private BSTNode doPut(BSTNode node, int key, Object value) {
  5. if (node == null) {
  6. return new BSTNode(key, value);
  7. }
  8. if (key < node.key) {
  9. node.left = doPut(node.left, key, value);
  10. } else if (node.key < key) {
  11. node.right = doPut(node.right, key, value);
  12. } else {
  13. node.value = value;
  14. }
  15. return node;
  16. }
  • 若找到 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. }
  14. if (p == null) {
  15. return null;
  16. }
  17. // 情况1 - 有左孩子
  18. if (p.left != null) {
  19. return max(p.left);
  20. }
  21. // 情况2 - 有祖先自左而来
  22. return ancestorFromLeft != null ? ancestorFromLeft.value : null;
  23. }
  24. public Object successor(int key) {
  25. BSTNode ancestorFromRight = null;
  26. BSTNode p = root;
  27. while (p != null) {
  28. if (key < p.key) {
  29. ancestorFromRight = p;
  30. p = p.left;
  31. } else if (p.key < key) {
  32. p = p.right;
  33. } else {
  34. break;
  35. }
  36. }
  37. if (p == null) {
  38. return null;
  39. }
  40. // 情况1 - 有右孩子
  41. if (p.right != null) {
  42. return min(p.right);
  43. }
  44. // 情况2 - 有祖先自右而来
  45. return ancestorFromRight != null ? ancestorFromRight.value : null;
  46. }

删除

要删除某节点(称为 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. }
  49. /**
  50. * 托孤方法
  51. *
  52. * @param parent 被删除节点的父亲
  53. * @param deleted 被删除节点
  54. * @param child 被顶上去的节点
  55. */
  56. // 只考虑让 n1父亲的左或右孩子指向 n2, n1自己的左或右孩子并未在方法内改变
  57. private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
  58. if (parent == null) {
  59. root = child;
  60. } else if (deleted == parent.left) {
  61. parent.left = child;
  62. } else {
  63. parent.right = child;
  64. }
  65. }

递归实现

  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. }
  6. public BSTNode doDelete(BSTNode node, int key, ArrayList<Object> result) {
  7. if (node == null) {
  8. return null;
  9. }
  10. if (key < node.key) {
  11. node.left = doDelete(node.left, key, result);
  12. return node;
  13. }
  14. if (node.key < key) {
  15. node.right = doDelete(node.right, key, result);
  16. return node;
  17. }
  18. result.add(node.value);
  19. if (node.left != null && node.right != null) {
  20. BSTNode s = node.right;
  21. while (s.left != null) {
  22. s = s.left;
  23. }
  24. s.right = doDelete(node.right, s.key, new ArrayList<>());
  25. s.left = node.left;
  26. return s;
  27. }
  28. return node.left != null ? node.left : node.right;
  29. }

说明

  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. }
  4. private AVLNode doPut(AVLNode node, int key, Object value) {
  5. if (node == null) {
  6. return new AVLNode(key, value);
  7. }
  8. if (key == node.key) {
  9. node.value = value;
  10. return node;
  11. }
  12. if (key < node.key) {
  13. node.left = doPut(node.left, key, value);
  14. } else {
  15. node.right = doPut(node.right, key, value);
  16. }
  17. updateHeight(node);
  18. return balance(node);
  19. }

删除

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

完整代码备份

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

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

上下限递归

  1. public boolean isValidBST(TreeNode node) {
  2. return doValid(node, Long.MIN_VALUE, Long.MAX_VALUE);
  3. }
  4. private boolean doValid(TreeNode node, long min, long max) {
  5. if (node == null) {
  6. return true;
  7. }
  8. if (node.val <= min || node.val >= max) {
  9. return false;
  10. }
  11. return doValid(node.left, min, node.val) && doValid(node.right, node.val, max);
  12. }
  • 设每个节点必须在一个范围内:数据结构与算法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. }
  8. private TreeNode insert(TreeNode node, int val) {
  9. if (node == null) {
  10. return new TreeNode(val);
  11. }
  12. if(val < node.val) {
  13. node.left = insert(node.left, val);
  14. } else if(node.val < val){
  15. node.right = insert(node.right, val);
  16. }
  17. return node;
  18. }

上限法

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

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

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

分治法

  1. public TreeNode bstFromPreorder(int[] preorder) {
  2. return partition(preorder, 0, preorder.length - 1);
  3. }
  4. private TreeNode partition(int[] preorder, int start, int end) {
  5. if (start > end) {
  6. return null;
  7. }
  8. TreeNode root = new TreeNode(preorder[start]);
  9. int index = start + 1;
  10. while (index <= end) {
  11. if (preorder[index] > preorder[start]) {
  12. break;
  13. }
  14. index++;
  15. }
  16. // index 就是右子树的起点
  17. root.left = partition(preorder, start + 1, index - 1);
  18. root.right = partition(preorder, index, end);
  19. return root;
  20. }
  • 刚开始 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 题