데이터 구조 이 진 트 리 학습 (binary search tree)

LLVM 의 Immutableset 을 배우 기 위해 그 밑 에 있 는 실현 은 AVL 트 리 (균형 이 진 트 리) 입 니 다. 저 는 이 트 리 에 익숙 하지 않 습 니 다. 대체적으로 알 지만 잘 모 르 기 때문에 이 진 트 리 를 먼저 배 워 야 합 니 다.
두 갈래 검색 트 리 나 두 갈래 검색 트 리 라 고 하 는데 Dictionary 사전 을 실현 하 는 데 사용 할 수 있 습 니 다. 사전 은 K, V 키 값 의 집합 입 니 다.일반 Dictionary 는 중복 되 는 K 를 포함 하지 않 습 니 다.Dictionary 의 추상 적 인 데이터 형식 규범 은 다음 과 같이 정의 할 수 있 습 니 다.

interface Dictionary<K extends Comparable<K>, V> {
	//               。
	public boolean isEmpty();
	//         k   <K,V>  ，     。 
	public Entry<K, V> get(K k); 
	//       k,v  ，                v。
	public void insert(K k, V v);
	//         k,v  。
	public void remove(K k);
}

이 진 트 리 의 정 의 는 4 가지 가 있 습 니 다. 책 을 참조 하면 됩 니 다.우리 가 가장 주목 해 야 할 것 은 이 진 트 리 에서 왼쪽 트 리 에 있 는 키 는 뿌리 보다 작 고 오른쪽 트 리 의 키 는 뿌리 보다 크다 는 것 이다.isEmpty, get, insert, remove 등 을 어떻게 실현 하 는 지 구체 적 으로 배 워 보 겠 습 니 다.
노드 와 나무의 구 조 를 다음 과 같이 가정 합 니 다 (방법 은 BSTree 류 에서 이 루어 집 니 다).

//        。
class TreeNode<K, V> {
	TreeNode left;  //    
	TreeNode right; //    
	K key;	       //  
	V value;        //    
}

//          。
class BSTree<K, V> implements Dictionary {
	TreeNode<K, V> root;  //    。
}

방법 isEmpty 는 비교적 간단 하 며 루트 가 비어 있 는 지 판단 하면 됩 니 다.더 이상 검토 할 필요 없어.
방법 get 은 다음 과 같 습 니 다:
 

  //   BSTree   .
  public TreeNode get(K k) {
    if (this.root == null) return null; //       
    return this.root.find(k);
  }

  //   TreeNode   。
  public TreeNode find(K k) {
    TreeNode<K, V> node = this;
    while (node != null) {
      int c = k.compareTo(node.getKey());
      if (c < 0) 
        node = node.getLeft();	//      。
       else if (c > 0)
        node = node.getRight();	//      。
       else
      return node;	//    。(c == 0)
    }
    return null;	//     。
  }

여기 서 두 갈래 로 나무의 핵심 성질 을 찾 았 습 니 다. compare 결과 에 따 르 면 k 가 현재 노드 의 키 보다 작 으 면 왼쪽 트 리 를 찾 고 크 면 오른쪽 트 리 를 찾 습 니 다. 같 으 면 자신 입 니 다.재 귀적 인 방법 으로 찾 아 볼 수도 있 지만 효율 적 으로 는 이렇게 쓰 는 것 보다 못 할 수도 있다.
insert 방법 은 다음 과 같 습 니 다.

  public void insert(K k, V v) {
    if (k == null) throw new NullPointerException("k");
    TreeNode<K, V> new_node = new TreeNode<K, V>(k, v);
    if (this.root == null) {
      //     ，         。
      this.root = new_node;
      return;
    }
    
    //       k     p, pp    p     。
    TreeNode<K, V> p = this.root, pp = null;
    while (p != null) {
      pp = p;    //    p       ，  pp     p     。
      int c = k.compareTo(p.getKey());
      if (c < 0)   //      。
        p = p.getLeft();
      else if (c > 0)    //      。
        p = p.getRight();
      else {    // p   key    k，      ，    v   。
        p.setValue(v);
        return;
      }
    }
    
    //       ，  p == null, pp       ，         pp   （ 、         ）
    if (k.compareTo(pp.getKey()) < 0)  // k < pp.key        pp     
      pp.left = new_node;
    else
      pp.right = new_node;
  }

 remove 는 다음 과 같 습 니 다.

  private TreeNode<K, V> internal_remove(K k) {
    if (this.root == null) return null;    //            。
    TreeNode<K, V> p = this.root, pp = null;
    
    //           k     p，       pp。
    //    pp   null    p      root。
    while (p != null) {
      int c = k.compareTo(p.getKey());
      if (c == 0) break;
      pp = p;
      p = (c < 0) ? p.left : p.right;
    }
    if (p == null) return null;     //           。
    
    //    p        ，pp      (    null)。
    if (p.left == null || p.right == null) {
      //    p         ，           p   。
      set_pp_child(pp, p, p.left != null ? p.left : p.right);
    } else {
      // p      。    left.max or right.min     p。           (min)。
      TreeNode<K, V> pR = p.right;
      if (pR.left == null) {
        //           ，   p_right    p   。
        pR.left = p.left;
        set_pp_child(pp, p, pR);
        return p;
      }
      
      // p      pR     ，           -- rmin。
      TreeNode<K, V> rmin = internal_remove_rmin(pR);
      rmin.left = p.left;    //   rmin    p，     rmin.left, .right
      rmin.right = pR;
      set_pp_child(pp, p, rmin);
    }
    return p;
  }
  
  
  //             (pR.min)，       。
  private TreeNode<K, V> internal_remove_rmin(TreeNode<K, V> pR) {
    if (pR.left == null) throw new java.lang.RuntimeException("pR.left is null");
    
    TreeNode<K, V> rmin = pR.left, rmin_pp = pR;  // rmin_pp   rMin     。
    while (rmin.left != null) {
      rmin_pp = rmin;
      rmin = rmin.left;    //          ，    pR.min。
    }
    
    //    rmin = pR.min, rmin_pp = rmin.parent。
    assert (rmin.left == null);    //    rmin         。
    rmin_pp.left = rmin.right;
    rmin.right = null;
    return rmin;
  }
  
  private void set_pp_child(TreeNode<K, V> pp, TreeNode<K, V> p, TreeNode<K, V> child) {
    if (pp == null)
      this.root = child;    //       ，     child
    else if (pp.left == p)
      pp.left = child;    // p   pp     ，    child
    else 
      pp.right = child;    // p   pp     ，    child
  }
  

remove 방법의 실현 은 좀 서 툴 러 보인다.
binary search tree 를 편리 하 게 연구 하기 위해 자바 애플 릿 을 만 들 었 습 니 다. 여기 있 습 니 다:http://vdisk.weibo.com/s/3dT-U/1331863473
이 프로그램 은 명령 find, insert, delete, dump 등 구 조 를 입력 하고 이 진 트 리 를 볼 수 있 습 니 다.도움말 은 help 이 고, exit 로 종료 합 니 다.
다음 단 계 는 이 진 트 리 를 기반 으로 AVL 트 리 구현 / 학습 을 준비 합 니 다.