IntervalTree DeleteNode Java 구현

Question

Java에서 IntervalTree 또는 RangeTree 구현이 필요하며 삭제 작업이 지원되는 것으로 찾는 데 문제가 있습니다.

가가의 sun.jvm.hotspot.utilities.IntervalTree에 하나의 내장,하지만 RBTree 슈퍼 클래스 상태에서 deleteNode 방법 :

/** 
* FIXME: this does not work properly yet for augmented red-black 
* trees since it doesn't update nodes. Need to figure out exactly 
* from which points we need to propagate updates upwards. 
*/ 

이 나무가 예외를 던지는 끝에서 노드를 삭제하려고 :

노드의 최대 엔드 포인트가 업데이트되지 않았습니다.

sun.jvm.hotspot.utilities.IntervalTree의 하위 클래스에 delete 기능을 올바르게 구현 하시겠습니까? 아니면 이미 올바르게 구현 한 다른 인터벌 트리 구현이 있습니까?

현재 삭제가 발생할 때마다 트리를 닦아서 다시 채우는 것이 이상적입니다 (참고 : RBTree의 DEBUGGING = false 설정은 엄청나게 빨라졌습니다).

Answer 1

삭제 된 노드 집합을 유지하기 위해 sun.jvm.hotspot.utilities.IntervalTree을 수정했습니다. 검색을 수행 할 때이 세트의 항목을 제외합니다. 이상적은 아니지만 "실제"삭제 작업을하는 것보다 훨씬 쉽습니다. 삭제 된 집합이 너무 커지면 트리를 다시 작성합니다.

Answer 2

This project에는 더 유용 할 수있는 RangeTree 구현이 있습니다. 태양 패키지는 신속하고 지저분한 사용을 위해 괜찮지 만, 나는 그 패키지에 의존하는 중요한 것을 만드는 것을 권장하지 않습니다. Sun은 안정적으로 유지하지 못할 수도 있습니다.

Answer 3

정확한 요구 사항을 모르지만 비 정적 세그먼트 트리가 도움이 될 수 있습니다. 그렇다면 Layout Management SW, 특히 SegmentTree package을 확인하십시오. 그것은 당신이 필요로하는 제거 기능이 있습니다.

자신의 롤을 결정했다면 오픈 소싱을 제안해도 될까요? 이미 열려 있고 쉬운 간격 트리가 없다는 것에 놀랐습니다.

Answer 4

증강 된 AVL 트리 @http://code.google.com/p/intervaltree/을 기반으로 한 C# 구현이 있습니다. 자바로 번역하기가 너무 어렵지 않아야합니다.

Answer 5

삭제가 포함 된 오픈 소스 구현을 발견했지만 완벽하게 작동하기위한 노력이 필요합니다.

더 큰 오픈 소스 프로젝트 Gephi의 모듈이지만 여기는 sources과 javadoc입니다. 당신이 Gephi를 설치할 수 있습니다 항아리를 원하고, 그것에서의 경우 :

/gephi/modules/org-gephi-data-attributes-api.jar 

거기 삭제 방법, 입력 간격 (대신 단지 입력 한)와 중복되는 모든 간격을 제거합니다. 그러나 나는 특정 노드 (하나의 간격을 저장하는)를 제거하는 개인적인 방법이 있다는 것을 발견했다. 또한 개인 검색 방법은 노드를 반환합니다.

그래서 약간의 노력으로 코드를 리팩토링하고 '특정 간격 삭제'기능을 사용할 수 있다고 생각합니다. 가장 빠르고 가장 더러운 방법은 private 메소드/Node 클래스를 public으로 만드는 것입니다. 하지만 오픈 소스 프로젝트이기 때문에 앞으로는 인터벌 트리의 좋은 표준 구현으로 진화 할 수있을 것입니다.