Java数据结构系列（1）——自平衡二叉树

1、基本概念

所谓自平衡二叉树，就是当我们插入或删除元素之后，二叉树的高度会自动调整到最小，这样我们就可以在对数时间内查找二叉树内的元素。

2、定义

TreeSet<Elemtype> set=TreeSet<>();

3、基本函数

set.ceiling(x)    // 取set中大于等于x的最小值，没有就返回空
set.floor(x)      // 取set中小于等于x的最大值，没有就返回空set.size()        // 返回树的大小set.remove()      // 移除树中元素set.add()         // 向树中添加元素

 

4、运用——LeetCode题

题目描述：给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 k。

输入: nums = [1,2,3,1], k = 3, t = 0
输出: true

分析：对于这道题，我们最主要的就是运用滑动窗口，然后查找窗口内的值是否满足要求。而对于查找问题，我们使用自平衡二叉树，就可以在对数级别内实现。

算法：用自平衡二叉树保存窗口里面的值。

• 如果树中大于等于x的最小值s，s<=x+t ，则返回true
• 如果树中小于等于x的最大值g，x<=g+t ，则返回true
• 将x存入树中，当树中元素大于窗口大小k，则删除最小进入树中的元素，循环直到结束。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/contains-duplicate-iii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
　　TreeSet<Integer> set=new  TreeSet<>();
　　for(int i=0;i<nums.length;++i){
　　　　Integer s=set.ceiling(nums[i]);
　　　　if(s!=null && s<=nums[i]+t) return true;
　　　　Integer g=set.floor(nums[i]);
　　　　if(s!=null && nums[i]<=g+t) return true;
　　　　set.add(nums[i]);
　　　　if(set.size()>k){
　　　　　　set.remove(nums[i-k]);
　　　　}
　　}
　　return false;
}

待续未完...