文章插图
左旋的操作同样可以用一句话简单表示：将当前结点S的左孩子E的右孩子旋转为当前结点S的左孩子 ， 同时将当前结点S旋转为左孩子E的右孩子 。可用动画表示：
文章插图
红黑树平衡二叉树（AVL）为了追求高度平衡 ， 需要通过平衡处理使得左右子树的高度差必须小于等于1 。高度平衡带来的好处是能够提供更高的搜索效率 ， 其最坏的查找时间复杂度都是O(logN) 。但是由于需要维持这份高度平衡 ， 所付出的代价就是当对树种结点进行插入和删除时 ， 需要经过多次旋转实现复衡 。这导致AVL的插入和删除效率并不高 。
为了解决这样的问题 ， 能不能找一种结构能够兼顾搜索和插入删除的效率呢？这时候红黑树便申请出战了 。
红黑树具有五个特性：
每个结点要么是红的要么是黑的 。
根结点是黑的 。
每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的 。
如果一个结点是红的 ， 那么它的两个儿子都是黑的 。
对于任意结点而言 ， 其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点 。
文章插图
红黑树通过将结点进行红黑着色 ， 使得原本高度平衡的树结构被稍微打乱 ， 平衡程度降低 。红黑树不追求完全平衡 ， 只要求达到部分平衡 。这是一种折中的方案 ， 大大提高了结点删除和插入的效率 。C++中的STL就常用到红黑树作为底层的数据结构 。
红黑树VS平衡二叉树
文章插图
除了上面所提及的树结构 ， 还有许多广泛应用在数据库、磁盘存储等场景下的树结构 。比如B树、B+树等 。这里就先不介绍了诶 ， 下次在讲述相关存储原理的时候将会着重介绍 。（其实是因为懒）
7 堆了解完二叉树 ， 再来理解堆就不是什么难事了 。堆通常是一个可以被看做一棵树的数组对象 。堆的具体实现一般不通过指针域 ， 而是通过构建一个一维数组与二叉树的父子结点进行对应 ， 因此堆总是一颗完全二叉树 。
对于任意一个父节点的序号n来说（这里n从0算） ， 它的子节点的序号一定是2n+1 ， 2n+2 ， 因此可以直接用数组来表示一个堆 。
不仅如此 ， 堆还有一个性质：堆中某个节点的值总是不大于或不小于其父节点的值 。将根节点最大的堆叫做最大堆或大根堆 ， 根节点最小的堆叫做最小堆或小根堆 。
文章插图
堆常用来实现优先队列 ， 在面试中经常考的问题都是与排序有关 ， 比如堆排序、topK问题等 。由于堆的根节点是序列中最大或者最小值 ， 因而可以在建堆以及重建堆的过程中 ， 筛选出数据序列中的极值 ， 从而达到排序或者挑选topK值的目的 。
8 散列表散列表也叫哈希表 ， 是一种通过键值对直接访问数据的机构 。在初中 ， 我们就学过一种能够将一个x值通过一个函数获得对应的一个y值的操作 ， 叫做映射 。散列表的实现原理正是映射的原理 ， 通过设定的一个关键字和一个映射函数 ， 就可以直接获得访问数据的地址 ， 实现O(1)的数据访问效率 。在映射的过程中 ， 事先设定的函数就是一个映射表 ， 也可以称作散列函数或者哈希函数 。
文章插图
散列表的实现最关键的就是散列函数的定义和选择 。一般常用的有以下几种散列函数：
直接寻址法：取关键字或关键字的某个线性函数值为散列地址 。
数字分析法：通过对数据的分析 ， 发现数据中冲突较少的部分 ， 并构造散列地址 。例如同学们的学号 ， 通常同一届学生的学号 ， 其中前面的部分差别不太大 ， 所以用后面的部分来构造散列地址 。
平方取中法：当无法确定关键字里哪几位的分布相对比较均匀时 ， 可以先求出关键字的平方值 ， 然后按需要取平方值的中间几位作为散列地址 。这是因为：计算平方之后的中间几位和关键字中的每一位都相关 ， 所以不同的关键字会以较高的概率产生不同的散列地址 。
推荐阅读
- 茯茶九大功效,茯茶是什么茯茶和黑茶是一回事吗
- Python中的数据结构
- 喝茶须知九大常识,青砖茶的九大功效
- 24 张图彻底弄懂九大常见数据结构
- 实现树结构的基本算法和相应的数据结构
- 九大经典算法思想及其典型应用
- 数据结构到底是个啥？轻松学习八类数据结构
- 九大凤凰单丛的茶叶知识
- 搜索引擎背后的经典数据结构和算法
- 保靖黄金茶的九大茶叶知识
