이진 탐색 트리

트리란?  

- 트리는 비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조다.

 

 - 트리를 구성하는 원소를 노드라고 하고 노드를 연견하는 선을 간선(edeg)이라 한다.

 - A에는 12개의 노드가 있다.

 - 트리 시작을 루트노드라 하고 레벨 0이 된다.

 - 같은 부모의 자식 노드들은 서로 형제노드 (Sibling Node)가 된다.

 - 자식노드들은 각각 독립하여 새로운 트리를 구성할 수 있으므로 각 노드는 자식노드 수만큼의 서브트리를 갖는다.

 - 한 노드가 가지는 서브 트리의 수, 즉 자식노드의 수를 그 노드의 차수(degree)라 한다.

 - 차수가 0인 노드 즉 자식이 없는 노드를 리프 노드(Leaf Node) 또는 단말 노드라 한다.

 - 여러 트리들의 집합을 포리스트라고 한다.

 

이진 탐색 트리란?

 - 탐색을 위한 자료구조로 이진 트리를 사용하기 위해서 저장할 데이터의 크기에 따라 노드의 위치를 정의한 것

 

이진 탐색 트리의 정의

(1) 모든 원소는 서로 다른 유일한 키를 갖는다.

(2) 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다.

(3) 오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다.

(4) 왼쪽 서브 트릐와 오른쪽 서브 트리도 이진 탐색 트리이다.

 

 

이진 탐색 트리에서 탐색 연산

1. 탬색은 항상 루트노드에서 시작

2. (키값 x= 루트 노드의 키값) 인 경우 : 원하는 원소를 찾았으므로 탐색 연산 성공

3. (키값 x < 루트 노드 키 값) 인 경우 : 루트 노드의 왼쪽 서브트리에 대해서 탐색 연산 수행

4. (키값 x > 루트 노드의 키값) 인 경우 : 루트 노드의 오른쪽 서브 트리에 대해서 탐색 연산 수행

 

예) 원소 11 탐색하기
① 찾는 킷값 11을 루트노드의 킷값 8과 비교
(찾는 킷값 11 > 노드의 킷값 8) 이므로 오른쪽 서브트리를 탐색
② (찾는 킷값 11 > 노드의 킷값 10) 이므로, 다시 오른쪽 서브트리를 탐색
③ (찾는 킷값 11 < 노드의 킷값 14) 이므로, 왼쪽 서브트리를 탐색
④ (찾는 킷값 11 = 노드의 킷값 11) 이므로, 탐색 성공! (연산 종료)

 

 

 

트리 구현하기

 

public class SimpleTree<E extends Comparable> {
   private E value;
   private SimpleTree<E> left;
   private SimpleTree<E> right;

   public SimpleTree(E toInsert) {
      this.value = toInsert;
   }

   public boolean search(final E toFind) {
      if (toFind.equals(value)) {
         return true;
      }

      if (toFind.compareTo(value) < 0 && left != null) {
         return left.search(toFind);
      }

      return right != null && right.search(toFind);
   }

   public void insert(final E toInsert) {
      if(toInsert.compareTo(value) < 0) {
         if(left == null) {
            left = new SimpleTree<>(toInsert);
         } else {
            left.insert(toInsert);
         }
      } else {
         if (right == null) {
            right = new SimpleTree<>(toInsert);
         } else {
            right.insert(toInsert);
         }
      }
   }

 - 원소의 값이 찾는 값과 같으면 첫 번째 if문에서 값 찾기를 끝냄

-  찾는 값이 현재 노드보다 작고 왼쪽 자식 노드가 null이 아니면 두번째 if문을 통해 왼쪽 노드를 검색해 값을 찾음.

 - 반대로 오른쪽 노드가 null이 아니면 오른쪽 노드를 검색해 값을 반환

 - 자식 노드가 없으면 트리의 끝에 도착헌 것이며 찾으려는 값이 트리에 없다.

 

 

- 트리를 따라가면서 각 노드의 값을 입력하려는 값과 비교해서 입력하려는 값이 현재 노드의 값보다 작으면 왼쪽 반대라면 오른쪽으로 이동

 

 

 - 객체 지향 프로그래밍에서는 Null 객체 패턴을 이용해 메서드를 단순화 할 수 있으며 null 값을 확인 하는 과정도 제외 시킬 수 있다.

 - 이 방법은 값을 가진 노드와 트리의 끝을 표현하는 리프 라는 두 가지 타입의 노드로 트리를 구성한다.

 

 

 - 이러한 접근법은 불균형한 트리를 만들 수 도 있다는 점에서 신경을 써야함/

 - 초기에 균형 잡힌 이진 탐색 트리의 특정 구현방법으로 생겨난 가념이 AVL트리(Adelson-Velskii and Landis' tree) 이다.

 

 - AVL트리는 어떤 노드는 모든 자식의 깊이 차이가 1을 넘지 않도록 만든다. 즉 노드에 삽입이나 삭제를 한 후 왼쪽과 오른쪽 부분 트리가 맞는지 확인 한 다음

   AVL  트리의 속성인 깊이 차이가 1을 넘지 않도록 한다는 점에 부합 되도록 값을 재배열

 

 - 참고로 보통 트리의 균형이 맞을 때는 검색이나 삽입, 삭제할 때O(log n)의 처리 시간이 소요된다.