二叉树

表示（存储）一颗二叉树

两种方法，一种是基于指针或引用的二叉链式存储法，一种是基于数组的顺序存储法。

链式存储法

每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。

顺序存储法

基于数组，把根节点存储在下标i=1的位置，节点X存储在数组中下标i的位置，下标为2 i的位置存储的就是左子节点，下标为2 i+1的位置存储的就是右子节点。反过来下标i / 2的位置就是父节点。这样，只要知道根节点的位置（一般为了方便计算，根节点会存储在下标为1的位置）就可以把整颗树串起来。

如果是非完全二叉树，其实会浪费比较多的数组存储空间。

如果某棵二叉树是一棵完全二叉树，用数组存储是最节省内存的一种方式。因为数组存储不需要像链式存储一样额外存储左右子节点的指针。这也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

堆其实就是一种完全二叉树，最常用的存储方式就是数组。

二叉树遍历

前序是指先遍历该节点，再遍历左，右节点。后序中序同理。
二叉树的前中后序遍历就是个递归的过程。

二叉树遍历的时间复杂度为：
从遍历顺序图可以看出，每个节点最多会被访问两次，所以遍历的时间复杂度跟节点的个数n成正比，也就是二叉树遍历的时间复杂度为O(n)。

二叉查找树

二叉查找树最大的特点就是支持动态数据集合的快速插入删除查找操作。

二叉查找树要求，在树中的任意一个节点，其左子树中每个节点的值，都要小于这个节点的值，而右子树节点的值。

1.二叉查找树的查找操作

2.二叉查找树的插入操作

插入操作类似于查找操作。

二叉查找树的删除操作

删除操作比较复杂，针对要删除节点的子节点个数的不同，分为三种情况来处理。

第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为nll。比如图中的删除节点55。

第二种情况是，如果要删除的节点只有一个子节点(只有左子节点或者右子节点)，我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点13。

第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点(如果有左子结点，那就不是最小节点了)，所以，我们可以应用上面两条规则（情况一二）来删除这个最小节点。比如图中的删除节点18。

实际上，关于二叉查找树的删除操作，还有个非常简单、取巧的方法，就是单纯将要删除的节点标记为“已删除”，但是并不真正从树中将这个节点去掉。这样原本删除的节点还需要存储在内存中，比较浪费内存空间，但是删除操作就变得简单了很多。而且，这种处理方法也并没有增加插入、查找操作代码实现的难度。

二叉查找树的其他操作

中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(n)，非常高效。二叉查找树也叫二叉排序树。

支持重复数据的二叉查找树

在实际开发中，二叉查找树中存储的都是对象，利用对象的某个字段作为键值(key)来构建二叉查找树，对象中其他字段叫作卫星数据。

如果存储的两个对象键值相同，有两个解决方法。

第一种方法比较容易。二又查找树中每一个节点不仅会存储一个数据，通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。

第二种不好理解但是更加优雅。每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。

当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。

对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

二叉查找树的时间复杂度分析

显然，极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求。我们需要构建一种不管怎么删除、插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的二叉查找树，这就是平衡二叉查找树。平衡二叉查找树的高度接近logn,所以插入、删除、查找操作的时间复杂度也比较稳定，是O(logn)。

散列表与二叉查找树

散列表的插入、删除、查找操作的时间复杂度做到常量级O(1),而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是O(logn)。
相比散列表二叉查找树的优势：

散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列。
散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)。
笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比logn小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
最后，为了避免过多的散列冲突,散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，会浪费一定的存储空间。

综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。在实际的开发过程中，需要结合具体的需求来选择使用哪一个。

红黑树

红黑树是一种平衡二叉查找树

平衡二叉查找树

定义：二叉树中任意一个节点的左右子树高度相差不能大于1.

最先发明出的平衡二叉查找树是AVL树，严格符合定义。是一种高度平衡的二叉查找树。

很多平衡二叉查找树其实并没有严格符合上面的定义(树中任意一个节点的左右子树的高度相差不能大于1)。发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

定义一颗红黑树

红黑树：

根节点是黑色的;
每个叶子节点都是黑色的空节点(NIL)，也就是说，叶子节点不存储数据;
任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的;
每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点;

暂时先将黑色的空的叶子节点都省略掉了。

红黑树是近似平衡的

“平衡” 的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

红黑树的高度：

完全二叉树的高度近似log2n, 这里的四叉“黑树”的高度要低于完全二叉树，所以去掉红色节点的“黑树”的高度也不会超过logn。

加上红色节点，最长路径不会超过2logn，也就是红黑树的高度近似2logn。

