20220531数据结构绿皮书读书笔记

 

 

 

 

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
Leave a Reply