资讯专栏INFORMATION COLUMN

Java知识点总结(Java容器-TreeSet)

codergarden / 2116人阅读

摘要:知识点总结容器知识点总结容器是接口的唯一实现,可以确保集合元素处于排序状态,底层是一棵排序树。底层使用红黑树算法进行维护,因此性能相对于来说要差一些,因为内部会自动进行排序操作。

Java知识点总结(Java容器-TreeSet)

@(Java知识点总结)[Java, Java容器, JavaCollection, JavaSet]

TreeSet

TreeSet是SortedSet接口的唯一实现,TreeSet可以确保集合元素处于排序状态,底层是一棵排序树。

底层使用红黑树算法进行维护,因此性能相对于HashSet来说要差一些,因为内部会自动进行排序操作。

TreeSet也是线程不安全

排序分为自然排序,定制排序,自然排序是TreeSet内部对add进来的值进行排序,定制排序是对排序条件的限制

手动实现TreeSet

</>复制代码

  1. package mySet;
  2. import java.util.Comparator;
  3. import java.util.Iterator;
  4. import java.util.NoSuchElementException;
  5. /**
  6. * 实现一个简单的TreeSet
  7. * @author george
  8. */
  9. public class MyTreeSet implements Cloneable, java.io.Serializable {
  10. // 为set底层树的结构排序用的比较器 当按照E的自然排序时为null
  11. private final Comparator comparator;
  12. // 头节点
  13. private transient SetNode root = null;
  14. // 节点个数
  15. private transient int size = 0;
  16. /**
  17. * 无参构造,设置比较器为null
  18. */
  19. public MyTreeSet() {
  20. comparator = null;
  21. }
  22. /**
  23. * 构造函数,传入定义好的比较器对象
  24. *
  25. * @param comparator
  26. * :比较器对象
  27. */
  28. public MyTreeSet(Comparator comparator) {
  29. this.comparator = comparator;
  30. }
  31. /**
  32. * 插入对象e到MyTreeSet中
  33. *
  34. * @param e
  35. * :要插入的对象
  36. * @return:返回是否插入成功
  37. */
  38. public boolean add(E e) {
  39. SetNode n = root;
  40. if (n == null) {
  41. root = new SetNode(e, null);
  42. size = 1;
  43. return true;
  44. }
  45. int comp;
  46. SetNode parents;
  47. Comparator cptor = comparator;
  48. // 若比较器不为空 用Comparator进行比较
  49. if (cptor != null) {
  50. do {
  51. parents = n;
  52. comp = cptor.compare(e, n.e);
  53. if (comp < 0)
  54. n = n.left;
  55. else if (comp > 0)
  56. n = n.right;
  57. else {
  58. return false;
  59. }
  60. } while (n != null);
  61. } else {
  62. if (e == null)
  63. throw new NullPointerException();
  64. // 用定义好的自然顺序方法进行排序比较
  65. Comparable cpb = (Comparable) e;
  66. do {
  67. parents = n;
  68. comp = cpb.compareTo(n.e);
  69. if (comp < 0)
  70. n = n.left;
  71. else if (comp > 0)
  72. n = n.right;
  73. else {
  74. return false;
  75. }
  76. } while (n != null);
  77. }
  78. // 找到新元素将来位置的父结点后,将元素实例化成结点插入到树中
  79. SetNode newNode = new SetNode(e, parents);
  80. if (comp < 0)
  81. parents.left = newNode;
  82. else
  83. parents.right = newNode;
  84. size++;
  85. return true;
  86. }
  87. /**
  88. * 返回是否含有元素e
  89. *
  90. * @param e
  91. * @return
  92. */
  93. public boolean contains(E e) {
  94. return getNode(e) != null;
  95. }
  96. /**
  97. * 删除元素e所在的结点
  98. *
  99. * @param e
  100. * @return
  101. */
  102. public boolean remove(E e) {
  103. SetNode node = getNode(e);// 找到元素e所在节点
  104. if (node == null)
  105. return false;
  106. deleteNode(node);// 进行删除
  107. return true;
  108. }
  109. /**
  110. * 找到元素e在树中的结点
  111. *
  112. * @param e
  113. * @return
  114. */
  115. private SetNode getNode(E e) {
  116. SetNode n = root;
  117. int comp;
  118. SetNode parents;
  119. Comparator cptor = comparator;
  120. // 若比较器不为空 用Comparator进行比较
  121. if (cptor != null) {
  122. do {
  123. parents = n;
  124. comp = cptor.compare(e, n.e);
  125. if (comp < 0)
  126. n = n.left;
  127. else if (comp > 0)
  128. n = n.right;
  129. else {
  130. return parents;
  131. }
  132. } while (n != null);
  133. } else {
  134. if (e == null)
  135. throw new NullPointerException();
  136. // 用定义好的自然顺序方法进行排序比较
  137. Comparable cpb = (Comparable) e;
  138. do {
  139. parents = n;
  140. comp = cpb.compareTo(n.e);
  141. if (comp < 0)
  142. n = n.left;
  143. else if (comp > 0)
  144. n = n.right;
  145. else {
  146. return parents;
  147. }
  148. } while (n != null);
  149. }
  150. return null;
  151. }
  152. /**
  153. * 删除树中的节点node 当结点node有左右子女时,往下所搜与node中的元素最为接近的元素的结点
  154. * 找到后将该结点的元素值赋给node,让node指向该结点, 接下来删除这个结点。 注意:最后要去掉的节点的子女个数都是小于2的
  155. *
  156. * @param node
  157. */
  158. void deleteNode(SetNode node) {
  159. size--;
  160. SetNode rep;
  161. if (node.left != null && node.right != null) {
  162. rep = replaceNode(node);
  163. node.e = rep.e;
  164. node = rep;
  165. }
  166. rep = (node.left != null ? node.left : node.right);
  167. if (rep != null) {
  168. rep.parents = node.parents;
  169. if (node.parents == null)
  170. root = rep;
  171. else if (node == node.parents.left)
  172. node.parents.left = rep;
  173. else if (node == node.parents.right)
  174. node.parents.right = rep;
  175. } else {
  176. if (node.parents == null) {
  177. root = null;
  178. }
  179. if (node.parents != null) {
  180. if (node == node.parents.left)
  181. node.parents.left = null;
  182. else if (node == node.parents.right)
  183. node.parents.right = null;
  184. }
  185. }
  186. }
  187. /**
  188. * 找到距离node中的元素大小最近的结点
  189. *
  190. * @param node
  191. * @return
  192. */
  193. SetNode replaceNode(SetNode node) {
  194. if (node == null)
  195. return null;
  196. else if (node.right != null) {
  197. SetNode p = node.right;
  198. while (p.left != null)
  199. p = p.left;
  200. return p;
  201. } else {
  202. SetNode p = node.parents;
  203. SetNode ch = node;
  204. while (p != null && ch == p.right) {
  205. ch = p;
  206. p = p.parents;
  207. }
  208. return p;
  209. }
  210. }
  211. /**
  212. * 清空set集合
  213. */
  214. public void clear() {
  215. size = 0;
  216. root = null;
  217. }
  218. /**
  219. * 返回结点的个数
  220. *
  221. * @return
  222. */
  223. public int size() {
  224. return size;
  225. }
  226. /**
  227. * 找到最小的元素
  228. *
  229. * @return
  230. */
  231. public E first() {
  232. SetNode p = root;
  233. if (p != null)
  234. while (p.left != null)
  235. p = p.left;
  236. if (p.e == null)
  237. throw new NoSuchElementException();
  238. else
  239. return p.e;
  240. }
  241. /**
  242. * 找到最大的元素
  243. *
  244. * @return
  245. */
  246. public E last() {
  247. SetNode p = root;
  248. if (p != null)
  249. while (p.right != null)
  250. p = p.right;
  251. if (p.e == null)
  252. throw new NoSuchElementException();
  253. else
  254. return p.e;
  255. }
  256. /**
  257. * 找到最小的元素所在的结点
  258. *
  259. * @return
  260. */
  261. public SetNode firstNode() {
  262. SetNode p = root;
  263. if (p != null)
  264. while (p.left != null)
  265. p = p.left;
  266. if (p.e == null)
  267. throw new NoSuchElementException();
  268. else
  269. return p;
  270. }
  271. /**
  272. * 迭代器
  273. * @return
  274. */
  275. public Iterator iterator() {
  276. return new KeyIterator(firstNode(), this);
  277. }
  278. }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/69630.html

