文章目录
- Java treeSet-平衡BST-红黑树
- 二叉树排序原理
- BST
- RBT 红黑树
- 关于Java中的TreeSet类
- TreeSet特点
- 继承关系
- TreeSet类中元素的排序方式
本篇文章最初是做leetcode-220-存在重复元素 III的时候参考官方答题思路而整理的一文。 红黑树讲解过于复杂会逐步补充进来。
references:
详解java中的TreeSet集合
TreeSet详解
Java基础知识之容器六TreeSet详解
Java中TreeSet那点事不是事
java TreeMap TreeSet 用法 原理 详解
linux学习21自平衡二叉树和红黑树的原理和特点
二叉树排序原理
对于一个序列[5,11,6,5,23,14],二叉树的排序原理如下
小的存储在左边(负数)大的存储在右边(正数)相等不存储。 
BST
二叉搜索树之所以有不错的搜索效率是因为在往树中插入数值时始终严格的遵守左子节点值比父节点值小右子节点值比父节点大的准则。以搜索 12 为例
从根节点开始 12 比 9 大所以转向右节点 12 比 29 小所以转向左节点 查找完毕。
思考如果数列是递增的那么此时树就是一个链表不能达到搜索时间复杂度为O(logN)的要求因此提出了平衡BST它的所有叶子节点深度差不超过 1。
RBT 红黑树
红黑树是一种半平衡的二叉搜索树它放弃了二叉搜索树的绝对平衡换来了较为简单的可维护性使得二叉搜索树插入新数据以及搜索数据时都具有不错的搜索性能。
之所以说红黑树是一种半平衡的二叉搜索树是因为红黑树中所有叶子节点的深度相差不会超过一倍。
红黑树必须同时满足以下五条特性
- 所有节点要么是红色要么是黑色
- 根节点必须是黑色
- 所有叶子NULLor NIL节点都是黑色的
- 红色节点的两个子节点必须是黑色不能有连续的红色节点
- 从根节点到任意叶子节点黑色节点的数目是相等的
叶子节点最浅的路径必定出现在全是黑色节点的路径最深的路径必定既有黑色节点又有红色节点。性质5要求所有路径的黑色节点数目相等所以对比叶子节点的最深路径和最浅路径时只需考虑最深路径中的红色节点。性质4要求路径中不能出现连续的红色节点所以最深的路径必定是红黑节点相间的这就解释了为什么叶子节点最深的路径最多是最浅的路径的 2 倍。
如果插入和删除操作都遵循红黑树的 5 条规则那么这个树就会始终保持是一个红黑树即一个半平衡树也就能维持树的插入和查询时的优异性能。之所以这么费尽心思的维护一个红黑树是因为实践证明红黑树的这些规则遵循起来是相对简单的。
树节点的左旋和右旋均不改变二叉搜索树的性质β始终介于 A、B之间。
关于Java中的TreeSet类
TreeMap和TreeSet算是java集合类里面比较有难度的数据结构。和普通的HashMap不一样普通的HashMap元素存取的时间复杂度一般是O(1)的范围。而TreeMap内部对元素的操作复杂度为O(logn)。虽然在元素的存取方面TreeMap并不占优但是它内部的元素都是排序的当需要查找某些元素以及顺序输出元素的时候它能够带来比较理想的结果。可以说TreeMap是一个内部元素排序版的HashMap。
TreeSet特点
- 它存储唯一的元素
- 它不保留元素的插入顺序
- 它按升序对元素进行排序
- 它不是线程安全的
在该实现中对象根据其自然顺序以升序排序和存储。该TreeSet中使用平衡树更具体的一个红黑树。
简单地说作为自平衡二叉搜索树二叉树的每个节点包括一个额外的位用于识别红色或黑色的节点的颜色。在随后的插入和删除期间这些“颜色”位有助于确保树保持或多或少的平衡。
继承关系
TreeSet是基于TreeMap实现的。
TreeSet为基本操作add、remove 和 contains提供受保证的 log(n) 时间开销。
TreeSet中的元素支持2种排序方式
- 自然排序
- 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
TreeSet类中元素的排序方式
TreeSet类的add()方法中会把存入的对象提升为Comparable类型 调用对象的compareTo()方法和集合中的对象比较 根据compareTo()方法返回的结果进行存储
创建TreeSet的时候可以指定一个Comparator 如果传入了Comparator的子类对象那么TreeSet就会按照比较器中的顺序排序 调用的对象是compare方法的第一个参数集合中的对象是compare方法的第二个参数
TreeSet构造函数什么都不传默认按照类中Comparable的顺序(没有就报错ClassCastException) TreeSet如果传入Comparator就优先按照Comparator
【本文转自：韩国服务器 http://www.yidunidc.com处的文章,转载请说明出处】