[2. 트리, 힙, 그래프] 균형 트리, n항 트리

https://dev-haram.online/67

[2. 트리, 힙, 그래프] 이진 검색 트리(Binary Search Tree)

앞선 게시글에서 이진 검색 트리에 대해 정리했다.

 

이진 검색 트리의 시간 복잡도에 대해 서술할 때, 트리의 삽입 순서에 따라 시간 복잡도가 달라진다고 언급했었다.

이를 조금 더 자세히 살펴보면, 

위 그림에서 왼쪽 트리와 오른쪽 트리를 비교해보면, 오른쪽 트리가 더 균형이 잡혀있다고 할 수 있다.

 

균형 트리 (balanced tree)

위 그림에서 오른쪽 트리는 편향되지 않는 상태로, 균형이 잡혔다고 한다.

이러한 상황에서는 원소 검색의 시간복잡도가 감소하기 때문에 편향된 트리보다 훨씬 최적화 되어있다.

균형 트리를 만들기 위해서는 트리의 높이가 최적화되어야 한다. 그렇기 때문에 원소 삽입 또는 삭제 후에 트리 구성을 조정하여 최적 트리를 만들 수 있도록 구현해야 한다.

이렇게 편향성이 줄어든 BST를 높이 균형 BST (height-balanced BST) 라고 한다.

이러한 트리를 만드는 방법은 여러 가지가 존재하며, 이를 통해 AVL 트리, 레드-블랙 트리 등의 다양한 트리를 만들 수 있다.

 

N-항 트리

지금까지는 주로 이진 트리에 대해서 서술했지만, 각 노드의 자식이 두 개가 아닌 n 개의 자식을 갖는 트리를 n 항 트리라고 한다.

n개의 자식 노드는 vector 컨테이너를 이용하여 저장할 수 있다.

struct nTree{
    int data;
    std::vector<nTree*> children;
}

컴퓨터 파일 시스템 구조나 컴파일러 등에서 n 항 트리를 사용한다.