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

+关注继续查看

C/C++精通，数据结构算法熟悉或者精通，LINUX系统编程熟悉或者精通，数字逻辑等。

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

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

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

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

1、简单左转如：

2、简单右转如：

3、先左转再右转

4、先右转再左转

/**********************************************************************//**
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指针的每条路径都包含相同数目的黑结点。

http://blog.csdn.net/v_july_v/article/details/6105630
http://blog.csdn.net/eson_15/article/details/51144079

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. */

0 0
【高阶数据结构】AVL树（动图详解）
【高阶数据结构】AVL树（动图详解）
0 0
【数据结构之旅】「AVL平衡树专项」带你领略常用的AVL树与红黑树的奥秘（规则篇）
【数据结构之旅】「AVL平衡树专项」带你领略常用的AVL树与红黑树的奥秘（规则篇）
0 0
C++ 第八节&数据结构 第七节 ——二叉搜索树 AVL树 红黑树（底层原理图+模拟实现）

0 0

0 0

0 0
Java数据结构——平衡二叉树(AVL树)
Java数据结构——平衡二叉树(AVL树)
0 0
《恋上数据结构第1季》平衡二叉搜索树、AVL 树
《恋上数据结构第1季》平衡二叉搜索树、AVL 树
0 0
+关注

10年ORACLE/MYSQL DBA，有一定C/C++基础