20220531数据结构绿皮书读书笔记
10 二叉树
10.1 定义
递归定义
二叉树是空的,或者由一个根节点和两个称作左右子树的二叉树构成的
前序中序后序遍历,也称先根中根或后根遍历
10.2 二叉搜索树
我们能否找到一个线性表的实现可以很快的搜搜,同时方便的修改呢?
二叉搜索树是个很好的解决方案,定义如下:
二叉搜索树是满足条件的二叉树,可以为空或者每个节点都有一个key,条件如下:
1.根节点的key比其他任意左子树中的节点大
2.根节点的key比其他任意右子树中的节点小
3.左右子树均是二叉搜索树
关于key的大小,可以延展下离散数学的偏序关系
10.3 构建二叉搜索树
自底向上构建,记录最顶的值,最后串起来
10.4 AVL树
调整子树高度使其平衡的一种二叉搜索树
子树高度相差不超过1
插入和删除时动态调整节点,使其始终满足这个条件,怎么旋转都是细节,如果你编程语言足够扎实,给出算法后应当能准确的实现,即使效率不高也没关系,反正一般情况的开发不需要自己造轮子
10.5 延展树
使旧数据放的远点,新数据更容易被访问到
在AVL的基础上,调整的时候做一些trick
拓展话题,树的布局算法
https://blog.hylstudio.cn/archives/917
https://llimllib.github.io/pymag-trees/
明天继续多路树
mark 目前是520页 ,pdf是538页
0 Comments