平衡叉树...pptVIP

  1. 1、本文档共34页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
平衡叉树..

平衡二叉树(AVL) 平衡二叉树的查找 BSTNode * SearchBST(BSTNode * bt,KeyType k) {//在以bt为根的平衡二叉树中,查找关键字为k的结点,找到返回指向该结点的//指针,否则返回NULL if (bt = =NULL || bt-key = =k) return bt; if(kbt-key) return SearchBST(bt-lchild,k); else return SearchBST(bt-rchild,k); } 平衡二叉树中结点的删除 平衡二叉树的删除 平衡二叉树的删除 平衡二叉树 void Delete2(BSTNode *q,BSTNode *r,int taller) /*由DeleteAVL()调用,用于处理被删结点左右子树均不空的情况*/ { if (r-rchild==NULL) { q-key=r-key; q=r; r=r-lchild; free(q); taller=1; } else { Delete2(q,r-rchild,taller); if (taller==1) RightProcess1(r,taller); } } * * 平衡二叉树的概念 平衡二叉树的查找 平衡二叉树中结点的插入与建立 平衡二叉树中结点的删除 平衡二叉树(AVL) 结点的平衡因子(balancd factor用bf表示) :二叉树中某结点左子树的高度与右子树的高度之差称为该结点的平衡因子. 平衡二叉树是另一种形式的二叉查找树。其特点是: 左右子树深度之差的绝对值不大于1 称有这种特性的二叉树为平衡二叉树。 在算法中,可以通过平衡因子来具体实现平衡二叉树的定义。 从平衡因子的角度可以说,若一棵二叉树中所有结点的平衡因子的绝对值小于或等于1,则该树称为平衡二叉树。 96 38 24 88 28 11 25 98 0 1 0 -1 1 -1 0 0 -1 -2 0 1、平衡二叉树插入结点的调整方法 若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性,首先从根结点到该新插入结点的路径之逆向根结点方向找第一个失去平衡的结点,然后以该失衡结点和它相邻的刚查找过的两个结点构成调整子树(最小不平衡子树),即调整子树是指以离插入结点最近,且平衡因子绝对值大于1的结点为根结点的子树,使之成为新的平衡子树。 96 38 24 88 28 11 25 98 -2 (1) LL型调整 A B f d e h h 0 1 h 1 2 调整方法: 单向右旋平衡,即将A的左孩子B 向右上旋转代替A成为根结点,将A结点向右下旋转成为B的右子树的根结点,而B的原右子树则作为A结点的左子树。 B A d e f lc=p-lchild; /*lc指向B p-lchild=lc-rchild; /*把B结点的右子树挂接为A的左子树 lc-rchild=p; /*A结点成为B的右孩子 p=lc; /*p指向新的根结点 p p (2)RR型调整 A a B b c h h 0 -1 调整方法: 单向左旋平衡:即将A的右孩子B向左上旋转代替A成为根结点,将A结点向左下旋转成为B的左子树的根结点,而B的原左子树则作为A结点的右子树。 B A c a b -1 -2 lc=p-rchild; /*lc指向B*/ p-rchild=lc-lchild; /*把B结点的左子树挂接为A的右子树*/ lc-lchild=p; /*A结点成为B的左孩子*/ p=lc; /*p指向新的根结点*/ p p (3)LR型调整 A B C n m i e h h+1 h+1 0 0 1 1 -1 2 C B A n m i e 调整方法:先左旋转后右旋转平衡,即将A结点的左孩子(即B结点)的右子树的根结点(即C结点)向左上旋转提升到B结点的位置,然后再把该C结点向右上旋转提升到A结点的位置。 p b c p-lchild=c-rchild; /*把C的右子树挂接成A的左子树*/ b-rchild=c-lchild; /*把C的左

文档评论(0)

panguoxiang + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档