반응형

개요

 

이번에는 트리 중에서 BST라고 불리는 이원 탐색 트리에 대해서 알아보겠습니다.

 


BST 정의!

 

이진트리로서 공백이 가능하고, 만약 공백이 아니라면

1. 모든 원소는 서로 상이한 키를 갖는다.

2. 왼쪽 서브트리의 키들은 그 루트의 키보다 작다.

3. 오른쪽 서브트리의 키들은 그 루트의 키보다 크다.

4. 왼쪽과 오른쪽 서브트리도 이원 탐색 트리이다.

 

즉 이 조건으로 인해 전체 트리의 모든 노드에 대해 2,3 조건이 만족을 해야 BST라고 할 수 있다.

 


그림

 

 

BST가 아닌 경우

 

 

BST인 경우

 


BST 에서의 삽입

 

1. 삽입할 레코드의 key값과 같은 값을 가진 노드를 탐색

(탐색이 성공하면 삽입을 포기하고 실패로 종료)

2. 탐색이 실패하면 동일 키의 레코드가 없음을 말한다.

(탐색이 끝난 지점을 가진 마지막 노드의 자식으로 새로운 노드를 삽입한다.)

 

 

 

30 , 40 , 24 , 58 , 26 , 48 , 11 , 13 삽입 과정

BST의 삽입 과정

 

 


BST 에서의 삭제

 

1. 삭제할 레코드가 리프 노드에 있는 경우 

부모의 해당 자식 필드에 NULL을 삽입한다. 삭제될 노드를 삭제한다.

 

2. 삭제할 레코드가 하나의 자식을 가진 비 리프 노드에 있는 경우

삭제될 노드의 자식을 삭제될 노드의 부모에 매달고 나서 삭제한다.

 

3. 삭제할 레코드가 두개의 자식을 가진 비 리프 노드에 있는 경우

왼쪽 서브트리에서 가장 큰 원소나 오른쪽 서브 트리에서

가장 작은 원소로 삭제될 노드의 내용을 대체한다.

그런 다음 대체하는 데 사용된 노드를 삭제하는 작업을 수행한다.

 

 

아래 그림에서 5를 삭제한다면 루트노드 30의 자식 노드가 2,40이 올 수 있다.

BST 

 


BST의 원소 수 : n

 


최악의 경우

 

BST의 높이 = n

키 [1,2,3....,n]을 순서대로 삽입

 


평균

 

BST 의 높이 = O(log n)

 


균형 탐색 트리(balanced search tree)

 

최악의 경우에도 height = O(log n) 이 되는 트리

탐색, 삽입, 삭제의 시간 복잡도 : O(h)

AVL, 2-3, 2-3-4, 레드-블랙(red-black), B트리, B+트리 등

 

이렇게 이번에는 BST에 대해서 알아보았습니다.

다음에는 코드와 함께 알아보도록 하겠습니다.

 


 

반응형

+ Recent posts