以剑指offer这本书为入门的笔记总结,同时也在这里记录相关的算法练习。
- [ok]链表
- [ok]二叉树
- [ok]栈
- [ok]队列
- [ok]哈希表
- 字典树
- [ok]二分查找
- [ok]插值查找(以及在选择中值上的优化)
- [ok]指数查找
- [ok]分块查找(类似于指数搜索,用2^i来进行分块)
- [ok]顺序查找
- [ok]二叉排序树(BST)
- 平衡二叉树(AVL)(详情)
- 2-3查找树
- 红黑树(RBT)(详情)
- B树和B+树
- 交换排序
- [ok]冒泡排序
- [ok]快速排序
- 插入排序
- [ok]简单插入排序
- [ok]希尔排序
- 选择排序
- [ok]简单选择排序
- [ok]堆排序
- 归并排序
- [ok]二路归并排序
- 多路归并排序
- 非比较累排序
- 计数排序
- 桶排序
- 基数排序
具体插入中,会遇到四种不平衡情况,因为在节点A的左孩子(L)的左子树(L)下插入新节点,导致了不平衡,简称:LL不平衡。其他三种不平衡情况分别为:RR不平衡、LR不平衡、RL不平衡。这四种情况的处理办法如下表:
不平衡情况 | 处理办法 |
---|---|
LL不平衡 | 单右旋 |
RR不平衡 | 单左旋 |
LR不平衡 | 先左旋再右旋 |
RL不平衡 | 先右旋再左旋 |
剩下两种情况处理方法类似。
RBT对平衡要求低,调整频率没有AVL高,平衡性米有AVL好;如果插入删除不怎么频繁,则AVL好点;如果相反,则BST好点。
- RBT根节点必须是黑色
- 每个节点都有颜色,要么红色,要么黑色
- 红黑树把空指针看作黑色节点,所以叶子节点是空节点
- 红属性:红色节点的孩子必须为黑色节点(对黑色没有这样的要求)
- 黑属性:任何一个节点到它的所有叶子节点的简单路径上包含的黑色节点数相同
- RBT的最大高度为:$2\cdot\log(n+1)$,n为节点数(这里是以2为低的对数,不把空指针算入节点)
- 黑色高度:从x节点到叶子节点的路径中包含的黑色节点个数(不含叶子)
如果是空树,将插入的节点作为根节点并涂上黑色,如果不是空树,则插入节点总是先涂上红色并称为新节点,然后检查以下几点:
- 如果新节点的父节点是黑色,则插入操作结束。
- 如果新节点的父节点是红色,且它的兄弟节点也是红色,则将它们全部涂黑,再向上检父节点,交换它的颜色,一直往上,直到根节点结束。
- 如果新节点的父节点是红色,同时父节的兄弟节点是黑色或没有节点,则需要旋转,再着色。根据两个红色的位置关系判断出需要RL,LR,RR,LL的操作,最后交换颜色,使它成为红黑树。
排序二叉树固然查询很高效,但它有不平衡的问题,可能左子树很长右子树却很短,造成查询时性能不佳(logn退化成n),完全平衡的二叉树能保证层数平均,从而查询效率高,但是维护又很麻烦,每次插入和删除有很大的可能要大幅调整树结构。红黑树就是介于完全不平衡和完全平衡之间的一种二叉树,通过每个节点有红黑两种颜色、从节点到任意叶子节点会经过相同数量的黑色节点等一系列规则,实现了【树的层数最大也只会有两倍的差距】,这样既能提高插入和删除的效率,又能让树相对平衡从而有还不错的查询效率。从整体上讲,红黑树就是一种中庸之道的二叉树。