이진 트리 binary tree

►  코딩테스트 합격자되기 자바스크립트편 09장 트리를 요약 정리한 포스팅입니다.

🌲 이진 트리란?

모든 노드의 최대 차수가 2를 넘지 않는 트리를 말한다.(= 간선이 최대 2개인 트리)

► 배열로 표현하기

배열은 선형 자료 구조, 트리는 계층 자료 구조이므로 배열로 트리를 표현하려면 아래 규칙을 따라야한다.

1. 루트 노드는 배열 인덱스 1번에 저장한다.
2. 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 * 2이다.
3. 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 * 2 + 1이다.

           1
          /   \
        2     3
       / \     \
     4   5     7
    /         /
   8         14

 

위의 트리로 보면 인덱스가 부모 * 2로 증가한다. 점선 화살표를 따라가며 인덱스를 확인해보면 1->3->7이다. 인덱스가 부모 인덱스 * 2 + 1로 증가한다. 실제 배열에 이진 트리를 저장하면 다음과 같다.

 

 

• 루트 노드를 인덱스 0으로 하면 왼쪽 자식 노드는 부모 노드의 배열 인덱스 * 2 + 1이 되고, 오른쪽 자식 노드는 부모 노드의 배열 인덱스 * 2 +2가 된다.
• 입력값에 따라 루트 노드를 0 혹은 1로 정해야 하는 경우가 있으므로 알아두자.
• 위의 표처럼 배열로 트리를 표현하면 자식이 없거나 쓰지 않는 인덱스들은 모두 빈 값이므로 메모리 낭비가 되는 단점이 있다.
• 하지만 이진 트리를 배열로 표현하는 방식은 굉장히 난이도가 쉬우므로 메모리만 넉넉하다면 구현 시간을 단축시키는 용도로 좋다.

이진 트리로 순회하기

현재 노드를 부모 노드로 생각했을 때 기준.

• 전위 순회 preorder : 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서
• 중위 순회 inorder : 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드
• 후위 순회 postorder : 왼쪽 자식 노드 -> 오른 쪽 자식 -> 부모 노드 순서

►포인터로 표현하기

포인터로 프리를 표현하려면 노드부터 정의해야 한다. 노드는 노드의 값, 왼쪽 자식 노드와 오른쪽 자식 노드를 가진다.
포인터로 표현한 트리는 배열과 달리 인덱스 연산을 하지 않으므로 메모리 공간을 낭비하지 않지만, 실제 노드를 따라가도록 구현해야 하므로 구현 난이도는 배열로 표현한 트리에 비해 조금 높다.

이진 트리 탐색하기

이진 트리에서 가장 중요한 것은 바로 탐색을 효율적으로 할 수 있도록 트리를 구축하는 것!

이진 탐색 트리 구축하기

이진 탐색 트리는 데이터 크기를 따져 현재 노드보다 값이 작으면 왼쪽 자식 위치에, 크기가 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 갖고 있다. 대상 데이터가 3 -> 4 -> 2 -> 8 -> 9 -> 7 -> 1 순서로 들어온다 해보자.

1. 최초의 데이터는 루트 노드가 되므로 3을 이진 탐색 트리에 루트 노드로 추가한다.
2. 다음으로 삽입하려는 데이터는 4이다. 3보다 크므로 오른쪽 자식 위치에 배치한다.
3. 다음으로 삽입하려는 데이터는 2이다. 2는 3보다 작으므로 왼쪽 자식 위치에 삽입한다.
4. 다음으로 삽입하려는 데이터는 8이다. 이미 자식이 있는 경우 값을 비교 후 큰 값을 기준으로 정렬된다. 8은 4보다 크므로 오른쪽 자식 위치를 본다. 구축할 때는 넣으려는 대상 데이터의 값이 크거나 같으면 오른쪽 자식으로, 작으면 왼쪽 자식으로 배치한다.
5. 9는 3보다 크므로 오른쪽으로 본다. 4보다 크므로 다시 ㅇ른쪽으로 본다. 8보다 크므로 오른쪽에 배치한다.
6. 7은 3보다크로 4보다 크고 8보다 작으므로 비어있는 8의 왼쪽 자식 자리에 7을 배치한다.
7. 마지막으로 1은 3보다 작고, 2보다 작으니 2의 왼쪽 자식에 배치한다.

    3
   / \
  2   4
 /       \
1       8
       /  \
      7    9

이진 탐색 트리 탐색하기

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

배열 탐색과 비교하기

• 이진 탐색 트리는 크기에 따라 찾는 방향이 정해지는 방면 배열은 인덱스를 순회하므로 이진 탐색 트리의 탐색이 훨씬 빠르다.

이진 탐색 트리의 시간 복잡도

이진 탐색 트리에 저장된 노드가 N개라고 했을 때 O(logN), 하지만 균형이 맞지 않은 경우 시간 복잡도가 배열과 비슷하다. (최악의 경우 O(N)으로 같다)

• 치우쳐진 형태의 트리(degenerate binary tree)일 경우는 시간 복잡도가 O(N)이됨 (교재 307p이미지 참고)
• 균형 이진 탐색 트리 : 균형 이진 탐색 트리를 활용하면 이진 트리의 탐색 연산 횟수가 트리 높이에 비례하고 트리의 높이는 logN으므로 탐색 시간 복잡도로 O(logN)으로 유지할 수 있다. 단 구현 난이도는 최상