범위 조정 BinaryTree를 검색하여 외부 요소를 가져옵니다.

Question

RedBlack [균형, 정렬] 바이너리 트리가 있고 [lower, upper] 범위 내의 모든 값을 찾으려고 검색 중입니다. 이 코드 그래서

public IEnumerable<TData> Range(
     BinaryTree<TData> root, 
     IComparer<TData> comparer, 
     TData lower, 
     TData upper) 
{ 
    var stack = new Stack<State>(16); 
    BinaryTree<TData> here = root; 

    do 
    { 
     if (here == null) 
     { 
      if (stack.Count == 0) 
       break; 

      State popped = stack.Pop(); 
      yield return popped.Data; 
      here = popped.Next; 
      continue; 
     } 

     if (comparer.Compare(here.Data, lower) < 0) 
     { 
      here = here.Right; 
     } 
     else if (comparer.Compare(here.Data, upper) > 0) 
     { 
      here = here.Left; 
     } 
     else 
     { 
      stack.Push(new State {Next = here.Right, Data = here.Data}); 
      here = here.Left; 
     } 
    } while (true); 
} 

, 나는 값

[0, 1, 4, 5, 6, 9], 

및

[3, 8] 

나는 다음을 얻을 것입니다 범위 내의 모든 요소를 ​​검색하여 빌드 트리를 가지고 있다면 검색 결과 :

[4, 5, 6]. 

제 질문은 검색의 바깥 쪽 요소를 얻기 위해이 알고리즘을 조정하는 방법입니다.

[1, 4, 5, 6, 9] 

트리의 1과 4 사이의 값 3 거짓말 즉

, 그래서 유사하게 6과 9 사이의 값 (8) 거짓말과 내가 9가 될 수있는 값에 포함 할 것, 1을 반환하려면이 같은 결과.

한 캐치 내가 루트

에서 검색 현재 NGenerics 일반적인 알고리즘 대답을 받아 들일

[편집]

를 사용하여 구현

를 다시 시작하지 않을 것입니다.

Answer 1

레드 블랙 트리를 채우려 고하는 것이 확실하지 않습니다. 당신이 배열 또는 데이터 (요소 누구의 번호가 변경되지 않습니다)의 스트림을 사용하는 경우 데이터의 증가 또는 감소가있는 경우 그러나 당신은 Segment Tree

class SegmentTree 
{ 
    class Node 
    { 
     int max, min, s, e; 
     Node left, right; 

     @Override 
     public String toString() 
     { 
      String str = "Min: "+this.min+" Max: "+this.max+" "+this.s+"-"+this.e; 
      return str; 
     } 
    } 

    private Node root; 

    public SegmentTree() {} 

    public SegmentTree(int[] array) 
    { 
     add(array); 
    } 

    public void add(int[] array) 
    { 
     root = add(0, array.length-1, array); 
    } 

    private Node add(int s, int e, int[] array) 
    { 
     Node n = new Node(); 
     n.s = s; 
     n.e = e; 

     if(n.s==n.e) 
     { 
      n.min = n.max = array[n.s]; 
      return n; 
     } 

     int mid = s+(e-s)/2; 
     n.left = add(s, mid, array); 
     n.right = add(mid+1, e, array); 
     n.max = Math.max(n.left.max, n.right.max); 
     n.min = Math.min(n.left.min, n.right.min); 

     return n; 
    } 


    // Get the max value between the limits l and r (both inclusive) 
    public int getMax(int l, int r) 
    { 
     return getMax(root, l, r); 
    } 

    private int getMax(Node n, int l, int r) 
    { 
     if(l<=n.s && r>=n.e) 
      return n.max; 
     if(l>n.e || r<n.s) 
      return Integer.MIN_VALUE; 
     return Math.max(getMax(n.left, l, r), getMax(n.right, l, r)); 
    } 

    public int getMin(int l, int r) 
    { 
     return getMin(root, l, r); 
    } 

    private int getMin(Node n, int l, int r) 
    { 
     if(l<=n.s && r>=n.e) 
      return n.min; 
     if(l>n.e || r<n.s) 
      return Integer.MAX_VALUE; 
     return Math.min(getMin(n.left, l, r), getMin(n.right, l, r)); 
    } 
} 

참고

를 사용하여이 갈 수 있습니다 그러면 나무를 재구성해야합니다. 빈번한 삽입/삭제/갱신이있는 경우에는 이것이 전혀 좋은 선택이 아닙니다.
데이터 세트가 있고 특정 범위의 값을 자주 확인해야하는 경우 매우 유용합니다.
최소 및 최대 값을 모두 저장하는 예제를 제공했습니다. 값의 합계 또는 기타 항목을 저장할 수 있습니다. Node
Java로 코드 작성을 사과하십시오.