<TIL 20.06.18 > Binary Search Tree

Binary Search Tree (이진 탐색 트리)

• 이진 탐색 트리의 가장 핵심은 왼쪽 자식 노드가 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 커야 한다는 것이다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
• 모든 노드의 키 값은 유일하다.
• 한 노드가 최대 2개의 자식만 가질 수 있다.
• 크게 탐색, 삽입, 삭제 이 세 가지의 연산이 필요하다.  
• 시간 복잡도는 셋다 O(h)로 동일하다. h는 트리의 높이다.

 

Binary Search Tree순회 법

---

여러 가지 순회 방법이 있는 이유는 트리는 선형이 아닌 비선형이기 때문에 모드 노드들을 거쳐가기 위한 방법이 필요하게 된다. 그리하여 아래와 같은 순회 방법이 나오게 되었다

 

 

1. 전위 순회 

루트 노드부터 시작해서 아래로 내려오면서 왼쪽 하위 트리를 방문하고 왼쪽 하위 트리의 방문이 끝나면 오른쪽 하위 트리를 방문하는 방식이다. 

 

부모 → 좌 → 우

 

 

2. 중위 순회

왼쪽 하위 트리부터 시작해서 루트를 거쳐 오른쪽 하위 트리를 방문하는 방식이다.

 

좌 → 부모 → 우

 

 

3. 후위 순회

왼쪽 하위 트리부터 시작해서 오른쪽 형제 노드를 방문 후 루트 노드를 방문하는 방식이다

 

좌 → 우 → 부모

 

 

Binary Search Tree의 문제점

---

이 데이터 구조는 실무에서 잘 쓰이지 않는다고 한다. 그 이유는 편향 트리(트리 쏠림 문제) 때문이라고 한다. 예를 들면 아래의 이미지와 같이 한쪽 방향으로만 계속 붙어 배열인 듯 배열 아닌 이진 탐색 트리가 됫을때이다.

 

 

 

 

 

 

 

이미지 출처 : https://hooni.net/66487