트리 구조

이진 검색 트리(BST)

널리 사용되는 형태의 이진트리

왼쪽 노드 <= 부모 노드 <= 오른쪽 노드의 관계를 가진다.

부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있다.

원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어든다.

BST가 마지막 레벨을 제외한 모든 노드에 두 개의 자식 노드가 있을 경우, 이 트리의 높이는 log 2N이 된다.

N은 원소의 개수, BST의 검색 및 삽입 동작은 O(log N)의 시간 복잡도를 갖는다.

이러한 형태의 이진트리를 완전 이진 트리

 

BST에서 원소 검색

루트 노드와 비교, 크다면 오른쪽, 작다면 왼쪽

BST에서 원소를 검색할 때는 트리의 모든 원소를 방문하지 않아도 된다.

현재 노드가 찾고자 하는 노드가 아닐 때마다 검색 범위가 반으로 줄어든다.

선형 자료 구조에 대한 이진 검색에서도 유사하게 나타난다.

 

BST에서 새 원소 삽입

새로운 원소를 추가하려면 먼저 원소가 삽입될 위치의 부모 노드를 찾아야 한다.

앞서 설명한 원소 검색과 비슷한 접근 방식을 사용하면 된다.

즉, 루트 노드부터 시작하여 각 노드를 추가할 원소와 비교하면서 원소가 삽입될 위치로 이동

새 원소를 추가하기 위해 제일 제일 비슷한 노드까지 이동, 크다면 오른쪽 자식에 추가, 작다면 왼쪽 자식에 추가

 

BST에서 원소 삭제

단순히 노드를 삭제하는 것으로 끝나는 것이 아니라, 노드 삭제 후 전체 트리가 BST 속성을 만족하도록 다른 적절한 노드로 삭제된 노드를 대체해야 하기 때문에 삽입보다 좀 더 복잡

삭제할 노드를 찾는 것

- 자식 노드가 없는 경우 : 단순히 해당 노드를 삭제

- 자식 노드가 하나만 있는 경우 : 노드 삭제 후, 부모 노드의 포인터가 해당 자식 노드를 가리키도록 조정

- 자식 노드가 두 개 있는 경우 : 노드 삭제 후, 현재 노드를 후속 노드로 대체

후속 노드란 현재 노드 다음으로 큰 숫자를 가진 노드

즉, 현재 원소보다 큰 원소들 중에서 가장 작은 원소를 의미 (젤 가까운 노드)

현재 노드의 오른쪽 서브 트리로 이동한 후, 가장 작은 값의 노드를 찾으면 된다.

가장 작은 노드를 찾으려면 서브 트리에서 가장 왼쪽에 위치한 노드로 이동하면 된다.

변경하려면 변경하려는 노드를 지우고 후속 노드의 값으로 덮어쓴다.

원래 후속 노드를 삭제, 그 후 설명한 삭제 방법을 그대로 적용

- 후속 노드는 오른쪽 자식 노드 하나만 가질 수 있다.

  만약 왼쪽 자식이 있었다면 해당 노드가 아닌 해당 노드의 자식 노드를 후속 노드로 선택했을 것

 

트리 연산의 시간 복잡도

검색의 경우 이론적으로 매번 검색 범위가 절반으로 줄어든다

N개의 노드를 가지고 있는 BST에서 검색에 필요한 시간은 T(N) = T(N/2) + 1

이 수식을 시간 복잡도를 표현하면 T(N) = O(logN)

그러나 삽입 함수를 잘 분석해보면 트리의 모양이 원소 삽입 순서에 따라 결정된다.

검색 범위가 앞서 사용한 수식처럼 T(N/2) 형태로 줄어드는 것도 항상 성립 X

그러므로 시간 복잡도가 O(logN)이라는 것도 항상 정확하다고 볼 수 없다.

 

균형 트리

트리가 왼쪽으로 편향되어 있을 경우 트리에서 find() 함수를 실행하면 비교 횟수가 원소 개수와 같아진다.

find() 함수의 시간 복잡도는 단순히 원소 개수에만 영향을 받는 것이 아니라 트리의 형태에 대해서도 영향을 받는다.

검색 단계를 면밀히 살펴보면 항상 트리의 아래쪽으로 한 단계씩 나아가는 것을 알 수 있다.

결국에는 더 이상 자식 노드가 없는 리프 노드에서 끝나게 된다.

여기서 찾고자 하는 원소를 발견하면 해당 노드를 반환하고, 없으면 NULL을 반환

검색에 필요한 단계의 수는 BST의 최대 레벨 수보다는 작다.

BST의 레벨 수를 BST의 높이라고 부르기 때문에 원소 검색의 실제 시간 복잡도는 O(높이)로 표현할 수 있다.

원소 검색의 시간 복잡도를 최적화하려면 트리의 높이가 최적화되어야 한다.

이런 작업을 트리의 균형 잡기

트리의 균형을 잡기 위해서는 원소 삽입 또는 삭제 후에 트리 구성을 조정

이렇게 조정되어 편향성이 줄어든 이진 검색 트리를 높이-균형 BST라고 한다.

트리의 균형을 잡는 방법은 여러 가지가 있으며, 이를 통해 AVL 트리, 레드-블랙 트리 같은 트리를 만들 수 있다.

AVL 트리의 기본 아이디어는 BST 속성을 유지하면서 트리 높이의 균형을 잡기 위해 약간의 회전을 수행

 

N-항 트리

각 노드가 N개의 자식을 가질 수 있다.

N은 임의의 양수이므로 N개의 자식 노드는 벡터를 이용하여 저장할 수 있다.

각각의 노드는 임의 개수의 자식을 거느릴 수 있다.

전체 트리도 임의의 형태를 가지게 된다.

평범한 N-항 트리도 그다지 유용하지 않다.

N-항 트리를 사용하는 대표적인 예

- 컴퓨터 파일 시스템 구조 : 리눅스에서는 루트부터, 윈도에서는 드라이브 이름부터 시작해서 다수의 파일과 폴더를 가질 수 있다.

- 컴파일러 : 대부분의 컴파일러는 표준 문법에 근거하여 소스 코드로부터 추상 구문 트리를 구성. AST를 다시 분석하여 하위 레벨 코드를 생성