快速构建AVL树

第５期　安阳师范学院学报　６ｌ　快速构建ＡＶＬ树　胡　云　（无锡市广播电视大学，江苏无锡２１４０１１）　［摘要］传统ＡＶＬ树的构建是从空树开始依次将结点插人进来，每插人～个结点就要判断新得到的新树是否满足　ＡＶＬ树的性质，如满足则继续下一个结点的插人，如不满足则先要将之调整为ＡＶＬ树再插入下一结点，直至结束。这种　方法需要对生成的中间树频繁地进行调整，耗时较多。本文提出了一种新的简单的方法，主旨是采用递归思想实现：先　将数据进行排序，然后将中点数据作为ＡＶＬ树的根，小于中点数据的数据构成ＡＶＬ树的左子树，大于中点数据的数据构　成ＡＶＬ树的右子树。　［关键词］ＡＶＬ树；平衡二叉树；二叉搜索树　［中图分类号］ＴＰ３０１．６　［文献标识码］Ａ　［文章编号］１６７１—５３３０（２００７）０５—００６１—０３　０　引言　简单方法。　平衡二叉树的定义：在一棵二叉树中，若除最　１　方法比较　后一层外，其余层都是满的，而最后一层上的结点　假设输入关键码序列为Ｌ｛１６，３，７，１１，９，２６，　可以任意分布，则称此树为平衡二又树。　１８，１４，１５｝，根据输入构建ＡＶＬ树。　二又搜索树的定义：二又搜索树或者是一棵　１．１传统的构建方法　空树，或者是具有下列性质的二又树：　基本思想：每当插入一个新结点时，ＡＶＬ树中　１）每个结点都有一个作为搜索依据的关键　相关结点的平衡状态会发生改变。因此，在插入　码（ｋｅｙ），所有结点的关键码互不相同；　一个新结点后，需要从插入位置沿通向根的路径　２）左子树（如果存在）上所有结点的关键码　回溯，检查各结点左、右子树的高度差。如果在某　都小于根结点的关键码；　一结点发现高度不平衡，停止回溯。从发生不平　３）右子树（如果存在）上所有结点的关键码　衡的结点起，沿刚才回溯的路径取直接下两层的　都大于根结点的关键码；　结点。如果这三个结点处于一条直线上，则采用　４）左子树和右子树也是二叉搜索树。　单旋转进行平衡化；如果这三个结点处于一条折　ＡＶＬ树的定义：ＡＶＬ树或者是空树，或者是具　线上，则采用双旋转进行平衡化…。　有下列性质的二叉搜索树：它的左子树和右子树　构建过程如图１所示：　都是ＡＶＬ树，且左子树和右子树的高度子差的绝　１．２本文提出的方法　对值不超过１。　基本思想：　根据上述定义可知，ＡＶＬ树实际上就是高度　１）对关键码序列Ｌ从小到大进行排序得到　平衡的二又搜索树。它是１９６２年由两位俄罗斯　Ｌ’；　数学家Ｇ．Ｍ．Ａｄｅｌ’ｓｏｎ—Ｖｅｌ’ｓｋｙ和Ｅ．Ｍ．Ｌａｎｄｉｓ提　２）选择序列Ｌ’中中间元素ｍ作为ＡＶＬ树的　出的。引入它是为了提高二叉搜索树的效率，减　根，在ｍ左边的元素作为ＡＶＬ树的左子树元素，　少平均搜索长度。他们提出了动态生成ＡＶＬ树　在ｍ右边的元素作为ＡＶＬ树的右子树元素；　的方法，在构建ＡＶＬ树的过程中为了保持高度的　３）按２的方法分别构建ＡＶＬ树的左子树和　平衡，需通过平衡化旋转调整树的结构，操作较复　右子树；　杂且不易理解。本文提出了一种构建ＡＶＬ树的　构建过程如图２所示：　［收稿日期］２００７—０８—１０　［作者简介］胡云（１９７８一），男，江苏盐城人，硕士，主要研究方向为计算机图形学、算法设计。　维普资讯 http://www.cqvip.com

