目录

折半查找：

有序二叉树：要求其左边的节点值小于父节点，右边的节点值大于父节点。

红黑树

1.认识红黑树的特性

 2.从2-3-4树到红黑树

 3.通过2-3-4树构建红黑树

---

 无序数组中查找某一个值——时间复杂度为 O(n)。

想办法降低时间复杂度。把它变有序。

O(logn)    : 循环减半

折半查找：

最左边定义一个left，最右边定义一个right。

left加right除以2，就是中间值mid。

真实查找一个数值4，4和3对比，3小于4，即把left指向3，mid指向5。就相当于 折掉了左边一半的数据（0 1 2）。 

现在 5 和 4相比，5大于4。right指向5，mid指向4。这就把剩下的一半的一半折掉了。

这样复杂度就是logn级别。

用户输入的数据一般都是无序的，我们想把这个数据变得有序。从无序到有序的状态用什么？

八大排序最短的时间复杂度也是O(nlogn)。

本身查找是O(n). 八大排序是行不通的。

能想办法达到O(1)级别吗？

真正能达到O(1)级别复杂度,是数组通过下标来获取数据。

定义一个空数组。

输入一个无序的数据，这次经过一个算法的计算，这个算法可以获取这个数组存放的位置，比如计算方式为  n % arr.length    得到的值就是 存放数据的下标。

5处于10的余数5,11除以10为1等等依次计算存放。

  这个计算是一个O(1)级别的复杂度。

此时假如还有数据 15，那么把它放哪里？

通过算法的运算得到了多个拥有相同下标的数据。

假设定义一个二维的数组，也会出现新的问题，数组有一个大的限制，数组的大小在创建时就确定了。 如果其中下标相同的数很多，还要开辟很多内存空间，多余的就浪费了。。

 

 所以横向存储不太合适，竖向存储也不太合适。

此时怎么解决？

毫无疑问，用链表！

加一条链表就可以，不用再创建内存空间了。

  查找这一条链，是O(1)级别的时间复杂度，但是在链表上查询时间复杂度又回到O（n）级别了。

能不能降低时间复杂度？

树

有序二叉树：要求其左边的节点值小于父节点，右边的节点值大于父节点。

 当前有一棵树如上图：（这就是一个有序二叉树）

链表（本质：链式存储）可以变为有序二叉树。

树也是链式存储，不同的是此时我们的是单链表，只能指向下一个节点，而在树上相当于特殊的链表，一个节点指向两个子节点。

所以时间复杂度便可以降为logn。

查找4，从上到下查找，5比4大，就甩掉右边的数据，到3和4比，3小于 4，继续往右查找到4。这也是循环减半，即logn。

验证有序二叉树真的时间复杂度为logn吗？

把一组数据，画为有序二叉树。

右边看就是一个 链表：O(n)

真实情况下O(logn)-O(n)，除非用户按非常标准的树的logn构建有序二叉树是logn,否则不是。不稳定

如何解决有序二叉树不稳定的问题？

 平衡二叉树    ———————>  有序二叉树的基础上进行操作，要求左右子树的高度差的绝对值不超过1（但用户输入的很有可能超过1）

一旦左右子树高度差超过1，就需要平衡调整。

四个调整策略：

LL  LR  RL  RR

 还用之前那个有序二叉树：

 插入0造成了4和5都不平衡，但是要选择离造成不平衡节点最近的。

LL型旋转：

 最后还是有序的。

最后结果：

 平衡二叉树能保证程序稳定在logn级别上。

红黑树

1.认识红黑树的特性

1.每个节点不是红色就是黑色

2.根节点是黑色

3.每个叶子节点(NIL节点，空节点)是黑色的

4.如果一个节点是红色的，则他的子节点必须是黑色的

5.从一个节点到该节点的所有子孙节点的所有路径上包含相同数目的黑色节点

内存最优二叉树

特殊说明：我们每次新插入的节点都是红色

将插入的节点写为红色，就不会违背特性5，少违背一条特性，也就意味着我们需要处理的情况也就越少。

 2.从2-3-4树到红黑树

2-3-4树的查询操作像普通的二叉搜索树一样，非常简单，但由于其结点元素数不确定，在一些编程语言中实现起来并不方便，实现一般使用它的等同——红黑树。

至于为什么说红黑树是 2-3-4树的一种等同呢，这是因为 2-3-4树的每一个结点都对应红黑树的一种结构，所以每一棵 2-3-4树也都对应一棵红黑树，下图是 2-3-4树不同结点与红黑树子树的对应。

 3.通过2-3-4树构建红黑树

• 新插入的结点颜色为红色，这样才可能不会对红黑树的高度产生影响。
• 2-结点对应红黑树中的单个黑色结点，插入时直接成功（对应 2-结点升元）。
• 3-结点对应红黑树中的黑+红子树，插入后将其修复成 红+黑+红 子树（对应 3-结点升元）；
• 4-结点对应红黑树中的红+黑+红子树，插入后将其修复成红色祖父+黑色父叔+红色孩子子树，然后再把祖父结点当成新插入的红色结点递归向上层修复，直至修复成功或遇到 root 结点；

 如上图所示，虽然向红黑树中插入了一个新结点，但由于旋转和变色，子树的高度保持不变。