详解红黑树和TreeMap的方法原理

       参考算法导论  本文篇幅可能较长需要读者慢慢理解，一步一步看。

       什么是红黑树？

       我们要了解红黑树就必须知道红黑树是什么？红黑树的红和黑是什么意思？红黑树能解决什么样的问题？红黑树解决这样问题采用的是什么方法？如果带着这样的问题去了解红黑树那么就有助于我们清楚的认识红黑树。

      首先对二叉树进行讲解（了解二叉树的同学可以跳过）

      首先二叉树这种数据结构是为了解决数据进行检索时快速的找到我们要找的数据。它区别于链表在于检索数据时所付出的时间代价是不一样的。

        

              从上图我们可以清楚的了解什么样的数据选择什么样的结构。比如我们要在集合{1,2,3,4····10000}中查找整数n，那么链表最坏的情况下的时间复杂度为O(n)，而二叉树（二叉树建立的合理矮胖矮胖的）则只需要O(lg n）。而数据量越来越大时二叉树表现得越好。

            但是当二叉树的数据分布是这个样子时那它和链表的区别就很小了。

            

            这样的二叉树结构显然不是我们想要的，我们想要的是那种深度越小越好的，也就是矮矮胖胖的。

           平衡二叉树

           平衡二叉树通过在给元素插入时改变节点数据来使树的结构变得矮平。

           

             从b变为a就是平衡二叉树的作用。

             那么平衡二叉树和红黑树有什么关系呢？红黑树就是一种平衡二叉树，它是通过改变元素节点时通过左旋和右旋进行的。那么还是倒回来，红是啥？黑是啥？左旋是啥？右旋是啥？这都tm是啥？哈哈。要想了解就要了解红黑树相关的另一种2-3树，红黑树是通过2-3树演化而来。

           2-3平衡树

           首先我们看一看2-3-4平衡树的结构。

           

            其中

                  根节点5是一个2-节点   2-节点就是有一个元素和两个儿子

                  子节点7 9是一个3-节点  3-节点就是有两个元素和三个儿子

                  子节点10  11  12 是一个4-节点 4-节点就是有三个元素四个儿子

             这里我们要研究的2-3节点没有4-节点那么为什么要看2-3-4平衡树呢？

             原因就是我们要解决的关键问题：插入元素时，2-3平衡树是如何进行平衡的？

             那么我们把插入进行分类：

                     1.元素插入2-节点           

                     2.元素插入3-节点

                             1.3-节点没有父节点

                             2.3-节点有一个2-节点的父节点

                             3.3-节点有一个3-节点的父节点

                   我们一种一种分析。（下图是依次插入数据）