이진 탐색 트리(Binary Search Tree)

🌟 이진 트리

한 노드의 왼쪽 서브트리에 있는 모든 키 값은 그 노드의 키 값보다 작다.

한 노드의 오른쪽 서브트리에 있는 모든 키 값은 그 노드의 키 값보다 크다.

 

🟩 루트 노드에서부터 시작해서 값의 크기 관계에 따라 트리의 경로를 따라 내려가면서 탐색 진행

 

🟩 삽입 연산

삽입할 원소를 탐색한 후, 탐색이 실패하면 해당 위치에 자식 노드로서 새 노드를 추가

 

 

🟩 삭제 연산

삭제되는  노드의 자식 노드의 개수에 따라 구분해서 처리

1. 자식 노드가 없는 경우 👉 남는 노드가 없어 위치 조절 불필요

 

2. 자식 노드가 1개인 경우 👉 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따로 올림

 

3. 자식 노드가 2개인 경우

👉 삭제할 노드 왼쪽 서브 트리의 가장 큰 자손을 해당 노드의 자리에 올린다

👉 삭제할 노드 오른쪽 서브 트리의 가장 작은  자손을 해당 노드의 자리에 올린다

 

 

🌟 후속자 노드(계승자 노드)

어떤 노드의 바로 다음 키 값을 갖는 노드

 

🟩 시간복잡도

키값을 비교하는 횟수에 비례 👉 이진 트리의 높이가 h이면 O(h)

 

🟩 삽입/삭제

기존 노드의 이동이 거의 발생하지 않음

삽입 : 노드의 이동이 없음

삭제 : 상수 번 이동 (0, 1, 1 또는 2)

 

🟩 원소의 삽입/삭제에 따라 경사 트리 형태가 될 수 있음

최악의 수행시간 O(n)을 가짐

경사 트리가 만들어지지 않도록 트리의 균형을 유지해서 O(logn)을 보장

👉 균형 탐색 트리 (탐색 트리의 좌우 서브트리가 같은 높이를 유지하는 자료구조)

👉 2-3-4트리, 레드-블랙 트리, B-트리