标题:
GLIB平衡二叉搜索树算法浅析【原】
[打印本页]
作者:
liuda
时间:
2015-1-23 19:21
标题:
GLIB平衡二叉搜索树算法浅析【原】
<p>GLIB平衡二叉搜索树算法浅析</p><p>一．树的基本概念</p><p>树，在计算机领域中，它是一种十分基础的数据结构，几乎所有操作系统都将文件存放在树状结构里，几乎所有的编译器都需要实现一个表达式树等等。</p><p> 树由节点和边组成；如图一，整个树有一个最上端节点，称为根节点（root），每个节点可以拥有具有方向性的边，用它来和其它节点相连。相连节点之中，以上者称为父节点，在下者称为子节点。无子节点称为叶节点。子节点可以存在多个，如果最多只允许两个子节点，即所谓的二叉树。不同的节点如果拥有相同的父节点，彼此互称为兄弟节点。跟节点至任何节点之间有唯一的路径，路径所经过的边数，称为路径长度。根节点至任一节点的路径长度，即所谓该节点的深度。根节点的深度永远都为0。某节点至其最深子节点（叶节点）的路径长度，称为该节点的高度。整棵树的高度，便以根节点的高度来代表。</p><p><img src="http://c.51hei.com/a/old/up/0/512311261930791.jpg" small="0"></p><p>图一</p><p>二．平衡二叉搜索树BBST(Balancing Binary Search Tree)</p><p> 所谓二叉搜索树，即二叉树，上面也讲到，即“任何节点最多只允许有两个子节点”。这两个子节点称为左子节点和右子节点，二叉树的运用极广，在linux内核中所使用的就是二叉树中的红黑树，上面提到的几乎所有的编译器都需要实现一个表达式树也是使用的二叉树，同时本文所要讲解的glib里面的树结构也是使用的二叉树。</p><p> 我们对数的操作，无非就是对树进行插入、删除、查找等操作。而这些操作都要是对树的节点进行操作，那怎么入手呢，好在二叉树有这么一个规则：任何一个节点的键值一定大于左子树中每一个节点的键值，并小于右子树中每一个节点的键值。因此，从根节点一直往左走，直至无路可走，可查得最小元素；反之，从右走，可得到最大元素。</p><p> 也许因为某些插入或删除的键值不够随机，二叉树可能会失去平衡，造成搜寻效率低落的情况，图二是极度平衡树跟极度不平衡树的状况。</p><p><img src="http://c.51hei.com/a/old/up/0/512311261929276.jpg" small="0"></p><p>图二</p><p> 树的平衡与否，并没有一个绝对的衡量标准。平衡的大致意义是没有任何一个节点的深度过大。有数种结构如AVL-tree、RB-tree、AA-tree均可实现平衡二叉树，它们都比一般的二叉树复杂，插入和删除节点的平均时间也比较长，但它们可以避免极难对付的最坏（高度不平和）情况，而且因为他们总是保持平衡，所以元素的搜寻所需时间也就比较小，比一般要省25%。</p><p> 在GLIB中所使用的平衡二叉树结构是AVL-tree，所以本文主要分析AVL-tree数据结构的插入跟删除方法，但是不会分析其源码实现，读者可以自行分析其结构。</p><p> 在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文《An algorithm for the organization of information》中发表了它。</p><p>1. BBST的插入：</p><p> 插入一个叶节点只有插入点至根节点路径上各节点可能会破坏AVL的平衡条件。由于只有只有插入点至根节点路径上各节点可能会破坏AVL的平衡条件，因此只需要调整最深的那个节点，便可使整棵树重新获得平衡。假设最深节点为Root【失去平衡树的根节点】，由于节点最多拥有两个子节点，而所谓的平衡破坏就是左右子树的高度相差2，因此可以分为如下四种情况：</p><p>a) 插入点位于Root的左子节点的左子树—左左情况</p><p>b) 插入点位于Root的右子节点的右子树—右右情况</p><p>c) 插入点位于Root的左子节点的右子树—左右情况</p><p>d) 插入点位于Root的右子节点的左子树—右左情况</p><p>情况a) 跟 b) 是从外侧插入，可以通过单旋来调整；c) 跟 d) 为内侧插入，可以通过双旋转来调整，如下图所示。</p><p><img src="http://c.51hei.com/a/old/up/0/512311261986769.jpg" small="0" height="508" width="758"></p><p>插入算法实现：</p><p>在平衡的二叉搜索树 BBST上插入一个新的数据元素e的递归算法可描述如下：</p><p>1) 若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1； </p><p>2) 若e的关键字和BBST的根结点的关键字相等，则不进行； </p><p>3) 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之： </p><p>1.1) BBST的根结点的平衡因子为-1（右子树的深度大于左子树的深度，则将根结点的平衡因子更改为0，BBST的深度不变； </p><p>1.2) BBST的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1； </p><p>1.3) BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：则若BBST的左子树根结点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变； </p><p>4) 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。 </p><p>2. BBST的删除：</p><p> 我们先来回顾下二叉搜索树的删除节点z的过程：如果z没有子节点，那么直接删除即可；如果z只有一个子节点，那么让这个子节点来代替z的 位置，然 后把z删除即可；如果z有两个子节点，那么找到z在中序遍历中的后继节点s（也就是从z->rchild开始向左下方一直走到底的那一个节点），把 s的key赋值给z的key，然后删除s。</p><p> 那么AVL-tree删除节点 z的方法首先也是按部就班以上的过程，这过程从根本上讲其实就是删除叶节点。删除一个叶节点只有删除点的父节点至根节点路径上各节点可能会破坏AVL的平衡条件。由于只有删除点的父节点至根节点路径上各节点可能会破坏AVL的平衡条件，因此只需要调整最深的那个节点，便可使整棵树重新获得平衡，处理方法跟插入节点调整平衡的方法及其相似。</p><p>删除算法实现：</p><p>三．RB-tree简介</p><p> RB-tree即红黑树，也是一种自平衡二叉查找树。红黑树的每个节点上的属性除了有一个key、3个指针：parent、lchild、rchild以外，还多了一个属性：color。它只能是两种颜色：红或黑。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下4点性质：</p><p>1. 根节点是黑色的。</p><p>2. 空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。</p><p>3. 红色节点的父、左子、右子节点都是黑色。</p><p>4. 在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。</p><p>这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。</p><p> 本文就简单介绍下红黑树的性质，具体关于插入、删除等操作可以参考本文所引用的参考资料。</p><p>四．参考资料</p><p>l AVL树 - 维基百科，自由的百科全书</p><p>l 红黑树 - 维基百科，自由的百科全书</p><p>l STL源码分析</p>
欢迎光临 (http://www.51hei.com/bbs/)
Powered by Discuz! X3.1