[자료구조] Binary Tree, BST

Binary Tree(이진 트리)

부모 노드의 자식 노드 수가 2개 이하로 구성되어 있는 Tree를 의미한다.

이진 트리는 다음과 같이 분류 할 수 있다.

• 정이진 트리(full binary tree): 자식 노드가 0 또는 2개인 이진 트리를 의미합니다.
• 완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리를 의미합니다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있습니다.
• 변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리를 의미합니다.
• 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리를 의미합니다.
• 균형 이진 트리(balanced binary tree): 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 차이가 1 이하인 트리입니다. map, set을 구성하는 레드블랙트리는 균형 이진 트리 중 하나입니다.

Binary Search Tree

이진 탐색 트리란 정렬된 이진 Tree로써 다음과 같은 속성을 가지고 있다.

• 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가 있는 노드만 포함된다.
• 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드만 포함된다.
• 왼쪽 및 오른쪽 하위 트리도 각각 이진 탐색 트리이어야 한다.
• 중복된 키를 허용하지 않는다.
• 이진 탐색 트리는 "검색"을 하기에 용이하다.

즉 왼쪽 자식 < 부모 < 오른쪽 자식이어야 한다.

 

BST의 특징

• BST는 Inorder Traversal(중위 순회)을 수행하여 모든 키를 정렬된 순서로 가져올 수 있다.
• BST의 검색에 대한 시간복잡도는 균형 상태이면 O(logN)의 시간이 걸리지만, 불균형한 상태(skewed)의 경우 O(n)이 걸린다.

불균형한 상태의 BST

이는 삽입 순서에 따라 달라지며, 불균형한 자료 구조인 경우 시간 복잡도가 O(N)이 된다.

삽입 순서가 어떻게 되든 트리의 노드들을 회전시키는 등의 방법을 통해 "균형잡히게 만든" 이진 탐색 트리가 있다.

발전된 트리로는 AVL트리, Red-Black 트리가 존재한다.

(예시로 map이라는 자료구조는 레드블랙트리 기반으로 구현되어 있다)

참조

https://yoongrammer.tistory.com/71

https://think0wise.tistory.com/91