索引树及基于索引树的二叉堆.pdf

索引树及基于索引树的二叉堆 何颖 西北工业大学软件学院，西安（710065 ） E-mail：cnheying@ 2 摘 要：本文提出一种性质介于树 与数组之间的数据结构— 索引树。索引树在数据量无限 制的增加但又需要对数据随机访问的情形下具有良好的性能。将索引树应用到二叉堆上，得 到了比传统二叉堆实现动态性能更好的一种二叉堆。 关键词：树，数组，索引树，二叉堆，动态扩张，随机访问 中图分类号：TP311.12 1．引言 树是数据结构中重要的非线性结构，由于其良好的动态性质得以在算法中大量应用。从 存储上看，树的节点可以离散的存储，不必像数组那样必须有固定的大小3 ，而是可以动态 扩张；从操作上看，对树节点的插入/删除、查找、取后继等操作都具有良好的性能特性。 但是树不能随机访问，使得大量基于元素随机访问的算法无法在树的结构上进行。 数组是数据结构中重要的线性结构，由于其良好的随机访问性质得以在算法中大量应 用。从存储上看，数组是连续存储，因此将偏移量作为索引可以在O （1）的时间复杂度内 随机访问数组元素。从操作上看，任何不涉及改变索引的操作都是高效率的。但是数组良好 随机性的基础是连续存储，计算机一次只能提供有限长度的连续空间。而当数组的长度达到 当前连续空间的上限时，必须寻找更大的连续空间，然后将数组复制到新的空间中，从程序 设计的角度来看，这等同于数组的大小必须是固定的。这严重的影响了数组在动态环境下的 使用效率。 本文利用标识根到节点路径的二进制编码来对节点索引，引入一个新的数据类型—索引 树。索引树在许多指标上以lb （n ）的代价兼有树和数组的优点。而对于二叉堆这种特殊结 构来说，利用索引树的特殊性质甚至可以避免lb （n ）的代价，既获得树的动态特性，又具 有数组的高效随机访问特性。 2 ．索引树及其性质 2.1 索引树的索引及其算法 引言中提到对利用标识根到节点的路径的二进制编码来对节点索引的思想。但如何编码 还是个未解的问题，下面我们将从路径的角度先用自然语言描述编码过程，由此可以发现惊 人的自然的结果。 由于任何根到节点的路径都包含根，而且任何非空树都是以根来表示的，所以，对根的 编码先不予考虑。 下面来考虑非根节点的编码。非根节点都是某个节点的儿子，最自然的编码方式就是用 0 表示节点的左儿子，用 1 表示节点的右儿子。 于是对于如下的树就有如图1 所示的编码： 2 由于所有树与二叉树同构，本文所称的树均为二叉树 3 动态数组本质上也是一旦定义了就不能改变大小的 -1- 图1 左0 右1 的编码方式 但是注意到 0，00，000、001、1 之类由于存在前导 0，使得编码并不对应唯一的二进 制数。为了区分不同个数的前导0，将上述编码前加一个1，这样10，100，1000 就对应到 不同的二进制数了，如图2 所示： 图2 增加1 前缀的左0 右1 编码方式 下面给出编码方法的递归定义，定义节点的编码是以它为根的树的编码，用 b （T ）表 示T 树的编码，则： 1 ）T 不是任何树的子树则b （T ） = 1 。 // 即T 是根节点 2 ）T 是t 的左子树则b （T ） = 2*b （t ）。// 即向左生长标记为0 3 ）T 是t 的右子树则b （T ） = 2*b （t ）+1 。// 即向右生长标记为1 这个序列按递增序排列，就是从1 开始的全