|
三 树形结构
?? ?1 树
?? ??? ?节点、根节点、父节点、子节点、兄弟节点（相同父亲才叫兄弟节点）
?? ??? ?一棵树可以没有任何节点，称为空树
?? ??? ?一棵树可以只有一个节点，也就是只有根节点
?? ??? ?子树、左子树、右子树 ：这个就是有直接关系的树，孙子不算
?? ??? ?节点的度：子树的个数
?? ??? ?树的度：所有节点度中的最大值
?? ??? ?叶子节点：度为0的节点
?? ??? ?非叶子节点：度不为零的节点
?? ??? ?层数：根节点在第一层，根节点的子节点在第二层，
?? ??? ?节点的深度:从根节点到当前节点的唯一路径上的节点数
?? ??? ?节点的高度：从当前节点到最远叶子节点的路径上的节点总数
?? ??? ?树的深度：所有节点深度中的最大值
?? ??? ?树的高度：所有节点高度中的最大值 ?
?? ??? ?树的深度= 树的高度
?? ??? ?
?? ??? ?有序树：树中任意节点的子节点之间有顺序关系 ? ? ? ? ? ? ? ? ? ? ? ? 有序树和无序树只针对子节点
?? ??? ?无序树：树的任意节点之间的子节点之间没有顺序 ?也称自由树
?? ?2 二叉树 binary tree
?? ??? ?定义：每个节点的度最大为2 并且左子树和右子树是有顺序的
?? ??? ?特点 ：
?? ??? ??? ?1每个节点的度最大是2?
?? ??? ??? ?2 左子树以及右子树都是有顺序的
?? ??? ??? ?3 即使节点只有一颗子树，也要区分左右子树
?? ??? ??? ?4 非空二叉树的第i层，最多有2的i次方-1个节点
?? ??? ??? ?5 在高度为h的二叉树上最多有2的h次方-1个节点
?? ??? ??? ?6 对于任意一个二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，那么就有n0=n2+1
?? ??? ?真二叉树：所有节点的度要么是零要么是二
?? ??? ?满二叉树：所有节点的度要么是0，要么是2，并且所有的叶子节点都在最后一层
?? ??? ??? ?特点：
?? ??? ??? ??? ?1在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多
?? ??? ??? ??? ?2 满二叉树一定是真二叉树，真二叉树不一定是满二叉树。
?? ??? ??? ??? ?3 满二叉树的高度是h 那么第i层的节点数量是2的i次方减一
?? ??? ?完全二叉树：叶子节点只会出现在最后两层，并且最后一层的叶子节点都靠左对其（叶子节点从上往下，从左到右进行排序）
?? ??? ??? ?特点：?? ?
?? ??? ??? ??? ?1 度为1的节点只有左子树
?? ??? ??? ??? ?2 度为1 的节点要么是1个，要么是0个
?? ??? ??? ??? ?3 同样节点数量的二叉树，完全二叉树的高度最小
?? ??? ??? ??? ?4 高度为h，则至少有2的h-1次方个节点，最多有2的h次方-1个节点
?? ??? ??? ??? ?5 具有n个节点的完全二叉树，从上到下，从左到右对节点从1开始进行编号，对于任意第i个节点，前提是i大于1 他的父亲节点编号是floor（i/2）
?? ??? ??? ??? ?6 总节点数量是n ?如果n是偶数，则叶子节点数量是二分之n ?如果n是奇数 叶子节点数量是n+1然后除以2 总结起来就是floor(n/2+1/2),除法默认就是向下取整直接除以2就行了
?? ??? ??? ??? ?而非叶子节点是ceiling(())
?? ??? ??? ??? ?
?? ?3 二叉搜索树：
?? ??? ?二叉搜索树：添加、删除、搜索的最坏的时间复杂度均可优化至O(logn)
?? ??? ?特点：任意一个节点的值都大于其左子树所有节点的值
?? ??? ? ? ? ?任意一个节点的值都小于其右子树所有节点的值
?? ??? ??? ? ?二叉搜索树存储的元素必须具备可比较性
?? ??? ?接口设计：
?? ??? ?int size()
?? ??? ?isEmpty()
?? ??? ?add(E element) 建立比较器，找到父节点，然后判断在父节点的位置，然后size++
?? ??? ?remove(E element)
?? ??? ?contains(E element)
?? ??? ?
?? ??? ?遍历：传递处理逻辑 增强遍历（在处理逻辑上加上判断）：目的是随时停止遍历
?? ??? ?前序遍历
?? ??? ?中序遍历
?? ??? ?后序遍历
?? ??? ?层序遍历
?? ??? ?
?? ??? ?打印?
?? ??? ?
?? ??? ?获取二叉树的高度
?? ??? ?
?? ??? ?判断是否是二叉树
?? ??? ?
?? ??? ?反转二叉树
?? ??? ?
?? ??? ?算法重点使用递归，迭代
?? ??? ?
?? ??? ?重构二叉树：前序遍历和中序遍历 ?以及后序遍历加上中序遍历 能确定唯一的二叉树
?? ??? ?
?? ??? ?前驱节点：left ！= Null ? 以及 ?left = null && parent != null ? 以及 left == null && parent == null 没有前驱节点
?? ?4 平衡二叉搜索树(avl树) ?让添加删除的时间复杂度维持在O(logn)
?? ??? ?背景：
?? ??? ?二叉树搜索树的时间复杂度 是O(logn) 就是二叉树的高度
?? ??? ?二叉搜索树的缺点：
?? ??? ?1 当有序添加元素时退化成链表
?? ??? ?2 删除节点的时候也会退化成链表
?? ??? ?平衡二叉搜索树：当节点数量固定的时候，左右子树的高度越接近，这颗二叉树就越平衡
?? ?
?? ??? ?改进二叉搜索树
?? ??? ?首先，节点的添加和删除时无法限制的，
?? ??? ?接着，在节点的添加、删除操作之后，想办法让二叉搜索树恢复平衡（减少树的高度）
?? ??? ?如果接着继续调整节点的位置，完全可以达到理想平衡，但是付出的代价比较大
?? ??? ?如果调整的次数比较多，反而增加了时间复杂度
?? ??? ?总结：用尽量少的调整次数达到适度平衡就可以
?? ??? ?经典的平衡二叉树
?? ??? ?avl树、红黑树
?? ??? ?平衡因子：某节点的左右子树的高度差
?? ??? ?特点：
?? ??? ?每个节点的平衡因子只可能是1 0 -1?
?? ??? ?每个节点的左右子树的高度差不超过1?
?? ??? ?搜索、添加、删除的时间复杂度是O(logn)
?? ??? ?
?? ??? ?添加导致的失衡：
?? ??? ?可能会导致所有的祖先节点都失衡，但是只要让高度最低的失衡节点恢复平衡，整棵树就平衡了
?? ??? ?父节点不会失衡，非祖先节点不会失衡，
?? ?
?? ??? ?ll 右边旋转 单旋 ? ll的意思是在失衡节点的左边左边
?? ??? ?rr 左边旋转 单旋
?? ??? ?LR 双旋 先左边，后边右边
?? ??? ?RL 双旋 先右边 后左边 ? ? ?
?? ??? ?总结： 相同字母反，不同字母同
?? ?
?? ??? ?删除导致的失衡：
?? ??? ?可能会导致父节点或者祖父节点失衡，但是只有一个能失衡，如果删除导致父节点失衡了，那么这个删除的节点一定是比较短的
?? ??? ?让父节点恢复平衡后，可能会导致更高的祖先节点失衡，但是最多需要ologn次调整
?? ?
?? ?5 B树
?? ??? ?讲b树的时候引入红黑树
?? ??? ?红黑树性质：
?? ??? ?1 节点是red或者black
?? ??? ?2 根节点是black
?? ??? ?3 叶子节点都是black
?? ??? ?4 红色节点的parent、子节点都是black 从根节点到叶子节点的所有路径上不能有两个连续的red节点
?? ??? ?5 从任意一个节点到叶子节点的所有路径都包含相同数目的black节点
?? ??? ?
?? ??? ?B树是一种多路搜索树，多用于文件系统、数据库的实现
?? ??? ?特点：一个节点可以存储超过两个元素、可以超过两个节点
?? ??? ? ? ? ?拥有二叉树的一些性质
?? ??? ??? ? ?平衡，每个节点的所有子树高度一致
?? ??? ??? ? ?比较矮
?? ? ? ?m阶b树：就是一个节点最多有m个子节点
?? ??? ?性质：
?? ??? ?1 节点内元素个数?
?? ??? ?根节点： 1 <= x <= m-1
?? ??? ? ? 非根节点：（m/2)取整减去1 <= x <m-1
?? ??? ?2 节点数 y= x + 1，就是在原来元素个数的范围上运算就行了
?? ??? ?代表：根节点 2<= y <= m
?? ??? ? ? ? ?非根节点：（m/2)取整 <= y <= m ? m =3， ?2<= y <=3 因此可以成为(2,3)树
?? ??? ?
?? ??? ?b树和二叉搜索树的关系
?? ??? ?两代合并,最多拥有四个子节点.
?? ??? ?三代合并,最多拥有八个子节点.
?? ??? ?n代合并,则最多是拥有2的n次方个子节点.
?? ??? ?
?? ??? ?添加:新添加的元素一定是在叶子节点中
?? ??? ?
?? ??? ?上溢:一个节点存储超过阶数的元素
?? ??? ? 一个节点引发上溢,那么这个节点的元素必然是m个
?? ??? ? 解决办法:将k位置上的元素向上与父节点合并 ?,如果父节点也触发了上溢,一直向上溢,知道根节点 ? 一旦到根节点了,则可能让b树高度加1
?? ??? ??
?? ??? ? 删除,
?? ??? ? 如果删除元素在叶子节点中,直接删除即可.
?? ??? ? 如果删除元素在非叶子节点中,找到前驱然后替换,删除前驱即可
?? ??? ? 下溢:
?? ??? ? 节点的元素删除之后,元素个数小于最低限制
?? ??? ? 产生下溢出的节点数量必然等于（m/2)取整-2
?? ??? ? 从左侧相邻节点借元素.
?? ??? ??
?? ??? ? 如果临近节点元素正好是最低限制的,无法借出,则从父节点中拿出一个,触发下溢,一直到根节点则可能导致b树变低
?? ??? ??
?? ??? ? 作业四阶b树从1 加到22 然后再一个一个删除
?? ??? ??
?? ?5 红黑树
?? ??? ?注意这里面再最后面都是有一个叶子节点的
?? ??? ?对于红黑树，判断的时候尽量使用颜色来进行判断
?? ??? ?性质：
?? ??? ?红黑树性质：
?? ??? ?1 节点是red或者black
?? ??? ?2 根节点是black
?? ??? ?3 叶子节点都是black
?? ??? ?4 红色节点的parent、子节点都是black 从根节点到叶子节点的所有路径上不能有两个连续的red节点
?? ??? ?5 从任意一个节点到叶子节点的所有路径都包含相同数目的black节点
?? ??? ?
?? ??? ?特点:红黑树其实与四阶b树具有等价性 ? 当Black节点与它的red子节点融合在一起的时候,形成一个b树节点
?? ??? ?红黑树中黑色节点的个数,就是四阶b树中,总节点数量
?? ??? ?
?? ??? ?无论添加还是删除只要操作之后还是红黑树就可以了
?? ??? ?添加:一共十二种情况 ?
?? ??? ?新添加节点直接设置为红色 ?这个不是绝对的，先按照符合b树的观点，就是一个黑色带着两个红色子节点。
?? ??? ?
?? ??? ?1 parent是black 不用任何操作 四种情况
? ? ? ? 2 叔父节点不是红色, 四种情况
?? ??? ??? ?进行双旋转操作
?? ??? ?3 叔父节点是red ?这个只需要染色，然后上溢出就行了
?? ??? ??? ?parent/uncle 染色乘black ? 上溢的时候当作新添加到上一层的节点。
?? ??? ??? ?向上合并,如果上溢到根节点,则将根节点染色乘black就行了
?? ??? ??? ?
?? ??? ?删除：
?? ??? ?在b树中删除节点都是在叶子节点中
?? ??? ?
?? ? ? ?1 红色节点直接删除，不用任何处理
?? ??? ?2 黑色节点
?? ??? ? ? ?1 拥有两个red子节点的black节点 不可能直接被删除，会找它的子节点替代删除，自己并没有被删除
?? ??? ??? ?2 拥有一个red子节点的black节点 需要删除 ?，用来替代的节点是红色节点染色成为黑色就可以
?? ??? ??? ?3 黑色叶子节点 ?需要删除· 1 兄弟是黑色，有至少一个红色兄弟节点，可以借 ?2 兄弟是黑色，兄弟节点没有红色子节点。此时如果父节点是红色，不会连锁下溢，如果父节点是黑色必然下溢出
?? ??? ??? ??? ?兄弟是红色，能借出的是兄弟的儿子，把兄弟的儿子旋转之后变成兄弟。变成兄弟是黑色情况
?? ??? ?
|