[인프런|Binary Search Tree(1)] 영리한 프로그래밍을 위한 알고리즘 강좌

Binary Search Tree

 

 

• Dynamic Set

데이터들이 고정되어 있지 않고 추가, 삭제, 수정 등으로 계속해서 바뀌는 집합을 Dynamic set이라 한다.

Dynamic set, Dictionary(hash 타입 데이터 구조), Search Structure 등으로 불린다.

 

Search Structure

새로운 데이터의 추가와 삭제가 가능 

쉽게 생각했을 때 배열, 연결 리스트를 사용 가능

데이터를 정렬해서 저장 혹은 정렬하지 않고 저장

 

- 배열

정렬 안 된 경우 데이터의 검색, 추가, 삭제

  - Search

  최악의 경우 O(n)

  - Insert

  마지막에 추가 하기에 O(1) 

  만약 공간이 모자라서 malloc 해야 하는 경우 새 배열에 기존 값을 다 복사해야 하므로

  O(n)

  - Delete

  인덱스로 접근하여 마지막 데이터 삭제하는 경우

   O(1)

 

  정렬된 경우 데이터의 검색, 추가, 삭제

  - Search

  O(log n) 이진 탐색(binary search)을 사용한다.

  - Insert

   O(n) 정렬된 기준에 맞게 알맞은 본인의 자리를 찾아야 한다.

  - Delete

  O(n)  중간 값이 삭제되면 그보다 뒤에 저장되어있던 데이터들이 앞으로 당겨와야 한다.

 

- 연결 리스트

  정렬 안 된 경우 데이터의 검색, 추가, 삭제

  - Search

  O(n) 연결 리스트라 포인터를 통해 다음 노드들이 무엇인지 알 수 있으므로 계속 방문해야하고

  맨 마지막 칸까지 가야하는 경우 그렇다. 최악의 경우 가정

  - Insert

  O(1) 맨 앞에 추가하는 기준

  - Delete

  O(1) 데이터 위치를 찾았다는 가정하에 삭제만 하는 것은  O(1)만 소요됨

  배열의 경우 뒤에 있는 데이터를 앞으로 당겨야 하지만 

  연결 리스트이므로 그럴 필요가 없다.

 

  정렬된 경우 데이터의 검색, 추가, 삭제

  - Search

  O(n)  binary search 사용 불가 한 번에 중간 노드가 누군지 알 수 없으므로 쓸 수 없음

  순차 탐색해야 한다

  - Insert

  O(n) 정렬되어있으므로 내가 어디에 들어가야 하나 찾아야 한다,

  - Delete

  O(1) 위치는 찾고 삭제하는 가정했을 때

 

그래서 배열, 연결 리스트를 사용하는 경우 search, insert, delete 적어도 하나는 O(n)을 피할 수 없다.

 

Dynamic set을 세 가지 연산(search, insert, delete) 모두 동시에 효율적으로 하는 방법이 없을까 고민하여

현재까지 나온 방법은 이진 탐색 트리, 해쉬 테이블 등이 있다.

 

레드-블랙트리, AVL트리는 이진탐색트리 기반으로 변형한 데이터 구조이다.

 

대부분의 경우 연산의 시간 복잡도는 트리의 높이에 비례한다!

 

 

 

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

이진트리이면서 각 노드에 하나의 키를 저장

각 노드 v에 대해서
그 노드의 왼쪽 부트리(subtree)에 있는 키들은  key [v]보다,
오른쪽 부트리에 있는 값은 크거나 같다.

 

 

- Search

root부터 시작하여 이진트리 조건(왼쪽은 root보다 작거나 같다. / 오른쪽은 root보다 크거나 같다)을

이용하여 탐색을 수행한다.

 

# Recursive

TREE-SEARCH(x, k)   // x는 root node, k는 찾는 값 여기서는 key값

if x = NIL or k =key [x]

  then return x

if k < key [x]

  then return TREE-SEARCH(left [x], k)

  else return TREE-SEARCH(right [x], k)

 

 

# Iterative

ITERATIVE-TREE-SEARCH(x, k)

  while x!= NIL and k!= key [x]

    do if k < key [x]

      then x <- left [x]

      else x <- right [x]

  return x