红黑树的高度只比高度平衡的AVL树的高度(logn)仅仅大了一倍,在性能上,下降得并不多。这样推导岀来的结果不够精确,实际上红黑树的性能更好。

Treap、Splay Tree,绝大部分情况下操作的效率都很高，但是也无法避免极端情况下时间复杂度的退化。尽管这种情况出现的概率不大，但是对于单次操作时间非常敏感的场景来说并不适用。
AVL树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊, AVL树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用AVL树的代价就有点高了。
红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比AVL树要低。所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，更倾向于这种性能稳定的平衡二叉查找树。

实现红黑树的基本思想

红黑树的平衡过程跟魔方复原非常神似，大致过程就是:遇到什么样的节点排布，就对应怎么去调整。只要按照这些固定的调整规则来操作，就能将一个非平衡的红黑树调整成平衡的。

在插入、删除节点的过程中，第三、第四点要求可能会被破坏，“平衡调整”,实际上就是要把被破坏的第三、第四点恢复过来。

左旋与右旋：

插入操作的平衡调整

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。关于插入操作的平衡调整，有这样两种特殊情况。

如果插入节点的父节点是黑色的，就什么都不用做，仍然满足红黑树的定义。
如果插入的节点是根节点，则直接改变它的颜色，把它变成黑色就可以了。

除此之外，其他情况都会违背红黑树的定义，于是就需要进行调整，调整的过程包含两种基础的操作:左右旋转和改变颜色。

红黑树的平衡调整过程是一个迭代的过程。正在处理的节点叫作关注节点。关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。

新节点插入后，如果红黑树平衡被打破，一般会有三种情况，需要根据每种情况的特点不断调整，让红黑树继续符合定义，即继续保持平衡。

case 1:如果关注节点是a，叔叔节点d是红色，依次执行下面操作：

将关注节点a的父节点b、叔叔节点d的颜色都设置成黑色;
将关注节点a的祖父节点c的颜色设置成红色;
关注节点变成a的祖父节点c;
跳到CASE 2或者CASE 3。

case2:如果关注节点是a，它的叔叔节点d是黑色，关注节点a是其父节点b的右子节点，依次执行下面操作：

关注节点变成节点a的父节点b
围绕新的关注节点b左旋
跳到CASE3

CASE 3:如果关注节点是a,它的叔叔节点d是黑色，关注节点a是其父节点b的左子节点，依次执行下面的操作:

围绕关注节点a的祖父节点c右旋;
将关注节点a的父节点b、兄弟节点c的颜色互换。
调整结束

删除操作的平衡调整

删除操作的平衡调整分为两步。
第一步是针对删除节点初步调整。初步调整是保证整颗红黑树在一个节点删除之后，仍然满足最后一条定义的要求，就是每个节点，从该节点到达其可达叶子节点的所有路径都包含相同数目的黑色节点。
第二步是针对关注节点进行二次调整，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。

针对删除节点初步调整

经过初步调整后，为了保证满足红黑树定义的最后一条要求，有些节点会被标记成两种颜色。有些节点会被标记成两种颜色，“红黑”或“黑黑”。

case1：如果要删除的节点时a，它只有一个子节点b。依次进行下面的操作：

删除节点a,并且把节点b替换到节点a的位置，这一部分操作跟普通的二叉查找树的删除操作一样。
节点a只能是黑色，节点b也只能是红色，其他情况均不符合红黑树的定义。这种情况下，把节点b改为黑色。
调整结束，不需要进行二次调整。

CASE 2:如果要删除的节点a有两个非空子节点，并且它的后继节点就是节点a的右子节点c。

太多且复杂，有的放矢不记了☺

要求叶子节点为黑的原因

之所以有这么奇怪的要求就是为了实现起来方便，只要满足这一条要求，在任何时刻，红黑树的平衡操作都可以归结为我们刚刚讲的那几种情况。

给红黑树添加黑色的空的叶子节点，不会比较浪费存储空间。虽然在讲解或者画图的时候，每个黑色的、空的叶子节点都是独立画出来的。实际上，在具体实现的时候，只需要共用一个黑色的、空的叶子节点就行了。

红黑树要点

第一点，把红黑树的平衡调整的过程比作魔方复原，不要过于深究这个算法的正确性。

第二点,找准关注节点,不要搞丢、搞错关注节点。

第三点，插入操作的平衡调整比较简单，但是删除操作就比较复杂。针对删除操作，有两次调整，第一次是针对要删除的节点做初步调整，让调整后的红黑树继续满足第四条定义，“每个节点到可达叶子节点的路径都包含相同个数的黑色节点”。但是这个时候，第三条定义就不满足了，有可能会存在两个红色节点相邻的情况。第二次调整就是解决这个问题，让红黑树不存在相邻的红色节点。