给jdk写注释系列之jdk16容器(7)-treemap源码解析-java开发java经验技巧

《给jdk写注释系列之jdk16容器(7)-treemap源码解析-java开发java经验技巧》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、给jdk写注释系列Zjdkl.6容器⑺-TrccMap源码解析-编程开发技术给jdk写注释系列之jdkl.6容器（7）-TreeMap源码解析原乂出处：吞噬天谄本系列：给jdk写注释系列Zjdkl.6容器（1）-ArrayList源码解析给jdk写注释系列之jdkl.6容器（2）-LinkedList源码解析给jdk写注释系列之jdkl.6容器（3）:Iterator设计模式给jdk写注释系列Zjdkl.6容器（4）-HashMap源码解析给jdk写注释系列Zjdkl.6容器（5）-LinkedHashMap源码解析给jdk写注释系列之jdkl.6容器（6）-Has

2、hSet源码解析&Map迭代器TreeMap是基于红黑树结构实现的一种Map,要分析TreeMap的实现首先就要对红黑树有所了解。???要了解什么是红黑树，就要了解它的存在主要是为了解决什么问题，对比其他数据结构比如数组，链表，Hash表等树这种结构又有什么优点。1・二叉查询树、红黑树介绍以下为个人理解，有误请拍砖?????下面我尽可能用通俗易懂的语言，简单总结一下数组，链表，Hash表以及树的优缺点。???1.数组，优点：（1）随机访问效率高（根据下标杳询），（2）搜索效率较高（可使用折半方法）。缺点：（1）内存连续且固定，存储效率低。（2）插入和删除效率低（可能

3、会进行数组拷贝或扩容）。???2.链表，优点：（1）不要求连续内存，内存利用率高，（2）插入和删除效率高（只需要改变指针指向）。缺点：⑴不支持随机访问，（2）搜索效率低（需要遍历）。???3.Hash表:优点：（1）搜索效率高,（2）插入和删除效率较高，缺点：（1）内存利用率低（基于数组），（2）存在散列冲突。???上血说的话比较啰嗦，再精炼一下：数组查询好、插入和删除差且浪费内存；链表插入和删除好、查询差；Hash表査询好、插入和删除也不错但是浪费内存。???也就是说，杏询好的插入和删除就差，插入和删除好的杏询就差，好不容易有一个杏询、插入和删除都不错的，但是却乂

4、浪费内存。哎，好苦恼啊，怎么办呢，愁死我啦。能不能做到查询、插入、删除效率都很高，又不浪费内存呢。答案当然是不能！哎，还是好愁人，烦死啦。但是可以做到查询、插入、删除效率比较高，又不浪费内存。哇塞，这是什么东东,这么牛掰，这就是二叉查询树（乂叫二义排序树，乂叫二叉搜索树）。你说二义树这么好，那有什么缺点吗，有！就是算法复杂。???那么什么是二叉查找树呢，它又冇哪些特点呢？（以下见于百度百科）???（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；?????（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值;?????（3）左、右了•树也分别

5、为二叉查找树；?????（4）没有键值相等的节点。按照二义査找树存储的数据，对元素的搜索效率是非常高的，比如上图中如果要查找俏为48的节点，只需要遍历4个节点就能完成。理论上，一颗平衡的二叉查找树的任意节点平均杳找效率为树的高度h,即O（lgn）o但是如果二叉杳找树的失去平衡（元素全在一侧）,搜索效率就退化为0（n）,因此二叉查找树的平衡是搜索效率的关键所在。而红黑树就是靠红黑规则来维持二叉查找树的平衡性。（一颗失去平衡的二叉树）简单用代码描述上面的二叉杏找树，试试看：publicclassBinaryTrcc{//二叉树的根节点publicTreeNoderoot

6、Node;//记录搜索深度publicintcount;/***利用传入一个数组來建立二叉树*/publicBinaryTree(int[]data){for(inti二0;i

7、ile(true){//新增的value比节点的value小，则在左子树if(value