[자료 구조] 이진 탐색 트리 (Binary Search Tree(BST))

자바 예제로 설명하는 이진 탐색 트리 (Binary Search Tree(BST))

이진 탐색 트리 예제

이진 탐색 트리 (Binary Search Tree(BST)) 란?

이진 탐색 트리는 트리 자료 구조의 종류 중 1개로써, 각 노드가 최대 2개의 자식(Child) 노드를 가질 수 있는 트리이다. 이진 탐색 트리에서 새로운 노드는 루트 노드부터 비교를 거쳐, 비교된 노드 보다 더 크면 오른쪽 서브 트리로 이동하고, 작으면 왼쪽 서브 트리로 이동해서 계속 크기 비교 후, 알맞은 자리에 삽입된다. 위의 그림에서 3이라는 노드가 삽입될 때, 우선 루트 노드인 33 과 비교 후, 22와 비교 후, 22의 왼쪽 자식 노드로 삽입되는 것 이다.

이러한 특징 덕분에, 이진 탐색 트리(Binary Search Tree)를 중위 순회(Inorder Traversal)로 순회하게 되면, 정렬된 값을 읽을 수 있다. 위의 예제를 Inorder Traversal 로 순회한다면

[3, 22, 26, 33, 44 55, 77]

이 된다

이진 탐색 트리(Binary Search Tree) 는 어디에 쓰일까?

• 이진 암호화
• 데이터 베이스
• 파일 시스템

이진 탐색 트리(Binary Search Tree)는 어떻게 구현되는가?

이진 트리는 추상 자료형이다, 이는 즉 매우 다양한 방법으로 구현될 수 있음을 의미한다. 보통 가장 자주 쓰이는 방법은 싱글 링크드 리스트(Singly Linked List)이다. 우선 아래에 적힌 이진 탐색트리의 Big O 복잡도를 보고 가자.

Operation	Big O Complexity
	Average	Worst
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Search	O(log n)	O(n)

큐(Queue)나 스택(Stack)과 같은 선형 자료 구조들과는 달리, 비선형 자료 구조에서 각각의 오퍼레이션들은 평균(Average)와 최악(Worst) 케이스이라는 두가지 케이스의 Big O 복잡도를 가진다. 이진 탐색 트리(Binary Search Tree)의 경우에 Average(평균) 케이스란 균형이 잘 맞는(Well-Balanced) 트리를 말하며, 최악의 케이스란 아래의 그림과 같은 형태를 띄어 선형 자료 구조와 다른게 없는 상황을 말한다. 아래 그림 예제를 보자.

이진 탐색 트리 최악의 경우

만약 우리가 이진 탐색 트리에 데이터를 33,22,3 순으로 삽입하면, 위의 그림과 같은 구조를 볼 수 있을 것 이다. 이럴 경우에 이진 탐색 트리는 싱글 링크드 리스트와 완전 일치하며, 비선형 자료 구조의 장점을 잃게 된다.

이진 탐색 트리(Binary Search Tree), 왜 중복 노드를 가져서는 안되는걸까?

아래의 자바(Java) 예제 코드를 보면 알겠지만, 이진 탐색 트리(Binary Search Tree)는 매우 직관적이고 단순한 검색 알고리즘을 가지고 있다. 이진 탐색 트리에서 새로운 노드가 더 부모 노드보다 더 크면, 그 노드는 오른쪽에 위치하게 되고, 작으면 왼쪽에 위치하게 된다. 이러한 특성 때문에, 검색 알고리즘은 검색 쿼리와 노드 값을 비교해가며 노드의 위치를 찾아간다.

만약 중복값을 가진 노드가 존재한다 가정할 때, 우리는 두 가지 검색 알고리즘을 만들 수 있을것이다.

첫번째로, 우선 발견되는 노드만 신경쓰고, 중복 노드가 존재할 가능성을 무시하는것이다. 이 경우에 이진 탐색 트리(Binary Search Tree)는 아무런 쓸모가 없고 사용되지 않을 노드를 가지게 되는 것 이고, 결국에 이는 메모리 낭비에 불과하다.

두번째 경우는, 우리가 중복되는 모든 노드를 검색하는 것 이다. 이 경우에 우리 검색 알고리즘은 언제나 중복 노드가 존재한다는 가정을 할 것이고, 결국 모든 중복 노드를 찾기 위해서 언제나 잎(Leaf) 노드, 즉 최 하위 노드까지 검색을 이어가야 하는 그리 좋지 않은 시나리오를 가질 것이다

