트리 (Tree)

트리 (Tree)

지금까지는 리스트, 스택, 큐 등의 선형 자료 구조(Linear Data Structure)만을 공부했습니다.

 - 선형 자료 구조는 자료들이 직선과 같이 나열되어 있는 구조를 의미합니다.

만약 선형이 아니고 자료가 계층적인 구조를 가지고 있다면 어떻게 해야할까요?

 - 조상과 자손, 전체와 부분, 상사와 부하직원, 컴퓨터의 디렉토리 구조 등의 계층적 관계입니다.

 - 이런 계층적인 관계를 표현하기에는 선형 자료 구조로는 한계가 있습니다.

트리는 이러한 계층적인 구조를 표현하는데 사용하는 자료구조입니다.

 - 인공지능 문제에서도 트리가 사용됩니다. 의사결정트리 등

트리의 용어들을 알아보겠습니다.

노드 : 트리의 구성요소들

루트노드 : 부모가 없는 노드, 트리는 하나의 루트노드만 가집니다.

리프노드 : 자식이 없는 노드

레벨(깊이) : 루트에서 단말노드까지의 거리, 루트노드만 있는 트리는 레벨이 0입니다.

형제노드 : 같은 부모를 가지는 노드

차수 : 바로 아래 자식노드의 개수

서브트리 : 루트를 제외한 나머지 노드들의 집합

그림으로 표현하자면 위 그림과 같습니다.

트리의 종류에는 이진트리, 이진탐색트리를 비롯하여 파일구조에서 사용되는 B트리, B+트리 등이 있습니다.

 - 이진트리와 이진탐색트리는 다른 트리입니다.

이번에는 이진트리와 이진탐색트리에 대해서만 설명하도록 하겠습니다.

 - 나머지 트리들은 추후 포스팅하겠습니다.

이진트리 (Binary Tree)

트리 중에서 가장 많이 사용되는 트리가 바로 이진트리입니다.

모든 노드가 2개의 서브트리를 가지고 있는 트리를 이진트리라고 합니다.

이진트리는

 - 공집합이거나

 - 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한 집합으로 정의됩니다.

 - 이진트리와 서브트리들은 모두 이진트리여야 합니다.

위와 같은 형태를 이진트리라고 할 수 있습니다.

이진트리의 성질

- 모든 노드의 차수가 2 이하입니다. 반면, 일반 트리는 자식 노드의 개수에 제한이 없습니다.

- 일반 트리와는 달리 이진 트리는 노드를 하나도 갖지 않을 수 있습니다.

- 서브트리간에 순서가 존재한다는 점도 다른 점입니다. 따라서 왼쪽 서브트리와 오른쪽 서브트리를 구별합니다.

- n개의 노드를 가진 이진트리는 정확하게 n-1개의 간선(edge)을 가집니다.

- 높이가 h인 이진트리의 경우 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가집니다.

- n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소 「log2(n+1)이 됩니다.

이진트리는

- 포화이진트리 : 용어 그대로 트리의 각 레벨에 노드가 꽉 차있는 이진트리입니다.

- 완전이진트리 : 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져있고 마지막 레벨 k에서 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리입니다.

- 기타이진트리 : 그 외의 이진트리

의 세 종류로 나누어집니다.

이진트리의 순회

이진트리를 순회하는 표준적인 방법에는 전위, 중위, 후위의 3가지 방법이 있습니다.

- 전위순회 (Preorder traversal)  : VLR

- 중위순회 (Inorder traversal)    : LVR

- 후위순회 (Postorder traversal) : LRV

루트가 가장 먼저 순회되면 전위, 중간에 순회되면 중위, 마지막에 순회되면 후위이며 서브트리 탐색은 왼쪽, 오른쪽의 순서로 진행됩니다.

이진탐색트리 (Binary Search Tree)

이진 탐색 트리는 이진트리 기반의 탐색을 위한 자료구조입니다.

이진트리의 정의

- 모든 원소의 키는 유일하다

- 왼쪽 서브트리의 키들은 루트의 키보다 작다

- 오른쪽 서브트리의 키들은 루트의 키보다 크다

- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다

따라서, 찾고자 하는 키값이 이진트리의 루트 노드의 키값과 비교하여 루트노드보다 작으면 왼쪽서브트리, 크면 오른쪽 서브트리를 탐색하는 방식입니다.

