通常,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)。本文仅代表作者个人观点,不代表守望者的本意。如有违法侵权内容,请提交到守望者管理员处,立即处理。 |
行业聚焦 面试交流 职位推荐 开发视频 技术交流 腾讯微博 新浪微博
友情链接:课课家教育 阿里云 鲜果 W3Cfuns前端网 中国企业家 环球企业家 投资界 传媒梦工场 MSN中文网 Android开发者社区 cnbeta 投资中国网 又拍云存储 美通说传播 IT茶馆 网商在线 商业评论网 TechOrange IT时代周刊 3W创新传媒 开源中国社区 二维工坊 Iconfans 推酷 智能电视网 FreeBuf黑客与极客 财经网 DoNews 凤凰财经 新财富 eoe移动开发者社区 i黑马 网易科技 新浪科技 搜狐IT 创业家 创业邦 腾讯财经 福布斯中文网 天下网商 TechWeb 雷锋网 新浪创业 和讯科技 品途O2O 极客公园 艾瑞网 抽屉新热榜 卖家网 人民网通信频道 拉勾网 创新派 简单云主机
手机版|黑名单|守望者 成才网 在线教育 linux 高级程序设计 C/C++ 大数据
( 蜀ICP备14029946号 )
成都守望者科技有限公司 © 2013-2016 All Rights Reserved