[Algorithm]이원 탐색 트리(Binary Search Tree)

• 특징: 임의 키를 가진 원소를 삽입, 삭제, 검색하는데 효율적인 자료구조
• 정의: 모든 원소는 상이한 키를 가짐 + 왼쪽 키 < 루트 키 < 오른쪽 키

• 원소 탐색 방법:

       - 키 값= x, 루트에서 탐색 시작 -> 공백일 시 실패로 종료 -> 루트키가 x이면 성공으로 종료

       - 키 값 x < 루트 키 일때, 왼쪽 서브트리만 탐색, 또는 반대로

       - 알고리즘

    public BinaryTree find(String x) {
      BinaryTree T = btree;
      int result;

      while (T != null) {
         // 비교를 해서 data보다 작음으로 왼쪽 링크를 쫒아감.
         if ((result = x.compareTo((String) T.data)) < 0) {
            // 왼쪽 링크 쫓아감
            T=T.llink;
         }
         // 비교를 해서 data와 같으므로 검색된 data를 반환함.
         else if (result == 0) {
            return T;
         }
         // 비교를 해서 data보다 큼으로 오른쪽 링크를 쫒아감.
         else {
            // 오른쪽 링크 쫓아감
            T=T.rlink;
         }
      }
      return T;
   }
}

 

• 원소 삽입 방법:

searchBST(B,x)

        - 알고리즘 

private BinaryTree insertKey(BinaryTree T, String x) {
   // 공백노드일시 최상위 노드에 삽입
   if (isEmpty(T)) {
      // 왼쪽, 오른쪽 링크는 null로 데이터는 x인 이진트리 생성
      BinaryTree newNode = new BinaryTree(null, x, null);
      return newNode;
   }
   // 입력된 문자열이 data보다 작으면 왼쪽 링크에 삽입
   else if (x.compareTo((String) T.data) < 0) {
      // 왼쪽 링크에 다시 insertKey를 사용하여 반환값 저장
      T.llink=insertKey(T.llink,x);
      return T;
   }
   // 입력된 문자열이 data보다 크면면 오른쪽 링크에 삽입
   else if (x.compareTo((String) T.data) > 0) {
      //오른쪽 링크에 다시 insertKey를 사용하여 반환값 저장
      T.rlink=insertKey(T.rlink, x);
      return T;
   } 
   else {
      return T;
   }
}

• 원소 삭제 방법:

       - 삭제하고자 하는 키 값의 원소 탐색 -> 노드 발견 시 삭제 연산

     

 

a. 자식이 없는 리프 노드 삭제

  ->부모 노드의 해당 링크 필드를 null로 변경 후 삭제

 

 

 

 

b. 자식이 하나인 노드 삭제

  -> 삭제되는 노드 자리에 자식 노드를 위치시킴

 

 

 

 

c. 자식이 둘인 노드 삭제

 -> 삭제되는 노드 자리에: 왼쪽 서브트리에서 제일 큰 원소 or 오른쪽 서브 트리에 제일 작은 원소로 대체

 

 

• 이원 탐색 트리의 결합과 분할

      1. 3원 결합: threeJoin(aBST,x,bBST,cBST)

        - 새로운 트리노드 cBST생성 -> key값이 x -> Left링크 필드에 aBST, Right 링크 필드에 bBST설정

        - 결합을 위한 조건: aBST의 모든 원소 < x,  bBST의 모든 원소 > x

        - 새로운 이원 탐색 트리의 높이 = max{height(aBST), height(bBST)} + 1

      2. 2원 결합: twoJoin(aBST,bBST,cBST)

        - aBST와 bBST를 결합하여 하나의 이원 탐색 cBST를 생성함

        - 결합을 위한 조건: aBST 모든 키 < bBST 모든 키

        - cBST의 높이: max{height(aBST), height(bBST)} + 1

           a. aBST에서 키 값 가장 큰 원소 삭제 후 threeJoin(aBST', max, bBST, cBST) 실행

            b. bBST에서 가장 작은 원소 삭제

     3. 분할: split(aBST, x, bBST, cBST)

       - 이원 탐색 트리 aBST를 주어진 키 값 x를 기준으로 b,c로 분할

       - 조건: bBST에서 x보다 작은 키 가진 aBST의 모든 원소 포함,  cBST는 x보다 큰 키값을 가진 aBST모두 포함, 

                  키 x가 aBST에 있다면 true, 아니면 false를 반환

       - 분할 연산: split(aBST, x, bBST, cBST)

          i) aBST 루트 노드의 키 = x: x의 왼쪽 서브트리는 bBST + 오른쪽 서브트리는 cBST

          ii) 루트노드 키 값 > x:  루트, 오른쪽 서브트리 ⊂ cBST

          iii) 루트노드 키 값 < x: 루트, 왼쪽 서브트리 ⊂ bBST

        * 분할 연산 알고리즘

split(aBST, x, bBST, cBST)
   small <- getTreeNode();  //키 값 x보다 큰 원소로된 BST
   large <- getTreeNode();  //키 값 x보다 작은 원소로된 BST
   S <- small;   //smallBST 순회 포인터
   L <- large;   //largeBST 순회 포인터
   P <- aBST;    //aBST 순회 포인터

     4. 이원 탐색 트리의 수행 시간

        - 트리의 높이 커짐 -> 원소 검색-삽입-삭제 연산 수행 시간 늘어남

        - n 개의 노드 이원 탐색트리의 높이 = n - 1

        - 평균적인 높이 = O(log n)  

 

    + 이진 트리의 기타 주요 연산

      a. 리프 노드인지 확인하는 함수: isLeaf()

public boolean isLeaf() {
   if(llink==null&&rlink==null)
      return true;
    else
       return false;// 왼쪽 링크와 오른쪽 링크가 null인지 확인
}

     b. 이진트리의 노드의 개수를 구하는 함수: size()

public int size() {
   // 왼쪽 링크와 오른쪽 링크가 null이면 반환값 1
   if(llink==null&rlink==null)
      return 1;
   // 왼쪽 링크만 null이면 오른쪽 링크의 크기와 루트의 크기(1)을 더해서 반환
   else if(llink==null&&rlink!=null)
      return rlink.size()+1;
   // 오른쪽 링크만 null이면 왼쪽 링크의 크기와 루트의 크기(1)을 더해서 반환
   else if(llink!=null&&rlink==null)
      return llink.size()+1;
   // 왼쪽, 오른쪽 링크 둘 다 null이 아니라면 왼쪽+오른쪽+루트 크기 반환
   else
      return 1+llink.size()+rlink.size();
}

     c. 이진트리의 리프노드 개수를 구하는 함수: numLeave()

public int numLeaves() {
    if (llink==null && rlink==null) return 1;
    if (llink==null) return rlink.numLeaves();
    // 오른쪽 링크가 null이면 왼쪽 링크의 numLeaves 호출
   if(rlink==null) return llink.numLeaves();
    // 왼쪽, 오른쪽 링크가 null이 아니면 왼쪽과 오른쪽 링크의 numLeaves를 더함
   return 1+ rlink.numLeaves()+llink.numLeaves();
  }