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;
}

待续未完...

相关推荐