이진 트리 & 인진 탐색 트리 (BST: Binary Search Tree)

여러 가지 트리의 모습

• 트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 한다.
• 수많은 선배 개발자들은 효율적인 탐색을 위해 고민하고 발전시켜 새로운 트리의 모습을 만드는 노력을 했다.
• 그래서 트리 구조는 가지고 있는 특징에 따라 여러 가지 이름으로 불린다.
• 많은 트리의 모습 중, 가장 간단하고 많이 사용하는 트리에 대해 알아보자.

👉 많이 사용하는 트리

• 이진 트리(binary tree)
• 이진 탐색 트리(binary search tree)

정이진트리, 포화이진트리, 완전이진트리

🌲 정 이진 트리 (Full binary tree)

• 정 이진 트리는 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.

🌲 완전 이진 트리 (Complete binary tree)

• 완전 이진 트리는 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.

🌲 포화 이진 트리 (Perfect binary tree)

• 포화 이진 트리는 정 이진 트리이면서 완전 이진 트리인 경우이다.
• 포화 이진 트리는 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.

 

⚡️ 이진 탐색 트리(Binary Search tree)

• 이진 탐색 트리(Binary Search Tree)는모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.
• 이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있습니다.
• 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야할 문제이다.
• 균형이 잡히지 않은 트리 탐색 문제를 해결하기 위해 삽입과 삭제 마다 ‘트리의 구조를 재조정’하는 과정을 거치는 알고리즘을 추가할 수 있다.