[ JAVA开发技术 ] 【守望者 j2se】apache-commons库实现TreeList解析

2014-10-11 17:24| 发布者: zhouy | 查看: 1068 | 收藏

摘要: 通常，Tree是Tree，List是List，两者不太可能混在一起。但apache-commons库却用tree实现了实现了List的接口，也就是TreeList类。与标准的LinkedList相比，TreeList稍微浪费一点空间，但常用操作的时间复杂度均降低到 ...

通常，Tree是Tree，List是List，两者不太可能混在一起。但apache-commons库却用tree实现了实现了List的接口，也就是TreeList类。与标准的LinkedList相比，TreeList稍微浪费一点空间，但常用操作的时间复杂度均降低到了O(log N)，值得在开发中权衡利弊、合理应用。

内部数据结构

TreeList内部包含了一个Thread AVL Tree。AVL Tree很常见了，是一种典型的Balanced Binary Tree，但下面简单介绍下Thread Binary Tree。Thread Binary Tree对Binary Tree增加了以下特性：(1)如果一个节点X没有左子树，则把本来应指向左子树的指针，指向中序遍历的前节点；(2)如果一个节点X没有右子树，则把本来应指向右子树的指针，指向中序遍历的后节点。

下图就是一个 Thread Binary Tree ，以节点 5 为例： (1) 节点 5 没有左子树，但节点 5 的中序遍历的前节点是 4 ； (2) 节点 5 没有右子树，但节点 5 的中序遍历的后节点是 6 。这两个特性提高了二叉树依序访问的速度。

以下是TreeList中AVL树节点的定义

static class AVLNode<E> {

/** 左子树或者中序遍历的前节点.*/

private AVLNode<E> left;

/** true表示left字段是左子树；false表示left字段是中序遍历的前节点 */

private boolean leftIsPrevious;

/** 右子树或者中序遍历的后节点 */

private AVLNode<E> right;

/** true表示right字段是右子树；false表示right字段是中序遍历的后节点 */

private boolean rightIsNext;

/** How many levels of left/right are below this one. */

private int height;

/** 在List中的索引相对于父节点索引的偏移量；根节点就是根节点的索引*/

private int relativePosition;

/** 节点所保存的有效荷载 */

private E value;

}

在逻辑上，TreeList中的节点是根据节点在List中的索引来比较大小的。在实现上，AVLNode类保存的是当前节点的索引相对于父节点的偏移量，也就是relativePosition这个字段。这样做的优点是，当向List中间插入一个节点时，插入点之后的所有节点的索引值都变大了，但因为AVLNode保存的是相对值，因此只需要修改特定子树的根节点的relativePosition值，整个子树所有节点的索引值都会发生变化。

时空复杂度

既然是用AVL树实现，则其在特定位置进行插入、删除和get操作的时间复杂度都是O(log N)，另外还要加上较大的时间常量。LinkedList是采用双向链表实现的，其在特定位置进行插入、删除和get操作的时间复杂度都是O(N)。

首先看一下LinkedList中每个节点的定义：

private static class Entry<E> {

E element;

Entry<E> next;

Entry<E> previous;

}

根据以上定义，在32位Hostspot虚拟机下，每个Entry对象占用6*4=24个byte（这包括8个byte的对象头、12个byte的真实字段和4个byte的对齐填充）。根据AVLNode的定义，每个AVLNode节点占用8*4=32个byte（包括8个byte的对象头、22个byte的真实字段和2个byte的对齐填充）。因此，TreeList的每个节点比LinkedLists多占据8个byte。

本文由守望者watchmen收集整理，部分内容源于网络(www.tuicool.com)。本文仅代表作者个人观点，不代表守望者的本意。如有违法侵权内容，请提交到守望者管理员处，立即处理。