第六章 二分搜索树

1 树结构无处不在 , 文件夹 , 图书馆书分类 , 公司的组织结构
2 BST也是一种二分思想
3 BST , 平衡二叉树 , 堆
4 和链表一样是动态数组结构 , 不需要在开始的时候分配容量
5 树 天然递归结构 , 每个节点都可以看做一颗二叉树

image.png

6 满二叉树
7 完全二叉树 堆
8 和链表类似 , 一个节点也可以当做链表 , 空也可以当做链表 , 做算法题的时候可以一般化操作


9 每个节点>左子树所有节点的值
每个节点 < 右子树所有节点的值

10 BST不一定是满的
11 树的核心思想 , 类比去图书馆找书 , 不需要遍历所有类比的书
12 元素需要有可比较性
13 BST的基本设计

14 BST添加元素的动画 6-3

15 递归地插入元素

16 实现的这个BST是不包含重复元素的
17 如果想包含重复元素 , 改变定义 , 知识点9小于等于和大于等于
18 插入元素的递归和非递归代码实现 , 类似链表的非递归

image.png

image.png

19 我的伪代码递归和非递归实现

20 最坏情况可能退化为链表

21 优化递归逻辑 , 将空作为一颗BST

22 add定义改变


image.png

23 代码更简洁清晰 , 定义的不同的巨大差距

24 链表插入和BST的add很相似 , 对比一下

25 递归实现contains(E e)

image.png

image.png

假设节点存储的是学生的成绩 , 访问该节点的操作是给每个学生+2分
访问的逻辑和业务相关

image.png

28 人肉走遍历逻辑 , 写出遍历结果
29 另一种更方便的人肉遍历逻辑
30 前序遍历的一个应用 : BST的tosring写法

image.png

image.png

31 如何打印这样的 tips : 层序遍历

image.png

32 中序遍历 , 有序的

image.png

33 用另一个方法来递归 , 再提供个用户接口方法 , 如: inOrder() , private inOrder(Node node)

34 后续遍历

image.png

35 后序遍历的应用 : 需要先处理左子树和右子树的场景 , 如为BST释放内存 , 先释放子树

36 后序遍历特点 , 先处理子树

37 设置3个辅助点 , 每个元素其实都会被访问3次 , 假设空也为一颗子树

image.png

image.png

38 前序遍历的辅助点动画演示

image.png

39 中序遍历的辅助点动画演示

image.png

40 后序遍历的辅助点动画演示

image.png

41 模拟系统栈的非递归遍历写法
画图 , 后入先出的规则
用之前的 Command结构体 , go , print 模拟完整的系统栈

42 中序和后序遍历非递归实现 , 应用不广泛
实现比较复杂 , 但是用command结构体的方式很简单 (玩转算法面试课程里提到 )

43 DFS ->栈 , BFS -> 队列

44 层序遍历 BFS 队列

45 BFS的意义 , 更快的搜索

image.png

46 常用于算法设计 , 如最短路径

47 图也有DFS和BFS , 图多了个visited map , 防止重复访问 , 树不会重复访问

48 找到各数据结构之间的联系 链表 树 图

49 删除操作拆解 , 先写出删最大最小值的方法

50 最小值一直向左走 , 最左边的元素
最大值一直向右走 , 最右边的元素

image.png

51 当删除最小值时候 , 最小值有子节点 , 把子节点拼上

image.png

52 removeMin()的定义 : 删除最小值所在节点 , 返回最小值

image.png

image.png

53 minimum 遍历了一次 , removeMin又遍历了一次 , 能合并这两部操作么

54 删除任意节点的情况分析
只有左孩子 or 只有右孩子
左右都有的:
融合两个子树

image.png

55

image.png

image.png

image.png

image.png

56 也可以用前驱代替

57 BST的顺序性
58 前驱和后继的获取
59 什么是floor ceil
60 floor 比45小的最大的元素 , ceil 比45大的最小元素
61 实现BST的floor和ceil

image.png

62 求BST中某个数的rank

image.png

63 select是rank的反向

image.png

64 每个节点维护一个size属性 , 方便rank和select的实现

image.png

65 维护depth属性

image.png

66 写一个支持重复元素的BST

image.png

67 leetcode上bst的题