gpt4 book ai didi

java - 扩充 java 集合以获得区间树

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:51:33 28 4
gpt4 key购买 nike

我正在浏览 Introduction to Algorithms by Cormen第 14 章(增强数据结构),他在其中谈论区间树。下面是他提到的区间树背后的设计方法。

Step 1: Underlying data structure

We choose a red-black tree in which each node x contains an interval x:int and the key of x is the low endpoint, x.int.low, of the interval. Thus, an inorder tree walk of the data structure lists the intervals in sorted order by low endpoint.

这可以通过声明一个具有minmax 的节点来完成。 comparableTo 函数应该只比较 x.int.low

Step 2: Additional information

In addition to the intervals themselves, each node x contains a value x.max, which is the maximum value of any interval endpoint stored in the sub-tree rooted at x.

Step 3: Maintaining the information

We must verify that insertion and deletion take O(lg n) time on an interval tree of n nodes. We can determine x.max given interval x.int and the max values of node x’s children:

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

Step 4: Developing new operations

The only new operation we need is INTERVAL-SEARCH(T,i), which finds a node in tree T whose interval overlaps interval i. If there is no interval that overlaps i in the tree, the procedure returns a pointer to the sentinel T:nil.

我可以通过 AVL 树 实现它,但出于好奇想知道我们是否可以扩充 java 中的现有库,如 TreeSet 或其他集合实体 以适应上述设计。如果是这样,您能否提供示例代码或示例?

最佳答案

我的区间树实现 AVL tree .

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

关于java - 扩充 java 集合以获得区间树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18922461/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com