相关文章

  • Java识点总结Java容器-Set)

    摘要:知识点总结容器知识点总结容器是一种不包括重复元素的。由于接口的特殊性,所有传入集合中的元素必须不同。集合判断两个对象是否相同,是使用方法,而不是使用运算符的。只能存储,所以只会在存储的情况下使用。 Java知识点总结(Java容器-Set) @(Java知识点总结)[Java, Java容器, JavaCollection, JavaSet] Set Set是一种不包括重复元素的Col...

    dack 评论0 收藏0
  • Java识点总结Java容器-Collection)

    摘要:知识点总结容器知识点总结容器函数库是包下的一些接口和类,类是用来产生对象存放数据用的,而接口是访问数据的方式。底层也是数组实现,线程安全,效率低效率高,线程不安全。 Java知识点总结(Java容器-Collection) @(Java知识点总结)[Java, Java容器, JavaCollection] [toc] Collection Collection函数库是java.uti...

    GeekGhc 评论0 收藏0
  • Java集合总结

    摘要:概述集合类主要有大分支,及。不能保证元素的排列顺序,顺序有可能发生变化不是同步的集合元素可以是但只能放入一个是接口的唯一实现类,可以确保集合元素处于排序状态。如果这两个的通过比较返回,新添加的将覆盖集合中原有的,但不会覆盖。 概述 Java集合类主要有2大分支,Collection及Map。Collection体系如下: https://upload-images.jianshu......

    toddmark 评论0 收藏0
  • 关于java集合框架的总结

    摘要:是哈希表实现的,中的数据是无序的,可以放入,但只能放入一个,两者中的值都不能重复,就如数据库中唯一约束。四和的相同点和区别相同两者都是基于哈希表实现的内部也都是通过单链表解决冲突问题同样实现了序列化和克隆接口区别继承的父类不同。 一.Arraylist与LinkedList有什么区别? 1、ArrayList是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率...

    Coding01 评论0 收藏0
  • Java集合问题大汇总

    摘要:集合中成员很丰富,常用的集合有,,等。实现接口的集合主要有。集合中不能包含重复的元素,每个元素必须是唯一的。而以作为实现的构造函数的访问权限是默认访问权限,即包内访问权限。与接口不同,它是由一系列键值对组成的集合,提供了到的映射。 原文地址 Java集合 Java集合框架:是一种工具类,就像是一个容器可以存储任意数量的具有共同属性的对象。 Java集合中成员很丰富,常用的集合有Arra...

    894974231 评论0 收藏0

发表评论

0条评论

codergarden

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<