이진 검색 트리(Binary Search Tree)

검색트리의 필요성을 알아보기위해

배열과 정렬의  [시간 복잡도] 

		SEARCH	INSERT	DELETE
배열	정렬	O(logN)	O(N)	O(N)
	정렬X	O(N)	O(1)	O(1)

 

		SEARCH	INSERT	DELETE
연결리스트	정렬	O(N)	O(N)	O(N)
	정렬X	O(N)	O(1)	O(1)

 

배열 정렬했을경우 INSERT와 , DELETE자기자리를 찾아야하기때문에 아무렇게나 넣기 불가능

연결리스트의 경우 정렬을 해뒀더라도 binary search 불가능하다. 순차적으로 따라가 볼 수 밖에 없음

정렬된 혹은 정렬되지 않은 배열 혹은 연결리스트를 사용할 경우 INSERT, SEARCH, DELETE 중 적어도 하나는 O(n) 

 

어떻게 하면 INSERT, SEARCH, DELETE 를 효율적으로 하는가?

대표적인 방법

 

1) 탐색 트리(binary search tree)

2) 해쉬

 

검색 트리

일반적으로 SEARCH, INSERT, DELETE 연산이 트리의 높이에 비례하는 시간 복잡도를 가진다.

 

이진 검색 트리(Binary Search Tree)

-이진탐색(binary search)와 연결리스트(Linked list)를 결합한 자료구조의 일종

(이진탐색은 탐색은 빠르지만 삭제,입력 불가능 연결리스트는 입력 삭제는 효율적이지만 탐색하는데 복잡) 

- 이진트리(부모 노드는 최대 두명 자식 가질 수 있음, 왼쪽 노드와 오른쪽 노드는 구분됨)
- 각 노드에 하나의 키(데이터)를 저장

- 각 노드 v에 대해서 그 노드의 왼쪽 subTree에 있는 키들은 key[v]보다 작거나 같고,

  오른쪽 부트리에 있는 값은 크거나 같다.

( 부모 노드는 왼쪽 서브 트리보다 크고, 오른쪽 서브 트리보다는 작다.)

-SEARCH

Tree-Search(x.k) // k는 내가 찾는 값 , x : 트리의 노드
if x = NIL or k = key[x]  //x 라는 노드 가 존재하지 않는다면 , 노드 x에 저장된 값=k 라면
  then return x
if k < key[x]    
  then return Tree-Search(left[x],k)  //왼쪽으로
  else then Tree-Search(right[x],k)  //오른쪽으로 따라 내려감
  
  시간 복잡도 O(h) , h는 트리의 높이

 

 

참고 

www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/dashboard