第六章 二分搜索树
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
26
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的题
网友评论