《数据结构》-平衡二叉树

9.1 概述,9.1.1 查找表,9.1.2 相关术语,9.1.3 类型说明,9.2 静态查找表,9.2.1 概述,9.2.2 顺序表的查找,9.2.3 有序表的查找,9.2.4 索引顺序表的查找,9.3 动态查找表,9.3.1 概述,9.3.2 二叉排序树和平衡二叉树,9.3.3 B-树和B+树,9.4 哈希表,9.4.1 定义,9.4.2 哈希函数的构造,9.4.3 处理冲突的方法,9.4.4 哈希表的查找及其分析,第九章查找,（2）平衡二叉树,定义,平衡二叉树（Balanced Binary Tree 或Height-Balanced Tree）又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。,平衡因子BF（Balance Factor）：二叉树上结点的左子树的深度减去它的右子树的深度的值。,由平衡二叉树的定义易知，平衡二叉树上所有结点的平衡因子只可能 是1、0和1。,（2）平衡二叉树,定义,例如，图9.6(a)所示为两棵平衡二叉树，而图9.6(b)为两棵不平衡二叉树，结点中的值为该结点的平衡因子,图形表示,(a) 平衡二叉树,(b) 不平衡二叉树,图9.6平衡与不平衡二叉树及结点的平衡因子,平衡二叉树是二叉排序树的另一种形式。我们希望由任何初始序列构成的二叉排序树都是平衡二叉树。因为平衡二叉树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的（其中N是结点的个数）。由此，它的平均查找长度也和logN同数量级。,typedef structBSTNode ElemTypedata;intbf;/结点的平衡因子struct BSTNode *lchild, *rchild;/左、右孩子指针 BSTNode, * BSTree;,C语言描述,构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。,构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。,例如:依次插入的关键字为5, 4, 2, 8, 6, 9,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋转一次,先向右旋转再向左旋转,9,5,向左旋转一次,继续插入关键字 9,假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行调整的规律可归纳为下列4种情况：,平衡调整,1单向右旋平衡处理： 由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次向右的顺时针旋转操作。如图9.6(a)所示。,2单向左旋平衡处理： 由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由1变为2，致使以*a为根的子树失去平衡，则需进行一次向左的顺逆针旋转操作。如图9.6(c)所示。,3双向旋转（先左后右）平衡处理： 由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡,则需进行两次旋转（先左旋后右旋）操作。如图9.6(b)所示。,4双向旋转（先右后左）平衡处理： 由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由1变为2，致使以*a为根的子树失去平衡,则需进行两次旋转（先右旋后左旋）操作。如图9.6(d)所示。,插入算法,算法思想：在平衡二叉排序树BBST上插入一个新的数据元素e的递归算法可描述如下：,1若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结 点，树的深度增1；,2若e的关键字和BBST的根结点的关键字相等，则不进行插入；,3若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加（1）时，分别就下列不同情况处理之：,iBBST的根结点的平衡因子为1（右子树的深度大于左子树的深度）：则将根结点的平衡因子更改为0，BBST的深度不变；,iiBBST的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1；,iiiBBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）： a.若BBST的左子树根结点的平衡因子为1，则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变； b. 若BBST的左子树根结点的平衡因子为1，则需进行先向左、后向右的双向旋转平衡处理，并且在旋转处理之后，修改根结 点和其左、右子树根结点的平衡因子，树的深度不变。,4若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（1）时，分别就不同情况处理之。其处理操作和上述3中描述相对称。,typedef structBSTNode ElemTypedata;intbf;/结点的平衡因子struct BSTNode *lchild, *rchild;/左、右孩子指针 BSTNode, * BSTree;,算法9.7如下： void R_Rotate (BSTree /p指向新的根结点 / R_Rotate,p,lc,算法9.8如下： void L_Rotate (BSTree /p指向新的根结点 / L_Rotate,p,lc,算法9.10如下：,#defineLH+1/左高#defineEH0/等高#defineRH-1/右高Status InsertAVL (BSTree &T, ElemType e, Boolean &taller) /若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入 /一个数据元素为e的新结点，并返回1，否则返回0。若因插入而使二 /叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T长高 /与否。,if (!T) /插入新结点，树“长高”，置taller为TRUET = (BSTree) malloc (sizeof (BSTNode);Tdata = e;Tlchild = Trchild = NULL;,Tbf = EH;taller = TRUE; ,else /应继续在*T的右子树中进行搜索if (!InsertAVL(Trchild, e, taller)/未插入 return 0;if (taller)/已插入到*T的右子树中且右子树“长高” switch (Tbf) /检查*T的平衡度case LH:/原本右子树比左子树高，现左、右子树等高Tbf = EH;taller = FALSE;break;case EH:/原本左右子树等高，现因右子树增高而使树增高Tbf = RH;taller = TRUE;break; case RH:/原本右子树比左子树高，需要作右平衡处理RightBalance (T);taller = FALSE;break; / switch (Tbf) / else / else return 1; / InsertAVL,void LeftBalance (BSTree ,case RH: Tbf = EH; lcbf = LH; break; / switch (rdbf)rdbf = EH;L_Rotate (Tlchild);/对*T的左子树作左旋平衡处理R_Rotate (T);/对*T作右旋平衡处理 / switch (lcbf) / LeftBalance,在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡 树的深度。,平衡树的查找性能分析：,问：含 n 个关键字的二叉平衡树可能达到的最大深度是多少？,n = 0,空树,最大深度为 0,n = 1,最大深度为 1,n = 2,最大深度为 2,n = 4,最大深度为 3,n = 7,最大深度为 4,先看几个具体情况:,反过来问，深度为 h 的二叉平衡树中所含结点的最小值 Nh 是多少？,h = 0,N0 = 0,h = 1,h = 2,h = 3,一般情况下，,N1 = 1,N2 = 2,N3 = 4,Nh