本篇博客我会重点介绍对红-黑树的理解，重点介绍红-黑树的查找，这里我们将要讨论的算法称为自顶向下插入，也就是把沿着树向下查找插入点
Ⅰ、平衡树和非平衡树
平衡树和非平衡树：当插入一组数据关键字是按照升序或者降序插入的话此时就是集中最极端的不平衡树，此时也可看做是一个链表此时对于此树的查找的时间复杂度为O(N),所以搜索不平衡树的时间复杂度介于平衡树时间复杂度O(logN)和O(N)之间时间具体取决于树的不平衡度。
Ⅱ、红-黑树规则
接下来我们要讨论的红-黑树具有以下几个特征（红-黑树规则）：
1.每一个节点不是红色就是黑色
2.根总是黑色的
3.若节点是红色的，则它的子节点必须全是黑色的（反过来就不一定成立）
4.从根到叶节点或空子节点的每一条路径必须包含相同数目的黑色节点
第四条中的“空子节点”指的是有右子节点的节点可能接左子节点的位置，或者说有左子节点的节点可能接右子节点的位置。就是非叶节点本可能有，但是实际上没有的那个子节点（若节点只有右子节点，那么空缺的左子节点就是空子节点，反之亦然）下图中50→25→25的右子节点（空子节点）黑色高度为1，从根到6以及到75的黑色节点数都为2，这样就违背了规则4，此树到叶节点的黑色节点数相同，但是有一个空子节点的黑色节点数为1所以此树不是红-黑树。
从根节点到叶节点路径上面的黑色节点数目称为黑色高度，所以上面的规则四的另一种陈述方法是：所有从根到叶节点路径上的黑色高度必须相同。
为了满足红黑树规则我们可能会使用到下面两种方式来进行修正，从而使一棵树满足红黑树规则，
改变节点颜色
执行旋转操作
为什么保证上面四个红-黑树规则就能保证红-黑树是平衡树呢？从红黑树规则分析我们可以得到若一棵树超过了两层不平衡怎这棵树则不可能满足红-黑树规则，超过两层不平衡则表明有路径的节点数比另外的路径的节点数多一个以上，多出来的要么有更多的黑色节点，若这样则违背了红-黑树规则4，要么至少有两个相邻接的红色节点，这样就违背了红色节点的子节点必须全部是黑色节点。
Ⅲ、树的旋转：
利用树的旋转来重新排列一些节点，来平衡一棵树，旋转必须要做到两件事情：
使一些节点上升，一些节点下降，帮助树平衡
保证不破坏二叉搜索树的特征（由于搜索算法依赖此特征，不然就没意义）
上面利用红黑树的颜色规则和节点的颜色变化只是有助于决定何时执行旋转。光改变颜色并不能让分树达到平衡，旋转才是让树平衡的关键操作，所以我们要好好理解树的旋转操作；做旋转的时候要注意做右旋顶点必须要有一个左子节点，左旋顶端必须要有右子节点，不然旋转后顶点会没有节点，接下来我们看下图的一个简单的旋转：
上图中a→b我们可以看到该树进行了一次右旋，a图中节点37称为顶端节点50的内侧子孙（节点12是外侧子孙点），对内侧子孙而言，如果他是上移的节点的子节点，它就必须要断开和父节点的连接并且重新连接到它以前的爷爷节点之上，就好像自己成为了自己的叔叔一样。上图是旋转过程中单节点的位置变换，上面我们说的内侧子孙也可以是一棵子树，下图我们展示了假如是子树的节点的一个移动情况，大致的原理差不多是相通的。
上图中的树进行了一次右旋，做了以下几个事情：
顶端节点（50）移动到他右子节点的位置
顶端节点的左子节点（25）移动到顶端的位置上
以节点12为根的整棵子树都向上移动
因节点为37为根的整棵子树横向移动，成为节点50的左子节点
以节点75为根的整棵子树向下移动