그렇니, 효율성(Efficiency)을 위해, 특이한 상황이 아니라면 트리는 중복 노드를 가지지 않는다.

아래 코드는 노드(Node) 클래스의 자바(Java) 예제 이다.

public class Node {
public class Node {
 private Node left, right;
 private int data;

 public Node(int data) {
  this.data = data;
  left = null;
  right = null;
 }

 /**
  * 현재 노드에서 중위 순회(inOrder Traversal)을 시작한다.
  */
 public void inOrder() {
  // 회귀 함수(Recursive Call)을 이용, 가장 왼쪽 노드로 이동한다.
  if (left != null) {
   left.preOrder();
  }
  // 그리고 노드를 읽는다.
  System.out.println(data);
  // 그 후 다시 회귀 함수(Recursive Call)을 이용 오른쪽 노드를 읽는다.
  if (right != null) {
   right.preOrder();
  }
 }

 /**
  * 현재 노드에서 전위 순회(PreOrder Traversal)을 시작한다
  */
 public void preOrder() {
  // 현재 노드를 읽는다
  System.out.println(data);
  // 그후 회귀 함수(Recursive Call)을 이용
  // 가장 왼쪽 잎(Leaf)노드로 이동.
  if (left != null) {
   left.preOrder();
  }
  // 그 후 오른쪽 노드를 탐색한다.
  if (right != null) {
   right.preOrder();
  }
 }

 /**
  * 현재 노드에서 후위 순회(PostOrder Traversal)을 시작한다
  */
 public void postOrder() {

  if (left != null) {
   left.postOrder();
  }

  if (right != null) {
   right.postOrder();
  }
  System.out.println(data);
 }

 public Node getLeft() {
  return left;
 }

 public void setLeft(Node left) {
  this.left = left;
 }

 public Node getRight() {
  return right;
 }

 public void setRight(Node right) {
  this.right = right;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

}

아래 코드는 이진 탐색 트리(Binary Search Tree) 클래스의 자바 예제 이다.

public class BinarySearchTree {
 private Node root;// 루트 노드 인스턴스 생성

 // 이진 탐색 트리 생성자
 public BinarySearchTree() {
  root = null;
 }

 public boolean isEmpty() {
  return root == null;
 }

 public void clear() {
  root = null;
 }

 public void inOrder() {
  root.inOrder();
 }

 public void preOrder() {
  root.preOrder();
 }

 public void postOrder() {
  root.postOrder();
 }

 /**
  * 주어진 인터져 t 로 새로운 노드를 생성, 삽입한다
  * 
  * @param 삽입할 인터져 t
  * @return 삽입이 성공하면 true 갑을, 실패하면 false 값을 리턴
  */
 public boolean insert(int t) {
  Node newNode = new Node(t);// 주어진 인터져 t 로 새 노드를 생성
  Node pointer;// 노드를 삽입할 위치까지 트리를 순회해야하니, 포인터 인스턴스를 생성한다
  boolean insertComplete = false;
  if (root == null) {
   // 트리가 empty 상태일 경우, 루트 노드에 삽입
   root = newNode;
  } else {
   pointer = root;
   // while 루프로 순회를 시작한다.
   while (!insertComplete) {
    if (pointer.getData() > t) {
     // 인터져 t 를 각 노드들과 비교하여, 작으면 
     // 왼쪽 자식으로, 크면 오른쪽 자식으로 이동한다
     if (pointer.getLeft() != null) {
      pointer = pointer.getLeft();
     } else {
      pointer.setLeft(newNode);
      insertComplete = true;
      break;
      // 노드 삽입이 완료됬다면, 더이상의 루핑은 불필요하다.
      // break 구문을 이용, 루프를 종료하자
     }
    } else if (pointer.getData() < t) {
     if (pointer.getRight() != null) {
      pointer = pointer.getRight();
     } else {
      pointer.setRight(newNode);
      insertComplete = true;
      break;
     }
    } else {
     // 만약 트리에 이미 중복되는 노드가 존재한다면
     // 삽입은 불필요하다. 그러니 루핑을 종료한다
     break;
    }
   }
  }
  // 삽입이 성공적이라면 true 값을
  // 중복 노드가 존재한다거나, 예상외 상황이 있어서 삽입을 실패했다면 false 값을 반환한다.
  return insertComplete;
 }

