数据结构 AVL树和红黑树的定义

这里只是大概描述了一下AVL的树的插入，以及红黑树的定义，并没有实现为代码，这个在以后的学习中如果遇到会
更加深入的学习，因为我学习数据结构的目的在于如果学习INNODB代码的时候遇到不太陌生，但是在INNODB代码
中并为找到AVL树的应用，而红黑树的应用仅仅用于数据恢复的时候，所以占时先了解概念和简单的操作，如果日后
需要再深入学习，其实数据库也是各种各样的数据结构的综合应用，
比如INNODB：大量的链表，伙伴算法，B+树，红黑树.......
其实学习源代码很多先决条件至少包含
C/C++精通，数据结构算法熟悉或者精通，LINUX系统编程熟悉或者精通，数字逻辑等。
这些东西对于我来说都要从头学习，其中任何一门弄到精通都不是易事，而综合起来
更是难于登天，对我这个门外汉更难，所以很多东西我只能了解，学习到在深入研究，
这些东西我已经学习了1年半了这一年半基本没看数据库的东西全在看这些，还有基本有一点
熟悉了，但是时间对我来说很少，不能像专业的开发一样专心的研究这些，因为我只是
一个DBA，还是一个曾经不懂代码的ORACLE DBA，如果一直研究这些数据库的老本都要
忘光，失去了竞争力，准备给自己2年的时间还剩下半年了，2年后继续研究数据库如果遇
到不懂的再补补，至少经过这一段时间学习学习到了很多以前不懂的东西，能够从一个软件
的角度来看待数据库，这就是进步。
好吧还是言归正传

AVL树(self-balancing binary search tree)他就为了解决排序二叉树(BST)的补足，

也就是BST树没有再平衡原理会出现某些极端情况，如下插入1 2 3 4 5 为顺序的

数据就会出现如下：

可以看到排序二叉树搜索4和5的时候，搜索的层次明显高于平衡二叉树，

AVL树通过自我旋转来完成再平衡原理，其中是根据最小不平衡子树的

平衡因子来判断旋转的方向，所谓不平衡因子就是 左子树深度-右子树深度

的差值，平衡二叉树一个重要的概念就是各个节点的平衡因子只能是-1,0,1

三个值，如果有多个不平衡的子树那么需要找到最小的不平衡子树为旋转

的基础，如果解决了最小不平衡子树的问题其他节点的不平衡性也就解决了

总体的原则

1、如果平衡因子为负数 则进行左旋转(逆时针)

2、如果平衡因子为正数 这进行右旋转(顺时针)

如下图加深理解

但是需要分为4种情况

1、简单左转如：

节点1的平衡因子为-2 需要逆时针左旋转

2、 简单右转如：

 

节点3平衡因子为2需要顺时针右转

3、 先左转再右转
可以看到节点的5的平衡因子为2，整体需要顺时针右旋转，但是我们发现节点1平衡因为-1，和结点的5的平衡因子符号不同，我们需要对节点进行逆时针左旋然后在对5进行右旋

 

这个时候节点3出现了3个分支，节点4需要进行处理，我们知道实际上4是3的直接前驱，那么就行如下变化：

4、 先右转再左转

可以看到节点2平衡因子为-2，整体需要逆时针左旋转，但是我们发现节点6的平衡因子为1，和结点2的平衡因为符号不同，我们需要先对节点6进行右旋，然后对节点2进行左旋转

这个时候节点4出现了3个分支，节点4需要进行处理，我们知道实际上3是2的直接后继，那么就行如下变化：

其他操作先不讨论，下面了解一下红黑树我用INNODB中的注释给出：
/**********************************************************************//**
Definition of a red-black tree
==============================
A red-black tree is a binary search tree which has the following
red-black properties:
   1. Every node is either red or black.
   2. Every leaf (NULL - in our case tree->nil) is black.
   3. If a node is red, then both its children are black.
   4. Every simple path from a node to a descendant leaf contains the
      same number of black nodes.  
   from (3) above, the implication is that on any path from the root
   to a leaf, red nodes must not be adjacent.
   However, any number of black nodes may appear in a sequence.
 */

/** Red black tree color types */
enum ib_rbt_color_t {
IB_RBT_RED,
IB_RBT_BLACK
};

/** Red black tree node */
struct ib_rbt_node_t {
ib_rbt_color_t color; /* color of this node */
ib_rbt_node_t* left; /* points left child */
ib_rbt_node_t* right; /* points right child */
ib_rbt_node_t* parent; /* points parent node */
char value[1]; /* Data value */
};

实际上中文的限制就是：
1、 每个结点要么是红的要么是黑的。  
2、根结点是黑的。  
3、每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。  
4、如果一个结点是红的，那么它的两个儿子都是黑的。  
5、对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。 
由于这些限制的出现使得红黑树也是一种平衡的二叉树，在LINUX中也有应用，他的主要
操作也是插入，平衡，删除，平衡等。
具体可以参考：
http://blog.csdn.net/v_july_v/article/details/6105630
http://blog.csdn.net/eson_15/article/details/51144079
已经MYSQL innodb 源码中的红黑树实现，我大概看了一下插入和旋转也不是很难主要是逻辑要清楚。
这里就不具体解释了，因为我也是了解了一下。
在大概说一下INNODB中的红黑树是恢复的时候才用到如下注释：
ib_rbt_t* flush_rbt; /*!< a red-black tree is used
exclusively during recovery to
speed up insertions in the
flush_list. This tree contains
blocks in order of
oldest_modification LSN and is
kept in sync with the
flush_list.
Each member of the tree MUST
also be on the flush_list.
This tree is relevant only in
recovery and is set to NULL
once the recovery is over.
Protected by flush_list_mutex */

Inserts a modified block into the flush list in the right sorted position.
This function is used by recovery, because there the modifications do not
necessarily come in the order of lsn's. */