루트보다 작은 값은 왼쪽, 루트보다 큰 값은 오른쪽 서브트리로 들어가며 서브트리의 서브트리들에도 이런 규칙은 적용됩니다.

이진탐색트리 코드

코드 출처 : https://github.com/1ambda/algorithm/tree/master/cpp/binary-search-tree/src

node.h
template <typename T>
class BinarySearchTree;

template <typename T>
class Node {

  // friend 선언으로 Node 클래스는 BinarySearchTree 클래스의 private 접근 가능
  friend class BinarySearchTree<T>;   
  
private:
  T data;          // 데이터와, 왼쪽, 오른쪽 서브노드로 구성
  Node* left;
  Node* right;

public:
  Node() {
    left = nullptr;
    right = nullptr;
  }

  Node(T t) {      // 기본적으로 노드의 왼쪽과 오른쪽 서브노드는 NULL로 선언
    data = t;
    left = nullptr;
    right = nullptr;
  }

  ~Node() {
  }
};

tree.h

#include <iostream>
#include <functional>
#include "node.h"

using namespace std;

template <typename T>         // 변수형 제한이 없도록 템플릿 클래스 선언
class BinarySearchTree {

 private:
  Node<T>* root;              // 루트노드 선언
  
 public:
  BinarySearchTree<T>();
  ~BinarySearchTree<T>();

  bool search(T value, function<int(T&, T&)>& comp);          // 노드 탐색
  bool remove(T value, function<int(T&, T&)>& comp);          // 노드 값 삭제 -> 아래 호출
  bool internal_remove(Node<T>*& current, T value, function<int(T&, T&)>& comp); // 노드 값 삭제
  bool insert(T value, function<int(T&, T&)>& f);             // 노드 값 삽입 -> 아래 호출
  bool internal_insert(Node<T>*& current, T value, function<int(T&, T&)>& f); // 노드 값 삽입
  Node<T>*& find_left_most_child(Node<T>*& current);          //  가장 왼쪽의 리프노드 찾기
  void replace_node(Node<T>*& replaced, Node<T>*& newone);    //  노드 값 변경
  void traverse_pre_order(function<void(T&)>& f);             //  전위순회
  void internal_traverse_pre_order(Node<T>* current, function<void(T&)>& f); // 내부 전위순회
  void traverse_in_order(function<void(T&)>& f);              //  중위순회
  void internal_traverse_in_order(Node<T>* current, function<void(T&)>& f);  // 내부 중위순회
  void traverse_post_order(function<void(T&)>& f);            //  후위순회
  void internal_traverse_post_order(Node<T>* current, function<void(T&)>& f); // 내부 후위순회
  bool is_empty(void);                                        //  비어있는지 확인
};

// 생성자로 초기 루트는 비어있는 상태 : NULL
template <typename T>
BinarySearchTree<T>::BinarySearchTree() {
  root = nullptr;
}

template <typename T>
BinarySearchTree<T>::~BinarySearchTree() {
  delete root;
}

// 이진탐색트리 탐색
template <typename T>
bool BinarySearchTree<T>::search(T value, function<int(T&, T&)>& comp)
{
  Node<T>* current = root;       // 루트노드를 현재 탐색 대상으로 설정


  while (current) {
    if (comp(current->data, value) == 0) {        // 현재 데이터가 찾고자하는 값이랑 같으면 리턴
      return true;                                
    } else if (comp(value, current->data) == 1) { // 메인의 comparator함수로 오른쪽 서브트리가 작으면 1
      current = current->right;                   // 그래서 결과가 1이면 오른쪽 서브트리로 들어가서 탐색
    } else {
      current = current->left;                    // 반대로 왼쪽 서브트리가 작으면 -1, 왼쪽 서브트리로 들어감
    }                                             // 계속 반복하면서 자리찾음
  }

  return false;                                   // 반복하다가 없으면 false 리턴
}

// 왼쪽 가장 리프노드 찾기
template <typename T>
Node<T>*& BinarySearchTree<T>::find_left_most_child(Node<T>*& current) {

  while(current->left) {
    current = current->left;                      // 왼쪽 서브트리 끝까지 들어감
  }
  
  return current;                                 // 리턴
}

