/* 8.7 平衡二叉树（AVL树） 平衡二叉树（Self-Balancing SearchTree或Height-Balanced Binary Search Tree）,是一种二叉排序树， 其中每一个节点的左子树和右子树的高度差至多等于1。 有两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年共同发明一种解决平衡二叉树的算法，所以 有不少资料中也称这样的平衡二叉树为AVL树。 8.7.1 平衡二叉树实现原理 平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了 平衡性，若是，则找出最小不平衡树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各节点之间的链接关系， 进行相应的旋转，使之成为新的平衡子树。 */ /* 8.7.2 平衡二叉树实现算法 ok，有了这么多的准备工作，我们可以来讲解代码了。首先是需要改进二叉排序树的结点结构，增加一个bf，用来 存储平衡因子。 */ //二叉树的二叉链表结点结构定义 //结点结构 typedef struct BiTNode { //结点数据 int data; //结点的平衡因子 int bf; //左右孩子指针 struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; //然后，对于右旋操作，我们的代码如下。 /* 对以P为根的二叉排序树作右旋处理，处理之后p指向新的树根节点，即旋转处理之前的左子树的根结点 */ void R_Rotate(BiTree *P) { BiTree L; //L指向P的左子树根节点 L=(*P)->lchild; //L的右子树挂接为P的左子树 (*P)->lchild = L->rchild; L->rchild = (*P); //P指向新的根结点 *P = L; } /* 左旋操作代码如下 对以P为根的二叉排序树作左旋处理，处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0 */ void L_Rotate(BiTree *P) { BiTree R; //R指向P的右子树根结点 R = (*P)->rchild; //R的左子树挂接为P的右子树 (*P)->rchild = R->lchild; R->lchild = (*P); //P指向新的根结点 *P = R; } //上边的代码和右旋是对称的,可以查看p594 图8-7-9对右旋操作的解释 /* 现在我们来看左平衡旋转处理的函数代码 */ #define LH +1 //左高 #define EH 0 //等高 #define RH -1 //右高 //对以指针T所指结点为根的二叉树作左平衡旋转处理。 本算法结束时，指针T指向新的根节点 void LeftBalance(BiTree *T) { BiTree L,Lr; //L指向T的左子树根节点 L = (*T)->lchild; switch(L->bf) { //检查T的左子树的平衡度，并作相应平衡处理 //新节点插入在T的左孩子的左子树上，要作单右旋处理 case LH: (*T)->bf = L->bf = EH; R_Rotate(T); break; //新结点插入在T的左孩子的右子树上，要作双旋处理 case RH: //Lr指向T的左孩子的右子树根 Lr = L->rchild; //修改T及其左孩子的平衡因子 switch (Lr->bf) { case LH: (*T)->bf = RH; L->bf = EH; break; case EH: (*T)->bf = L->bf = EH; break; case RH: (*T)->bf = EH; L->bf = LH; break; } Lr->bf = EH; //对T的左子树作左旋平衡处理 L_Rotate(&(*T)->lchild); //对T作右旋平衡处理 R_Rotate(T); } } /* 8.8 多路查找树（B树） B树和B+树 书上只给出了一些概念描述和图片，并没有给出实现的代码 我们之前谈的树，都是一个结点可以右多个孩子，单它自身只存储一个元素。二叉树限制更多，结点最多只能有 两个孩子。 一个结点（父节点也叫双亲节点）只能存储一个元素，在元素非常多的时候，就使得要么树的度非常大（结点拥有 子树的个数的最大值），要么树的高度非常大，甚至两者都必须足够大才行。这就使得内存读取存取外存次数非常多， 这显然成了时间效率上的瓶颈，这迫使我们要打破每一个结点只存储一个元素的限制，为此引入了多路查找树的概念。 多路查找树（muitl-way search tree），其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。 由于它是查找树，所有元素之间存在某种特定的排序关系。 在这里，每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的。为此，我们讲解它的4种特殊形式： 2-3树、2-3-4树、B树、B+树。 B树的数据结构就是为内外存的数据交互准备的。 一棵m阶的B+树和m阶的B树差异在于： 1.有n棵子树的结点中包含有n个关键字。 2.所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小 而大顺序链接； 3.所有分支结点可以看成索引，结点中仅含有其子树中的最大（或最小）关键字。 */