分类： LINUX
2011-06-09 14:54:05
谨以此文纪念过往的岁月
一. 前言
在内核中遍布着种种数据结构，其中比较常见的是链表，二叉树，红黑树等常见的数据结构。对于软件专业出身的人一定会很熟悉，不过对于我们这些半路出家的人就比较难理解了。谨以此文来记录鄙人的一些学习过程。下面有很多都是从网上copy的，请各位见谅。
二. 二叉树
什么是树？额！不说了，你看看现实中的树，就知道这是一个什么样的数据结构了。在其中比较有名的是二叉树，什么是二叉树？额！就是只有两个节点的树。
这样的节点可以组织成下图所示的各种形态。
图 26.9. 二叉树的定义和举例
二叉树可以这样递归地定义：
上图举例示意了几种情况。
链表的遍历方法是显而易见的：从前到后遍历即可。二叉树是一种树状结构，如何做到把所有节点都走一遍不重不漏呢？有以下几种方法：
图 26.10. 二叉树的遍历
前序（Pre-order Traversal）、中序（In-order Traversal）、后序遍历（Post-order Traversal）和深度优先搜索的顺序类似，层序遍历（Level-order Traversal）和广度优先搜索的顺序类似。
前序和中序遍历的结果合在一起可以唯一确定二叉树的形态，也就是说根据遍历结果可以构造出二叉树。过程如下图所示：
图 26.11. 根据前序和中序遍历结果构造二叉树
上面的摘自：
三．排序二叉树
排序二叉树（BST，Binary Search Tree）具有这样的性质：对于二叉树中的任意节点，如果它有左子树或右子树，则该节点的数据成员大于左子树所有节点的数据成员，且小于右子树所有节点的数据成员。排序二叉树的中序遍历结果是从小到大排列的。排序
排序二叉树是一种特殊的二叉树。
如何创建一个排序二叉树呢，一种采用递归的方法就是
CNode *Insert(CNode *node,unsigned char value){
if(node == NULL)
return new CNode(value);
if(node->FindData()>value){
node->SetLeft(this->Insert(node->FindLeft(),value));
}
else{
node->SetRight(this->Insert(node->FindRight(),value));
}
return node;
}
另外一种就是不采用递归的方法就是
CNode *Insert_node(CNode *node,unsigned char value){
CNode *tmp;
CNode *tmp_bak;
if(node == NULL){
node = new CNode(value);
return node;
}
tmp = node;
while(tmp){
tmp_bak = tmp;
if(value
tmp = tmp->FindLeft();
}
else if(value>tmp->FindData()){
tmp = tmp->FindRight();
}
else if(value == tmp->FindData())
return NULL;
}
if(value
tmp = new CNode(value);
tmp_bak->SetLeft(tmp);
}
else if(value>tmp_bak->FindData()){
tmp = new CNode(value);
tmp_bak->SetRight(tmp);
}
return node;
}
上面的code比较粗糙，各位看官不要喷啊！排序记住一点就排序二叉树就是中序查询的时候，其值是顺序的。这个比较好理解。不过上面构造排序二叉树的办法有个很大的毛病就是，输入参数的不同会导致构造出的二叉树的深度不一样，而导致查询的时候，其使用的时间不同。在这里AVL树就出现了，通过对数的调整，尽量使数变的平衡。
五．平衡排序二叉树
所谓的平衡是指树的左节点深度与右节点深度差值不超过1，一般情况下，不能做到完全平衡，只要做到大概平衡的时候就够了。
AVL树又称为高度平衡的二叉搜索树，是1962年由两位俄罗斯数学家G．M．Adel’ son－Vel'sky和E．M．Landis提出的。引人它的目的，是为了提高二叉搜索树的效率，减 少树的平均搜索长度。为此，就必须向二又搜索树每插人一个新结点时调整树的结构，使 得二又搜索树保持平衡，从而尽可能降低树的高度，减少树的平均搜索长度。
一、AVL树的定义：一棵ALV树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树 都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。
图（a）给出的二叉搜索树不是AVL树，根的右子树的高度为l，而左子树的高度 为4。图（b）给出的二叉搜索树是AVL树。在图中每个结点旁边所注的数字结出 该结点右子树的高度减去左子树的高度所得的高度差。称这个数字为结点的平衡因子(balance factor)。 根据 AVL树的定义，任一结点的平衡因子只能取一1，0和 1。如果一个结点的平衡因子的绝对值大于1，则这棵二叉搜索树就失去了平衡，不再是AVL树了。
如果一棵二叉搜索树是高度平衡的，它就成为ＡＶＬ树，如果它有N个结点，其高度可保持在Ｏ(log2n），平均搜索长度也可保持在Ｏ(log2n）。
二、平衡化旋转
如果在一棵原本是平衡的二又搜索树中插入一个新结点，造成了不平衡。此时必须 调整树的结构，使之平衡化。平衡化旋转有两类：单旋转（左旋和右旋）和双旋转（左平衡 和右平衡）。给出加人了平衡化旋转操作的AVL一树的类声明如下。每当插人一个新结点时，AVL树中相关结点的平衡状态会发生改变。因此，在插人 一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点左、右子树的高度差。 如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径 取直接下两层的结点。如果这三个结点处于一条直线上，则采用单旋转进行平衡化；如果 这三个结点处于一条折线上，则采用双旋转进行平衡化。
单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不 平衡的形状相关。而双旋转分为先左旋后右旋和先右旋后左旋两类。
1．左单旋转（rotate left）
如果在插入新结点之前AVL树的形状如图7．18（a）所示。图中的大写字母用来指 明结点，矩形框表示结点的子树，其中的字母h给出子树的高度。若h=一1，则B，C和 D都是空指针；若h≥0，则这三个结点在树中实际存在。此时树满足AVL树的条件，是 高度平衡的二叉搜索树。接下来，如果在子树E中插人一个新结点，该子树的高度增加1 导致结点A的平衡因子变成 十2，如图 7．18（b）所示，出现不平衡。
图7.18 左单旋转前后树的变化
沿插人路径检查三个结点A，C和E。它们处于一条方向为“＼”的直线上，需要做左 单旋转：以结点C为旋转轴，让结点A反时针旋转成为C的左子女，C代替原来A的位 置，原来C的左子女D转为A的右子女，旋转后的形状如图7．18（C）所示。通过检查各 个结点的平衡因子可知，树又恢复了平衡。
2．右单旋转（rotate right）
如果一棵 AVL树如图 19（a）所示，在结点 B的左子树D上插入新结点使其高度 由h增加到h＋l，导致结点A的平衡因子由一1增加到一2，造成了不平衡，见图 19（b）。为使树恢复平衡，从A沿刚才的插人路径连续取3个结点A，B和D，它们处于 一条方向为“／’的直线上，因此需要做右单旋转，以结点B为旋转轴，将结点A顺时针向 下旋转成为B的右子女，结点B代替原来结点A的位置，原来结点B的右子女转为结点 A的左子女。从而使树又达到平衡。
图19 右单旋转前后树的变化
3．先左后古双旋转（rotation left right）
双旋转总是考虑3个结点。设给出一棵AVL树，如图20（a）所示。图7．20中用 矩形框表示的所有子树都是AVL树。结点B和E的平衡因子为0而结点A的平衡因 子为一1。子树的高度h至少等于1。现在假设我们在子树F或G中插人一个新结点，则 该子树的高度增加 1，如图 20（b）将新结点插人到子树F中。此时结点A的平衡因子 变为一2，发生了不平衡。从结点A起沿插人路径选取3个结点A，B和E，它们位于一 条形如“ <”的折线上，因此需要进行先左后右的双旋转。首先以结点E为旋转轴，将结 点B反时针旋转，以E代替原来B的位置，使得B成为E的左子女，原来E的左子女F 转为B的右子女。参看图20（C），这恰为前面介绍的左单旋转。接下来，再以结点E为 旋转轴，将结点A顺时针旋转，使得A成为E的右子女，原来E的右子女G转为A的左 子女。这样又恢复了树的平衡。
图20 先左后右双旋转
4．先右后左双旋转（rotation right left）
如图21（a）所示。结点D和C的平衡因子为0而结点A的平衡因子为豆。子树 的高度h至少等于1。现在在子树F或G中插人一个新结点，则该子树的高度增加1，例如图21（b）将新结点插人到子树G中。此时结点A的平衡因子变为2， 发生了不平衡。 从结点 A起沿插人路径选取3个结点 A,C和D，它们位于一条形如“ ＞”的折线上，因此 需要进行先右后左的双旋转。首先做右单旋转：以结点D为旋转轴，将结点C顺时针旋转，以D代替原来C的位置，使得C成为D的右子女，原来D的右子女G转为 C的左子女。参看图7.21(c)。接下来做左单旋转：以结点D为旋转轴，将结点A反时针旋转，使得A成为D的左子女，原来D的左子女F转为A的右子女。 这样恢复了树的平衡，如图21(d)所示。
图21 先右后左双旋转
三、AVL树的插入和删除
在向一棵本来是高度平衡的AVL树中插人一个新结点时，应判断从插入结点到根 的路径L各结点的平衡因子的变化。如果树中某个结点的平衡因子的绝对值 |balance| ＞1，则出现了不平衡，需要从离插人结点最近的发生不平衡的结点沿插人路径做平衡化处理。
通常，AVL树的建立从一棵空树开始。通过输人一系列对象的关键码，根据前面所 讲的二叉搜索树的插人方法插人新结点。每插入一个结点后就应判断从该结点到根的路 径上是否有结点发生不平衡，如果有不平衡情况，利用平衡旋转方法进行树的调整，逐步建立AVL树。设输人关键码序列为{16，3，7，11，9，26，18，14，15｝，则插人和调整过程如图7．22所示。
为了在AVL树上执行删除，同样需要考虑平衡化旋转问题。给出步骤如下：
（1）如果被删结点X最多只有一个子女，那么问题比较简单。如果被删结点X有两 个子女，首先搜索X在中序次序下的直接前驱y（同样可以找直接后继）。再把结点y的 内容传送给结点x，现在问题转移到删除结点y，把结点y当作被删结点x。
（2）将结点x从树中删去。因为结点X最多有一个子女，可以简单地把X的双亲? 点中原来指向x的指针改指到这个子女结点；如果结点X没有子女，x双亲结点的相应指 针置为NULL。然后将原来以结点工为根的子树的高度减1，并沿X通向根的路径反向 追踪高度的这一变化对路径上各个结点P的影响，进行平衡化处理。
casel：当前结点 P的平衡因子为 0。如果它的左子树或右子树被缩短，则它的平衡 因子改为 1或一1。参看图 7．23的 casel。
case2：结点 p的平衡因子不为 0，且较高的子树被缩短，则 p的平衡因子改为 0。参 看图 7．23的 case2。
case3：结点 P的平衡因子不为 0，且较矮的子树又被缩短，则在结点 P发生不平衡。 我们将进行平衡化旋转来恢复平衡。令P的较高的子树的根为q（该子树未被缩短），根 据。的平衡因子，有如下3种平衡化操作。
case 3a：如果 Q的平衡因子为 0，则执行一个单旋转来恢复结点 P的平衡，如图 7．23 中 case 3a所示。
case 3b：如果 q的平衡因子与 P的平衡因子相同，则执行一个单旋转来恢复平衡，结 点 p和q的平衡因子均改为 0。如图 7．23中 case 3b所示。
case 3c：如果 p与q的平衡因子相反，则执行一个双旋转来恢复平衡，先围绕q转再 围绕产转。新的根结点的平衡因子置为0，其他结点的平衡因子相应处理。参看图7．23 ·中的 case
3c。
在 case 3a， 3b和 3c的情形中，旋转的方向取决于是结点户的哪一棵子树被缩短，在图 7．23中只是给出了某些可能情况。图7．24给出删除一个结点时做平衡化旋转的示例。
四、AVL的高度
若 设在新结点插人前AVL树的高度为h，结点个数为n，则插人一个新结点的时间 是O（h）。这与一般的二叉搜索树相同。但对于一棵不一定平衡的三叉搜索树来说，树的 高度最大可能是h=n-1，因此，最坏情况下，在一般二又搜索树中插入一个新结点所需 的时间为o（n）。那么，对于AVL树来说，h应当是多大呢？
若设Nh是高度为h的AVL树的最小结点数。在最坏情况下，根的一棵子树的高度为h-l，另一棵子树的高度为h-2，这两棵子树也是高度平衡的。因此有
二叉搜索树适合于组织在内存中的较小的索引（或目录）。对于存放在外存中的较大 的文件系统，用二叉搜索树来组织索引就不太合适了。若以结点为内外存交换的单位，则在搜索过程中为找到所需的关键码，需对外存进行log2n次访问，这是 很费时的。因此在文件检索系统中大量使用的是用B树或B十树做文件索引。