// 노드 값 대체하기
template <typename T>
void BinarySearchTree<T>::replace_node(Node<T>*& replaced, Node<T>*& newone) {

  if (replaced == nullptr || newone == nullptr) {       // 둘다 NULL이면 대체할 게 없음 아무것도안함
    return;
  }

  if (replaced->left != nullptr && replaced->right != nullptr) { // 대체할 노드에 자식노드가 있으면
      newone->left = replaced->left;                             // 새로운 노드에 자식노드를 붙여줌
    if(replaced->right != newone)                                // 대체할 노드의 오른쪽 자식노드가 새로 들어올 노드와 같은 값이 아니면(?)
      newone->right = replaced->right;                           // 새로운 노드에 자식노드를 붙여줌
  }
  
  Node<T>* temp = replaced;                   // 우선 빈 공간에 대체될 값을 넣어주고
  replaced = newone;                          // 새로운 값을 대체될 장소에 넣고
  delete temp;                                // 대체될 값이었던 기존의 값 삭제
  
  return;
}

// 노드 값 삭제하기
template <typename T>
bool BinarySearchTree<T>::remove(T value, function<int(T&, T&)>& comp)
{
  return internal_remove(root, value, comp);  // 루트부터 내부 순회하며 삭제
}

// 노드 내부 탐색하며 값 삭제하기
template <typename T>
bool BinarySearchTree<T>::internal_remove(Node<T>*& current, T value,
                                          function<int(T&, T&)>& comp) {

  if (comp(current->data, value) == 0) {            // 메인의 comparator, 0이면 노드 찾은것.
    if (current->left == nullptr && current->right == nullptr) { // 리프노드라면      
      delete current;
      current = nullptr;       // 끝에 삭제하고 널포인터 넣어주고
    } else if (current->left != nullptr && current->right != nullptr) { // 자식노드가 둘다 있으면
      replace_node(current, find_left_most_child(current->right));      // 삭제할 값을 오른쪽 서브트리의 가장 왼쪽 값으로 대체, 반대로 왼쪽 서브트리의 가장 오른쪽 값으로 대체해도 됨
    } else if (current->left != nullptr && current->right == nullptr) { // 왼쪽 자식노드만 가지고 있으면
      replace_node(current, current->left);                             // 삭제할 값을 왼쪽 자식노드의 값으로 대체
    } else if (current->left == nullptr && current->right != nullptr) { // 오른쪽 자식노드만 가지고 있으면
      replace_node(current, current->right);                            // 삭제할 값을 오른쪽 자식노드의 값으로 대체
    }

    return true;
    
  } else if (comp(value, current->data) == 1) {      // 메인의 comparator, 1이면 삭제할 노드 값이 현재 노드 값보다 큰 것
    return internal_remove(current->right, value, comp);  // 재귀함수로 오른쪽 서브트리 탐색
  } else {                                           // 메인의 comparator, -1이면 삭제할 노드 값이 현재 노드 값보다 작은 것
    return internal_remove(current->left, value, comp);  // 재귀함수로 왼쪽 서브트리 탐색
  }

  return false;
}

// 노드 값 삽입
template <typename T>
bool BinarySearchTree<T>::insert(T value, function<int(T&, T&)>& comp) {

  return internal_insert(root, value, comp);  // 내부 탐색 하며 값 삽입하는 함수 호출, 루트부터 시작
}

// 노드 내부 탐색하며 값 삽입하기
template <typename T>
bool BinarySearchTree<T>::internal_insert(Node<T>*& current, T value,
                                          function<int(T&, T&)>& comp) 
{
  // recursive
  if (current == nullptr) {         // 현재 탐색 부분이 비어있으면
    current = new Node<T>(value);   // 새로운 값 삽입
    return true;
  } else if (comp(current->data, value) == 1) {     // 1이면 현재 노드 값이 삽입할 노드 값보다 큰 것
    return internal_insert(current->left, value, comp); // 그렇담 왼쪽 서브트리로 재귀함수
  } else if (comp(current->data, value) == -1) {    // -1이면 현재 노드 값이 삽입할 노드 값보다 작은 것
    return internal_insert(current->right, value, comp); // 그렇담 오른쪽 서브트리로 재귀
  } 

  // duplicated
  return false;
}

