增强Java集合以获得区间树

Question

增强Java集合以获得区间树

javaalgorithmdata-structurestreeinterval-tree

3

我正在阅读Cormen的《算法导论》第14章（增强数据结构），其中他谈到了区间树。以下是他提到的区间树设计方法。

步骤1：底层数据结构

我们选择一棵红黑树，其中每个节点x包含一个区间x:int，而x的键是区间的低端点x.int.low。因此，数据结构的中序遍历按照低端点排序列出区间。

这可以通过声明具有min和max的节点来完成。comparableTo函数应仅比较x.int.low。

步骤2：附加信息

除了区间本身之外，每个节点 x 都包含一个值 x.max，它是存储在以 x 为根的子树中的任何区间端点的最大值。

步骤3：维护信息

我们必须验证插入和删除在 n 个节点的区间树上需要 O(lg n) 的时间。我们可以通过给定区间 x.int 和节点 x 的子节点的 max 值来确定 x.max：

x:max = max(x.int.high; x.left.max; x.right.max)

步骤4：开发新操作

我们唯一需要的新操作是 INTERVAL-SEARCH(T,i)，它在树 T 中找到与区间 i 重叠的节点。如果树中没有与 i 重叠的区间，则该过程返回指向哨兵 T:nil 的指针。

我可以通过AVL树来实现这个，但是出于好奇想知道是否可以增强Java中现有的库，比如TreeSet或其他集合实体，以适应上述设计。如果可以的话，请提供一个示例代码或示例？

- Trying

1

特别是，我认为你无法做到这一点的原因是无法钩入树形旋转事件以更新“max”值。 - Erik P.

@ErikP，谢谢。我已经自己实现了，下面是我的代码。如果您有任何意见，请在评论中提出。 - Trying

1

一种基于AVL的Java实现已经维护，并可在此处获得 https://github.com/Breinify/brein-time-utilities/#intervaltree。 - Philipp

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Trying · Accepted Answer

我的区间树实现，使用AVL树。

public class IntervalTreeAVL<T>{
    private static class TreeNode<T>{
        private T low;
        private T high;
        private TreeNode<T> left;
        private TreeNode<T> right;
        private T max;
        private int height;
        private TreeNode(T l, T h){
            this.low=l;
            this.high=h;
            this.max=high;
            this.height=1;
        }
    }
    private TreeNode<T> root;
    public void insert(T l, T h){
        root=insert(root, l, h);
    }
    private TreeNode<T> insert(TreeNode<T> node, T l, T h){
        if(node==null){
            return new TreeNode<T>(l, h);
        }
        else{
            int k=((Comparable)node.low).compareTo(l);
            if(k>0){
                node.left=insert(node.left, l, h);
            }
            else{
                node.right=insert(node.right, l, h);
            }
            node.height=Math.max(height(node.left), height(node.right))+1;
            node.max=findMax(node);
            int hd = heightDiff(node);
            if(hd<-1){
                int kk=heightDiff(node.right);
                if(kk>0){
                    node.right=rightRotate(node.right);
                    return leftRotate(node);
                }
                else{
                    return leftRotate(node);
                }
            }
            else if(hd>1){
                if(heightDiff(node.left)<0){
                    node.left = leftRotate(node.left);
                    return rightRotate(node);
                }
                else{
                    return rightRotate(node);
                } 
            }
            else;
        }
        return node;
    }
    private TreeNode<T> leftRotate(TreeNode<T> n){
        TreeNode<T> r =  n.right;
        n.right = r.left;
        r.left=n;
        n.height=Math.max(height(n.left), height(n.right))+1;
        r.height=Math.max(height(r.left), height(r.right))+1;
        n.max=findMax(n);
        r.max=findMax(r);
        return r;
    }
    private TreeNode<T> rightRotate(TreeNode<T> n){
        TreeNode<T> r =  n.left;
        n.left = r.right;
        r.right=n;
        n.height=Math.max(height(n.left), height(n.right))+1;
        r.height=Math.max(height(r.left), height(r.right))+1;
        n.max=findMax(n);
        r.max=findMax(r);
        return r;
    }
    private int heightDiff(TreeNode<T> a){
        if(a==null){
            return 0;
        }
        return height(a.left)-height(a.right);
    }
    private int height(TreeNode<T> a){
        if(a==null){
            return 0;
        }
        return a.height;
    }
    private T findMax(TreeNode<T> n){
        if(n.left==null && n.right==null){
            return n.max;
        }
        if(n.left==null){
            if(((Comparable)n.right.max).compareTo(n.max)>0){
                return n.right.max;
            }
            else{
                return n.max;
            }
        }
        if(n.right==null){
           if(((Comparable)n.left.max).compareTo(n.max)>0){
                return n.left.max;
            }
            else{
                return n.max;
            } 
        }
        Comparable c1 = (Comparable)n.left.max;
        Comparable c2 = (Comparable)n.right.max;
        Comparable c3 = (Comparable)n.max;
        T max=null;
        if(c1.compareTo(c2)<0){
            max=n.right.max;
        }
        else{
            max=n.left.max;
        }
        if(c3.compareTo((Comparable)max)>0){
            max=n.max;
        }
        return max;
    }


TreeNode intervalSearch(T t1){
        TreeNode<T> t = root;
        while(t!=null && !isInside(t, t1)){
            if(t.left!=null){
                    if(((Comparable)t.left.max).compareTo(t1)>0){
                    t=t.left;
                }
                else{
                    t=t.right;
                }
            }
            else{
                t=t.right;
            }
        }
        return t;
    }
    private boolean isInside(TreeNode<T> node, T t){
        Comparable cLow=(Comparable)node.low;
        Comparable cHigh=(Comparable)node.high;
        int i = cLow.compareTo(t);
        int j = cHigh.compareTo(t);
        if(i<=0 && j>=0){
            return true;
        }
        return false;
    }
}