６２　安阳师范学院学报　第５期　０　⑧　Ｏ　图１传统方法构建ＡＶＬ树的过程　图２改进方法构建ＡＶＬ树的过程　２算法实现　ｉｆ（ｉ＜ｊ）　本文方法的算法描述如下（采用Ｃ＋＋语言　｛　描述）：ｔｅｍｐ＝Ａ［ｉ］；Ａ［ｉ］：Ａ［ｊ］；Ａ［ｊ］＝ｔｅｍｐ；　／／二叉树结点　｝　ｓｔｒｕｃｔ　ＢｔｒｅｅＮｏｄｅ｛　｝ｗｈｉｌｅ（ｉ＜ｊ）；　ｉｎｔ　ｄａｔａ；　Ａ［ｓ］＝Ａ［ｊ］；Ａ［ｊ］＝ｘ；　ＢＴｒｅｅＮｏｄｅ＊ｌｅｆｔ：　ｉｆ（ｓ＜Ｊ一１）ＱｕｉｃｋＳｏｒｔ（Ａ，ｓ，ｊ一１）；　ＢｔｒｅｅＮｏｄｅ＊ｒｉｇｈｔ；　ｉｆ（ｊ＋１＜ｔ）ＱｕｉｃｋＳｏｒｔ（Ａ，ｊ＋１，ｔ）；　｝；　｝　／／用快速排序法对关键码排序　ｖｏｉｄ　ＱｕｉｃｋＳｏｒｔ（ｉｎｔ　Ａ［］，ｉｎｔ　ｓ，ｉｎｔ　ｔ）　／／ＡＶＬ树生成算法　｛　ｖｏｉｄ　ＣＲＥＡＴ（ＢＴｒｅｅＮｏｄｅ＊＆ｒｏｏｔ，ｉｎｔ　ａ　ｉｎｔ　ｉ＝ｓ，ｊ＝ｔ＋１；　［］，ｉｎｔ　ｎ）　ｉｎｔ　ｘ＝Ａ［ｓ］；　｛　ｄｏ｛　ｉｆ（ｎ＞Ｏ）　ｄｏ　ｉ＋＋；ｗｈｉｌｅ（Ａ［ｉ］＜ｘ）；　｛　ｄ０　ｊ一一；ｗｈｉｌｅ（Ａ［ｊ］＞ｘ）；　ｉｎｔ　ｌｏｗ，ｈｉｇｈ，ｍｉｄ；　维普资讯 http://www.cqvip.com

