Binary Search Tree 조회 과정

BST 조회 과정

다음의 BST에서 41데이터를 찾는 과정을 살펴보자

성능

 

트리의 높이가 n 이라면 노드의 개수는 (2^n)-1

 

트리의 밸런스가 잘 맞을 경우 → O(logN)

트리의 편향이 심할 경우 → O(N)

 

BST 성능 = 높이

 

조회 과정

41를 찾는다고 가정해 보자

노드와 비교해 41이 더 크면, 오른쪽 서브트리로 이동시키고

노드와 비교해 41이 더 작으면, 왼쪽 서브트리로 이동시킨다(재귀적)

 

 

 

 

데이터를 조회하는 과정에서 4번의 연산이 소요됐다.

 

한번에 한칸씩 내려가면서 결국 끝까지 가면 어떤 데이터든 찾을 수 있게 된다.

 

따라서, Binary Search Tree(BST)에서는 트리의 높이가 최대한 작아야 한다. 왜냐하면 트리의 높이가 곧, 조회성능과 비례하기 때문이다.