首页 > 代码库 > Java集合类汇总记录-- apache.commons4(TreeList)

Java集合类汇总记录-- apache.commons4(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值,整个子树所有节点的索引值都会发生变化。

时空复杂度

TreeList既然是用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。