【红黑树学习-2】二叉树原理解析

二叉树：树的每个节点最多只能有两个子节点。

图1

图2

二叉搜索树

如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。

二叉搜索树要求：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。

二叉搜索树-查找节点：

查找某个节点，我们必须从根节点开始查找。
　　①、查找值比当前节点值大，则搜索右子树；
　　②、查找值等于当前节点值，停止搜索（终止条件）；
　　③、查找值小于当前节点值，则搜索左子树；

二叉搜索树-插入节点：

要插入节点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性，
待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，
反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置。

二叉搜索树-遍历节点：

遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历，中序遍历和后序遍历。而二叉搜索树最常用的是中序遍历。
　　①、中序遍历:左子树——》根节点——》右子树
　　②、前序遍历:根节点——》左子树——》右子树
　　③、后序遍历:左子树——》右子树——》根节点

二叉搜索树-查找最大值和最小值

要找最小值，先找根的左节点，然后一直找这个左节点的左节点，直到找到没有左节点的节点，那么这个节点就是最小值。
同理要找最大值，一直找根节点的右节点，直到没有右节点，则就是最大值。

二叉搜索树-删除节点：

删除节点是二叉搜索树中最复杂的操作，删除的节点有三种情况，前两种比较简单，但是第三种却很复杂。
1、该节点是叶节点（没有子节点）
2、该节点有一个子节点
3、该节点有两个子节点

①、删除没有子节点的节点

要删除叶节点，只需要改变该节点的父节点引用该节点的值，即将其引用改为 null 即可。

②、删除有一个子节点的节点

删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可。

③、删除有两个子节点的节点

当删除的节点存在两个子节点，那么删除之后，两个子节点的位置我们就没办法处理了。
既然处理不了，我们就想到一种办法，用另一个节点来代替被删除的节点，那么用哪一个节点来代替呢？

我们知道二叉搜索树中的节点是按照关键字来进行排列的，某个节点的关键字次高节点是它的中序遍历后继节点。
用后继节点来代替删除的节点，显然该二叉搜索树还是有序的。

那么如何找到删除节点的中序后继节点呢？

其实我们稍微分析，这实际上就是要找比删除节点关键值大的节点集合中最小的一个节点，只有这样代替删除节点后才能满足二叉搜索树的特性。
后继节点也就是：比删除节点大的最小节点。

④、删除有必要吗？

通过上面的删除分类讨论，我们发现删除其实是挺复杂的，那么其实我们可以不用真正的删除该节点，只需要在Node类中增加一个标识字段isDelete，
当该字段为true时，表示该节点已经删除，反之则没有删除。这样删除节点就不会改变树的结构了。
影响就是查询时需要判断一下节点是否已被删除。

二叉搜索树-时间复杂度分析：

1.回顾经典-二分查找算法
[1,2,3,4,5,6,7,8,9。。。。。。。100]
暴力算法：运气好时 性能不错，运气不好时 性能暴跌…
二分查找算法：数据源必须是有序数组，性能非常不错，每次迭代查询可以排除掉一半的结果。

2.二分查找算法最大的缺陷是什么？
强制依赖 有序数组，性能才能不错。

3.数组有什么缺陷？
没有办法快速插入，也没有办法扩容

4.那怎么才能拥有二分查找的高性能又能拥有链表一样的灵活性？
二叉搜索树！！
5.二分查找算法时间复杂度推算过程

从上表可以看出N/(2^K)
肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，
也就是是查到剩余最后一个数才查到我们想要的数据，也就是
N/(2^K)=1 => 2^K = N => K = log2 (N) => 二分查找算法时间复杂度：O(log2(N)) => O(logN)

普通二叉搜索树致命缺陷：

这颗二叉树查询效率咋样呢？
O(N)

怎么解决 二叉搜索树 退化成线性链表的问题？
如果插入元素时，树可以自动调整两边平衡，会保持不错的查找性能。

AVL树简介：

AVL树有什么特点？
1、具有二叉查找树的全部特性。
2、每个节点的左子树和右子树的高度差至多等于1。

符合规范

错误

平衡树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了！（插入或者删除时，会发生左旋、右旋操作，使这棵树再次左右保持一定的平衡）
如何构建AVL树

为什么有了平衡树还需要红黑树？

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，
因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，
几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树！！！