 /**
  * 인터져 t 를 가진 노드를 트리에서 제거한다
  * 
  * @param t 제거할 값 인터져 t
  * @return 성공적으로 제거했을 때 true 값을, 실패했을 때 false 값을 리턴한다
  */
 public boolean remove(int t) {
  Node pointer, parentPointer;
  pointer = parentPointer = root;
  while (pointer != null && pointer.getData() != t) {
   // 삭제할 노드를 찾을 때까지 루핑으로 트리를 순회한다
   parentPointer = pointer;// parentPointer 인스턴스가 삭제할 노드의 부모 노드를 참조하도록 한다.
   if (pointer.getData() > t) {
    pointer = pointer.getLeft();
   } else {
    pointer = pointer.getRight();
   }
  }

  if (pointer == null) {
   // 첫번째 상황: 트리에 삭제할 노드가 존재하지 않을때
   return false;
  } else {
   if (pointer == root && pointer.getLeft() == null) {
    // 두번째 상황: 제거할 노드가 루트 노드이고, 루트노드가 왼쪽 자식 노드를 가지지 않을 때
    root = root.getRight();
   } else if (pointer != root && pointer.getLeft() == null) {
    // 세번째 상황: 루트 노드가 아닌 제거할 노드가 왼쪽 자식 노드를 가지지 않을 때
    if (pointer == parentPointer.getLeft()) {
     // 제거할 노드가 부모 노드의 왼쪽에 위치할 때
     parentPointer.setLeft(pointer.getRight());
    } else {
     // 제거할 노드가 부모 노드의 오른쪽에 위치할 때
     parentPointer.setRight(pointer.getRight());
    }
   } else {
    // 네번째 상황: 제거할 노드가 2개의 자식 노드 모두를 가지고 있을 때
    // 이러한 상황에서 우리는 제거할 노드에서 파생된 서브 트리에서 가장 큰 노드를 검색한 후, 
    // 제거할 노드의 위치에 삽입할 것 이다.
    // BST에서 가장 오른쪽에 위치한 노드는 가장 큰 값을 가졌다는걸 기억하자.
    // 그러니 BST의 왼쪽 서브 트리의 가장 오른쪽에 존재하는 잎(Leaf)노드는 루트 노드의 가장 좋은 대체제 이다.
    Node rightMostNode = pointer;
    // while 루핑을 이용해서 가장 오른쪽 노드로 이동하자
    while (rightMostNode.getRight() != null) {
     rightMostNode = rightMostNode.getRight();
    }
    // 제거할 노드의 데이터 값을 가장 오른쪽 노드의 데이터 값으로 바꿔주자
    pointer.setData(rightMostNode.getData());
    rightMostNode = null;// 오른쪽 노드를 null로 만든다
   }
  }
  return true;
 }

 /**
  * 인터져 t 값을 가진 노드를 검색한다
  * 
  * @param t 검색할 인터져 t
  * @return 존재한다면 true 값을, 그렇지 않다면 false 값을 반환한다.
  */
 public boolean serach(int t) {
  Node pointer;
  if (root.getData() == t) {
   // 루트 노드가 값을 가지고 있는지 확인
   return true;
  } else {
   // 값을 찾을 때 까지 트리를 순회하자
   pointer = root;
   while (pointer != null) {
    if (pointer.getData() > t) {
     pointer = pointer.getLeft();
    } else if (pointer.getData() < t) {
     pointer = pointer.getRight();
    } else {
     // 인터져 t가 노드와 비교 했을 때 크지도 작지도 않다면, 이는 값이 일치함을 말한다. 
     // 루핑을 종료한다
     break;
    }
   }
  }
  // 만약 트리에 인터져 t 값을 가진 노드가 존재하지 않는다면
  // 위의 while 루프에서 트리의 끝까지 여행하게 될거고, 결국 pointer 인스턴스는 null 값을 참조하게 될 것 이다
  // 하지만 트리에 t값을 가진 노드가 존재한다면, pointer 인스턴스는 그 노드를 참조할 것 이다.
  // 그렇니 pointer 인스턴스가 null 값을 가지지 않는다면, 트리에 t 값을 가진 노드가 존재한다고 볼 수 있다.
  return pointer != null;
 }
}