1. 首页
  2. IT资讯

数据结构 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 为顺序的

数据就会出现如下:
数据结构 AVL树和红黑树的定义

可以看到排序二叉树搜索45的时候,搜索的层次明显高于平衡二叉树,

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

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

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

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

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

总体的原则

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

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

如下图加深理解

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

但是需要分为4种情况

1、简单左转如:

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

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

2、简单右转如:

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

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

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

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

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

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

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

4、先右转再左转
数据结构 AVL树和红黑树的定义

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

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

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

其他操作先不讨论,下面了解一下红黑树我用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. */

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7728585/viewspace-2127419/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:深沉的少年,转转请注明出处:http://www.cxybcw.com/183879.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code