// 전위순회
template <typename T>
void BinarySearchTree<T>::traverse_pre_order(function<void(T&)>& printer)
{
  // depth-first traversal
  internal_traverse_pre_order(root, printer); // 루트부터 전위순회 시작
}

// 전위순회 재귀함수
template <typename T>
void BinarySearchTree<T>::internal_traverse_pre_order(Node<T>* current,
                                                      function<void(T&)>& f) {
  if (current == nullptr) {  // 현재 탐색할게 없으면 종료
    return;
  }

  f(current->data);  // 여기서 f는 메인에 정의되어있는데 현재 값을 출력해주는 것
  internal_traverse_pre_order(current->left, f); // 그리고 왼쪽 서브트리 값 출력
  internal_traverse_pre_order(current->right, f); // 오른쪽 서브트리 값 출력
}

// 중위순회
template <typename T>
void BinarySearchTree<T>::traverse_in_order(function<void(T&)>& printer)
{
  // depth-first traversal
  internal_traverse_in_order(root, printer); // 마찬가지로 루트부터 중위순회 시작
}

template <typename T>
void BinarySearchTree<T>::internal_traverse_in_order(Node<T>* current,
                                                      function<void(T&)>& f) {
  if (current == nullptr) {  // 탐색할게 없으면 종료
    return;
  }

  internal_traverse_in_order(current->left, f);  // 현재 값의 왼쪽 서브트리 값 먼저 출력
  f(current->data);                              // 현재 값 출력
  internal_traverse_in_order(current->right, f); // 현재 값의 오른쪽 서브트리 값 출력
}

// 후위순회
template <typename T>
void BinarySearchTree<T>::traverse_post_order(function<void(T&)>& printer)
{
  // depth-first traversal
  internal_traverse_post_order(root, printer);  // 루트부터 후위순회 시작
}

template <typename T>
void BinarySearchTree<T>::internal_traverse_post_order(Node<T>* current,
                                                      function<void(T&)>& f) {
  if (current == nullptr) {  // 탐색할게 없으면 종료
    return;
  }

  internal_traverse_post_order(current->left, f);  // 현재 값의 왼쪽 서브트리 값 먼저 출력
  internal_traverse_post_order(current->right, f); // 현재 값의 오른쪽 서브트리 값 출력
  f(current->data);                                // 현재 값 출력

}


template <typename T>
bool BinarySearchTree<T>::is_empty(void)
{
  if (root == nullptr)
    return false;          // 루트가 NULL이면 empty true일텐데 흠...
  
  return true;
}

main.cpp
#include <iostream>
#include "tree.h"

using namespace std;

int main(int argc, char *argv[])
{

  BinarySearchTree<int> bst;    // 이진탐색트리 탬플릿 클래스 선언, 자료형은 int로

  function<int(int&, int&)> comparator = [](int& lhs, int& rhs)->int{  // comparator, 트리 탐색자 정도?
                                          // (value, current)의 형태로 비교됨                               
    if(lhs > rhs) {              // 대상 값이 현재 탐색중인 값보다 크면 리턴 1 : 오른쪽 서브트리 탐색
      return 1;
    } else if (lhs < rhs) {      // 대상 값이 현재 탐색중인 값보다 작으면 리턴 -1 : 왼쪽 서브트리 탐색
      return -1;
    } else {
      return 0;                  // 대상 값과 현재 탐색중인 값이 같으면 0
    }
  };

  function<void(int& value)> printer = [](int& value)->void{   // 현재 값 출력
    std::cout << value << std::endl;
  };                        

  bst.insert(3, comparator);   // 3삽입, 3과 이미 들어가있는 값들 비교하면서
  bst.insert(2, comparator);   // 2삽입, 마찬가지
  bst.insert(5, comparator);   // 5삽입
  bst.insert(4, comparator);   // 4삽입
  bst.insert(6, comparator);   // 6삽입

  // std::cout << bst.search(1, comparator) << std::endl; // 1 탐색, 있나 없나만 True, False : 결과는 False
  // bst.insert(1, comparator);                           // 1 삽입
  // std::cout << bst.search(1, comparator) << std::endl; // 1 탐색, True

  bst.remove(5, comparator);   // 5삭제
  bst.traverse_pre_order(printer);  // 전위순회 결과출력
  
  return 0;
}

출처 : http://wonjayk.tistory.com/216