[자료구조] 이진 트리

이진 트리

• 노드 하나가 최대 2개의 자식 노드를 가지는 구조
• 배열 또는 포인터로 구현할 수 있음

배열로 표현하기

배열은 선형 자료구조이나 트리는 계층 자료구조, 따라서 배열로 트리를 표현하려면 3가지 규칙이 필요함.

• 루트 노드는 배열 인덱스 1번에 저장
• 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x 2
• 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x 2 + 1
  

입력값에 따라 루트 노드는 0 또는 1이 될 수 있음.

• 노드들의 부모-자식 관계를 곱연산하여 배열의 인덱스로 사용하기 때문에 실제 노드 갯수보다 많은 공간 사용
• 즉, 배열로 트리를 표현하면 쓰지 않는 인덱스는 빈 값이므로 메모리가 낭비
• 생성 시간 복잡도는 O(N)

포인터로 표현하기

• 노드는 노드의 값, 왼쪽 자식 노드와 오른쪽 자식 노드를 가진다.
• 배열과 달리 인덱스 연산을 하지 않으므로 메모리 공간을 낭비하지 않음

이진 트리 탐색하기

• 이진 트리에서 가장 중요한 것은 탐색을 효율적으로 할 수 있도록 트리를 구축하는 것
• 이진 탐색 트리는 데이터 크기를 따져 현재 노드보다 값이 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 갖고 있음
• 이진 탐색 트리의 시간 복잡도는 트리 균형에 의존함

1. 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고, 크면 오른쪽 노드를 탐색
2. 본인이 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드를 탐색
3. 값을 찾으면 종료, 노드가 없을 때까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없는 것

트리의 순회

// 전위 순회 (부모 -> 왼쪽 -> 오른쪽)
function preOrder(nodes, idx) {
  if ( idx < nodes.length ) {
    let ret = `${nodes[idx]} `; // 루트 노드
    ret += preOrder(nodes, idx * 2 + 1); // 왼쪽 노드
    ret += preOrder(nodes, idx * 2 + 2); // 우측 노드
    return ret;
  }

  // idx >= nodes.length일 때는 빈 문자열 반환
  return "";
}

// 중위 순회 (왼쪽 -> 부모 -> 오른쪽)
function inOrder(nodes, idx) {
  if ( idx < nodes.length ) {
    let ret = inOrder(nodes, idx * 2 + 1);
    ret += `${nodes[idx]} `;
    ret += inOrder(nodes, idx * 2 + 2);
    return ret;
  }

  return "";
}

// 후위 순회 (왼쪽 -> 오른쪽 -> 부모)
function postOrder(nodes, idx) {
  if ( idx < nodes.length ) {
    let ret = postOrder(nodes, idx * 2 + 1);
    ret += postOrder(nodes, idx * 2 + 2);
    ret += `${nodes[idx]} `;
    return ret;
  }

  return "";
}

function solution(nodes) {
    return [
      preOrder(nodes, 0).slice(0, -1),
      inOrder(nodes, 0).slice(0, -1),
      postOrder(nodes, 0).slice(0, -1)
    ]
}

이진 탐색 트리 구현

// 노드 클래스 정의
class Node {
  constructor(key) {
    this.left = null;
    this.right = null;
    this.val = key;
  }
}

// 이진 탐색 트리 클래스
class BST {
  constructor() {
    this.root = null;
  }

  // 루트 노드부터 시작해서 이진 탐색 트리 규칙에 맞는 위치에 새 노드 삽입
  insert(key) {
    if ( !this.root ) {
      this.root = new Node(key);
    } else {
      let curr = this.root;

      while (true) {
        // 삽입하려는 값이 현재 노드의 값보다 작은 경우 왼쪽 자식 노드로 이동
        if (key < curr.val) {
          if (curr.left) {
            curr = curr.left;
          } else {
            curr.left = new Node(key);
            break;
          } 
        } else {
          if (curr.right) {
            // 삽입하려는 값이 현재 노드의 값보다 큰 경우 오른쪽 자식 노드로 이동
            curr = curr.right;
          } else {
            curr.right = new Node(key);
            break;
          }
        }
      }

    }
  }

  // 이진 탐색 규칙에 따라 특정 값이 있는지 확인(루트 노드부터 시작)
  search(key) {
    let curr = this.root;

    // 현재 노드가 존재하고, 찾으려는 값과 현재 노드의 값이 같지 않은 경우 반복
    while (curr && curr.val !== key) {
      // 찾으려는 값이 현재 노드의 값보다 작은 경우 왼쪽 노드로 이동
      if (key < curr.val) {
        curr = curr.left;
      } else {
        curr = curr.right;
      }
    }

    return curr;
  }
}

// list에 있는 데이터를 활용해서 이진 탐색 트리 생성, searchList 원소 탐색
function solution2(list, searchList) {
  const bst = new BST();

  for (const key of list) {
    bst.insert(key);
  }

  const result = [];

  for (const searchVal of searchList) {
    if (bst.search(searchVal)) {
      result.push(true);
    } else {
      result.push(false);
    }
  }

  return result;
}

solution2([5, 3, 8, 4, 2, 1, 7, 10], [1, 2, 5, 6]);