Intervaltree DeleteNode Java 구현

StackOverflow https://stackoverflow.com/questions/1418150

  •  07-07-2019
  •  | 
  •  

문제

나는 필요하다 IntervalTree 또는 Java의 Rangetree 구현이며, 삭제 지원이 작동하는 것을 찾는 데 어려움이 있습니다.

내장이 내장되어 있습니다 sun.jvm.hotspot.utilities.intervaltree, 하지만 deleteNode RBTREE 슈퍼 클래스 상태의 방법 :

/**
 * 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.
 */

트리에서 노드를 삭제하려고하면 예외가 발생합니다.

노드의 최대 종말점은 제대로 업데이트되지 않았습니다

제대로 구현하는 것이 얼마나 어려울까요? delete sun.jvm.hotspot.utilities.intervaltree의 서브 클래스에서의 기능? 아니면 이미 올바르게 구현하는 또 다른 인터벌 트리 구현이 있습니까?

현재 나는 단지 삭제가있을 때마다 나무를 닦고 그것을 다시 채색하고 있습니다. 이는 이상적이지 않습니다 (참고 : RBTREE의 디버깅 설정 = false는 엄청나게 물건을 뿌립니다).

도움이 되었습니까?

해결책

나는 결국 수정했다 sun.jvm.hotspot.utilities.IntervalTree 삭제 된 노드 세트를 유지합니다. 검색을 수행 할 때이 세트의 항목을 제외합니다. 이상적이지는 않지만 이것은 "실제"삭제 작업을하는 것보다 훨씬 쉬웠습니다. 삭제 된 세트가 너무 커지면 트리를 재건합니다.

다른 팁

이 프로젝트 더 많이 사용할 수있는 rangetree 구현이 있습니다. Sun 패키지는 빠르고 더 큰 용도로 사용하기에는 괜찮을 수 있지만, 중요한 것을 구축하는 것은 권장하지 않습니다. 태양은 그들을 안정적으로 유지하지 않을 수 있습니다.

나는 당신의 정확한 요구 사항을 모르지만 비 정적 세그먼트 트리가 당신에게 효과적 일 수 있습니다. 그렇다면 살펴보십시오 레이아웃 관리 SW, 특히 세그먼트 트리 패키지. 필요한 제거 기능이 있습니다.

직접 굴리기로 결정했다면 오픈 소싱을 제안 할 수 있습니까? 이미 열려 있고 쉬운 간격 트리가 없다는 것에 놀랐습니다.

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

삭제 된 오픈 소스 구현을 발견했지만 완전히 기능하게 만들기 위해 약간의 노력을 기울입니다.

더 큰 오픈 소스 프로젝트의 모듈입니다 Gephi, 그러나 여기에 있습니다 출처 그리고 Javadoc. 항아리를 원한다면 Gephi를 설치할 수 있으며 다음과 같습니다.

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

삭제 방법은 입력 간격과 겹치는 모든 간격을 제거합니다 (입력 단지 입력 대신). 그러나 Soruces에서 특정 노드 (한 간격을 저장하는)를 제거하는 개인 메소드가 있음을 발견했습니다. 또한 개인 검색 방법은 노드를 반환합니다.

따라서 약간의 노력으로 코드를 리팩터링하고 '특정 간격 삭제'기능을 가질 수 있다고 생각합니다. 가장 빠르고 가장 더러운 방법은 개인 메소드/노드 클래스를 공개하는 것입니다. 그러나 오픈 소스 프로젝트이기 때문에 미래에 좋은 인터벌 트리의 우수한 표준 구현으로 발전 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top