제11-1강. 이진검색트리(Binary Search Tree)

• 이진검색트리(Binary Search Tree)

 

- 여러 개의 키(key)를 저장

- 다음과 같은 연산들을 지원하는 자료구조

   INSERT - 새로운 키의 삽입

   SEARTCH - 키 탐색

   DELETE - 키의 삭제

ex) 심볼테이블

 

 

		search	insert	delete
배열	정렬된 경우	O(logn)	O(n)	O(n)
	정렬되지 않은 경우	O(n)	O(1)	O(1)
연결리스트	정렬된 경우	O(n)	O(n)	O(1)
	정렬되지 않은 경우	O(n)	O(1)	O(1)

 

 

• 다양한 방법들

- 정렬된, 혹은 정렬되지 않은 배열 혹은 연결리스트를 사용할 경우

  INSERT, SEARCH, DELETE 중 적어도 하나는 O(n)

- 이진탐색트리(Binary Search Tree), 레드-블랙트리(red-black tree), AVL-트리 등의 트리에 기반한 구조들

- Direct Address Table, 해쉬 테이블 등..

 

 

• 검색트리

- Dynamic set을 트리의 형태로 구현

- 일반적으로 SEARCH, INSERT, DELETE 연산이 트리의 높이(height)에 비례하는 시간복잡도를 가짐

- 이진검색트리(Binary Search Tree), 레드-블랙트리(red-black tree), B-트리 등..

 

 

• 이진검색트리(BST : Binary Search Tree)

각 노드마다 최대 두 명의 자식을 가질 수 있고, 누가 왼쪽 자식이고 오른쪽 자식인지 명시되어 있는 트리

이진검색트리(BST: Binary Search Tree)

 

 

이진검색트리(BST: Binary Search Tree)

 

 

• 순환을 이용해 표현한 이진탐색 의사코드

// SEARCH. x : 루트노드, k : 찾는 값
TREE-SEARCH (x, k){
	if x == null or k == key[x]	// key[x] : 노드 x에 저장된 값
    	then return x
    if k < key[x]
    	then return TREE-SEARCH(left[x], k)
        else return TREE-SEARCH(right[x], k)
}

시간복잡도 : O(h), 여기에서 h는 트리의 높이

 

 

 

• 반복문을 이용해 표현한 이진탐색 의사코드

INTERATIVE-TREE-SEARCH(x, k){
	while x != null and k != key[x]
    	do if k < key[x]
        	then x // left[x]
            else x // right[x]
    	return x
}

시간복잡도 : O(h), 여기에서 h는 트리의 높이