第５期　ｌｏｗ＝０；ｈｉｇｈ＝ｎ一１；　胡云：快速构建ＡＶＬ树　６３　方法实现算法的时间复杂度只为Ｏ（１ｏｇ２　ｎ）；如给　定序列无序，本文方法和传统方法实现算法的时　间复杂度虽都为０（ｎｌｏｇ２　ｎ），但比较次数显著减　少，传统方法约需１．４４ｎｌｏｇ２　ｎ次比较，本文方法约　需（ｎ＋１）ｌｏｇ２　ｎ。用本文方法构建ＡＶＬ树，可以使　构建过程更加简单，但本文主要针对的是根据给　定序列构建得到最终的ＡＶＬ树，如果只是在已有　ｍｉｄ＝（１ｏｗ＋ｈｉｇｈ）／２；　ｒｏｏｔ＝ｎｅｗ　ＢＴｒｅｅＮｏｄｅ；　ｒｏｏｔ一＞ｄａｔａ：ａ［ｍｉｄ］；　ｒｏｏｔ一＞ｌｅｆｔ＝ＮＵＬＬ：　ｒｏｏｔ一＞ｒｉｇｈｔ：ＮＵＬＬ；　ＣＲＥＡＴ（ｒｏｏｔ一＞ｌｅｆｔ，ａ，ｍｉｄ）；　ＣＲＥＡＴ（ｒｏｏｔ一＞ｒｉｇｈｔ，ａ＋ｍｉｄ＋１，ｎ—ｍｉｄ　的ＡＶＬ树上进行插入或删除运算，还是借助平衡　一１）；　化旋转来完成更好一些。　｝　｝　［参考文献］　３　结束语　［１］殷人昆．数据结构［Ｍ］．北京：清华大学出版社，　比较图１和图２，显然利用本文方法构建　２０ｏ２．１９６—２０３．　ＡＶＬ树不需要频繁的平衡化旋转，可以快速构建　［２］许卓群．数据结构［Ｍ］．北京：广播电视大学出版　得到ＡＶＬ树。如给定序列已基本有序，传统方法　社．２００１．１９７—２０７．　实现算法的时间复杂度虽为０（ｎｌｏｇ２　ｎ），而本文　Ｆａｓｔ　Ｂｕｉｌｄ　ｔｈｅ　ＡＶＬ　Ｔｒｅｅ　ＨＵ　Ｙｕｎ　（Ｗｕｘｉ　Ｒａｄｉｏ＆Ｔｅｌｅｖｉｓｉｏｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｘｉ　２１４０１　１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｏ　ａｓｓｉｇｎ　ａ　ｄｉｓｏｒｄｅｒｌｙ　ｓｅｑｕｅｎｃｅ　ｔｏ　ｃｏｎｓｔｒｕｃｔ　ｔｈｅ　ＡＶＬ　ｔｒｅｅ，ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｍｅｔｈｏｄ　ｓｔａｒｔｓ　ｆｒｏｍ　ｔｈｅ　ｅｍｐｔｙ　ｔｒｅｅ　ｔｏ　ｉｎｓｅｒｔ　ｔｈｅ　ｐｏｉｎｔ　ｉｎ　ｔｕｒｎ．Ｗｈｅｎ　ｅｖｅｒｙ　ｔｉｍｅ　ｉｎｓｅｒｔｓ　ｔｈｅ　ｔｒｅｅ，ｔｈｅ　ｎｅｗ　ｔｒｅｅ　ｗｉｌｌ　ｄｅｃｉｄｅ　ｗｈｅｔｈｅｒ　ｉｔ　ｓａｔｉｓｆｉｅｓ　ｔｈｅ　ＡＶＬ　ｔｅｒｅ’Ｓ　ｎａｔｕｒｅ．Ｉｆ　ｉｔ　ｓａｔｉｓｆｉｅｓ，ｔｈｅ　ｎｅｘｔ　ｐｏｉｎｔ　ｗｉｌｌ　ｉｎｓｅｒｔ，ｉｆ　ｉｔ　ｄｏｅｓ　ｎｏｔ　ｓａｔｉｓｆｙ　ｔｈｅｎ　ｉｔ　ｍｕｓｔ　ａｄｊｕｓｔｓ　ｔｏ　ｂｅ　ｔｈｅ　ＡＶＬ　ｔｅｒｅ　ａｇａｉｎ　ｔｈｅｎ　ｉｎｓｅｒｔｓ　ｎｅｘｔ　ｐｏｉｎｔ，ｕｎｔｉｌ　ｔｈｅ　ｅｎｄ．Ｔｈｉｓ　ｍｅｔｈｏｄ　ｎｅｅｄｓ　ｔｏ　ｃａｒｒｙ　ｏｎ　ｔｈｅ　ａｄｊｕｓｔｍｅｎｔ　ｆｒｅｑｕｅｎｔｌｙ　ｔｏ　ｔｈｅ　ｐｒｏ—　ｄｕｃｔｉｏｎ　ｏｆ　ｔｈｅ　ｍｉｄｄｌｅ　ｔｒｅｅ，ｉｔ　ｉｓ　ｖｅｒｙ　ｔｅｄｉｏｕｓ．Ｔｈｉｓ　ａｒｔｉｃｌｅ　ｐｒｏｐｏｓｅｓ　ｏｎｅ　ｓｉｍｐｌｅ　ｍｅｔｈｏｄ　ｏｎ　ｔｈｉｓ　ｑｕｅｓｔｉｏｎ．　Ｋｅｙ　ｗｏｒｄｓ：ＡＶＬ　ｔｒｅｅ；Ｂａｌａｎｃｅｄ　ｂｉｎａｒｙ　ｔｒｅｅ；Ｔｗｏ　ｆｏｒｋｓ　ｔｈｅ　ｓｅａｒｃｈ　ｔｒｅｅ　［责任编辑：Ｄ］