이진 트리와 이진 탐색 트리

🌲 이진 트리(Binary tree)

자식 노드가 최대 두 개인 노드들로 구성된 트리

• 이 두개의 자식 노드는 왼쪽 자식 노드, 오른쪽 자식 노드로 나눌 수 있다.
• 자료의 삽입, 삭제 방법에 따라 나뉜다.
  • 정 이진 트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
  • 포화 이진 트리(Perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리
  • 완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.
    

---

🌲 이진 탐색 트리(Binary Search Tree)

이진 탐색(binary search) ✚ 연결 리스트(linked list)를 결합한 이진트리

• 이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료 입력과 삭제를 가능하게끔 고안됨.

  특징

  • 각 노드에 중복되지 않는 키(Key)가 있다.
  • 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
  • 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
  • 좌우 서브트리도 모두 이진 탐색 트리여야 한다.
    
    

즉, 이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다.

⭐️ 균형 잡힌 트리가 아닐 때

• 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다.
• 탐색하는 데 시간이 더 걸리는 경우가 있으며 이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정 하는 과정을 거치는 알고리즘을 추가할 수 있다.

⭐️ 이진 탐색 트리 특징

• 이진 탐색 트리 연산 : 트리의 높이가 h라면, O(h)의 복잡도를 가지게 된다.
• 장점 : 기존 이진 트리보다 탐색이 빠르다.
• 이진 탐색 트리의 탐색 과정
  1. 루트 노드의 키와 찾고자 하는 값을 비교, 만약 찾고자 하는 값이라면 탐색을 종료한다.
  2. 찾고자 하는 값이 루트 노드의 키보다 작다면, 왼쪽 서브 트리로 탐색을 진행
  3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행
• 이 과정을 찾고자 하는 값을 찾을 때까지 반복해 진행한다.
• 트리 안에 찾고자 하는 값이 없더라도 최대 h번의 연산 및 탐색이 진행된다
• 최대 트리의 높이(h)만큼 탐색을 진행

---

JavaScript에서 이진 검색 트리 구현
여러 언어로 이진 검색 트리 구현