您好,欢迎来到华佗健康网。
搜索
您的当前位置:首页快速构建AVL树

快速构建AVL树

来源:华佗健康网
维普资讯 http://www.cqvip.com

第5期 安阳师范学院学报 6l 快速构建AVL树 胡 云 (无锡市广播电视大学,江苏无锡214011) [摘要]传统AVL树的构建是从空树开始依次将结点插人进来,每插人~个结点就要判断新得到的新树是否满足 AVL树的性质,如满足则继续下一个结点的插人,如不满足则先要将之调整为AVL树再插入下一结点,直至结束。这种 方法需要对生成的中间树频繁地进行调整,耗时较多。本文提出了一种新的简单的方法,主旨是采用递归思想实现:先 将数据进行排序,然后将中点数据作为AVL树的根,小于中点数据的数据构成AVL树的左子树,大于中点数据的数据构 成AVL树的右子树。 [关键词]AVL树;平衡二叉树;二叉搜索树 [中图分类号]TP301.6 [文献标识码]A [文章编号]1671—5330(2007)05—0061—03 0 引言 简单方法。 平衡二叉树的定义:在一棵二叉树中,若除最 1 方法比较 后一层外,其余层都是满的,而最后一层上的结点 假设输入关键码序列为L{16,3,7,11,9,26, 可以任意分布,则称此树为平衡二又树。 18,14,15},根据输入构建AVL树。 二又搜索树的定义:二又搜索树或者是一棵 1.1传统的构建方法 空树,或者是具有下列性质的二又树: 基本思想:每当插入一个新结点时,AVL树中 1)每个结点都有一个作为搜索依据的关键 相关结点的平衡状态会发生改变。因此,在插入 码(key),所有结点的关键码互不相同; 一个新结点后,需要从插入位置沿通向根的路径 2)左子树(如果存在)上所有结点的关键码 回溯,检查各结点左、右子树的高度差。如果在某 都小于根结点的关键码; 一结点发现高度不平衡,停止回溯。从发生不平 3)右子树(如果存在)上所有结点的关键码 衡的结点起,沿刚才回溯的路径取直接下两层的 都大于根结点的关键码; 结点。如果这三个结点处于一条直线上,则采用 4)左子树和右子树也是二叉搜索树。 单旋转进行平衡化;如果这三个结点处于一条折 AVL树的定义:AVL树或者是空树,或者是具 线上,则采用双旋转进行平衡化…。 有下列性质的二叉搜索树:它的左子树和右子树 构建过程如图1所示: 都是AVL树,且左子树和右子树的高度子差的绝 1.2本文提出的方法 对值不超过1。 基本思想: 根据上述定义可知,AVL树实际上就是高度 1)对关键码序列L从小到大进行排序得到 平衡的二又搜索树。它是1962年由两位俄罗斯 L’; 数学家G.M.Adel’son—Vel’sky和E.M.Landis提 2)选择序列L’中中间元素m作为AVL树的 出的。引入它是为了提高二叉搜索树的效率,减 根,在m左边的元素作为AVL树的左子树元素, 少平均搜索长度。他们提出了动态生成AVL树 在m右边的元素作为AVL树的右子树元素; 的方法,在构建AVL树的过程中为了保持高度的 3)按2的方法分别构建AVL树的左子树和 平衡,需通过平衡化旋转调整树的结构,操作较复 右子树; 杂且不易理解。本文提出了一种构建AVL树的 构建过程如图2所示: [收稿日期]2007—08—10 [作者简介]胡云(1978一),男,江苏盐城人,硕士,主要研究方向为计算机图形学、算法设计。 维普资讯 http://www.cqvip.com

62 安阳师范学院学报 第5期 0 ⑧ O 图1传统方法构建AVL树的过程 图2改进方法构建AVL树的过程 2算法实现 if(i<j) 本文方法的算法描述如下(采用C++语言 { 描述):temp=A[i];A[i]:A[j];A[j]=temp; //二叉树结点 } struct BtreeNode{ }while(i<j); int data; A[s]=A[j];A[j]=x; BTreeNode*left: if(s<J一1)QuickSort(A,s,j一1); BtreeNode*right; if(j+1<t)QuickSort(A,j+1,t); }; } //用快速排序法对关键码排序 void QuickSort(int A[],int s,int t) //AVL树生成算法 { void CREAT(BTreeNode*&root,int a int i=s,j=t+1; [],int n) int x=A[s]; { do{ if(n>O) do i++;while(A[i]<x); { d0 j一一;while(A[j]>x); int low,high,mid; 维普资讯 http://www.cqvip.com

第5期 low=0;high=n一1; 胡云:快速构建AVL树 63 方法实现算法的时间复杂度只为O(1og2 n);如给 定序列无序,本文方法和传统方法实现算法的时 间复杂度虽都为0(nlog2 n),但比较次数显著减 少,传统方法约需1.44nlog2 n次比较,本文方法约 需(n+1)log2 n。用本文方法构建AVL树,可以使 构建过程更加简单,但本文主要针对的是根据给 定序列构建得到最终的AVL树,如果只是在已有 mid=(1ow+high)/2; root=new BTreeNode; root一>data:a[mid]; root一>left=NULL: root一>right:NULL; CREAT(root一>left,a,mid); CREAT(root一>right,a+mid+1,n—mid 的AVL树上进行插入或删除运算,还是借助平衡 一1); 化旋转来完成更好一些。 } } [参考文献] 3 结束语 [1]殷人昆.数据结构[M].北京:清华大学出版社, 比较图1和图2,显然利用本文方法构建 20o2.196—203. AVL树不需要频繁的平衡化旋转,可以快速构建 [2]许卓群.数据结构[M].北京:广播电视大学出版 得到AVL树。如给定序列已基本有序,传统方法 社.2001.197—207. 实现算法的时间复杂度虽为0(nlog2 n),而本文 Fast Build the AVL Tree HU Yun (Wuxi Radio&Television University,Wuxi 21401 1,China) Abstract:To assign a disorderly sequence to construct the AVL tree,the traditional method starts from the empty tree to insert the point in turn.When every time inserts the tree,the new tree will decide whether it satisfies the AVL tere’S nature.If it satisfies,the next point will insert,if it does not satisfy then it must adjusts to be the AVL tere again then inserts next point,until the end.This method needs to carry on the adjustment frequently to the pro— duction of the middle tree,it is very tedious.This article proposes one simple method on this question. Key words:AVL tree;Balanced binary tree;Two forks the search tree [责任编辑:D] 

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- huatuo0.com 版权所有 湘ICP备2023021991号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务