이진 탐색 트리 BST

2019-11-23

BST, 검색트리, 이진탐색트리

1. 검색트리 Search Tree

1.1. 계층적인 구조를 표현

조직도
디렉토리와 서브디렉토리 구조
가계도

1.2. 트리의 특징

트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됩니다.
맨 위의 노드를 "루트(root)"라고 부릅니다.
노드를 연결하는 선을 "link", "edge","branch"
부모노드 자식노드로 구성되어있습니다.
루트노드를 제외한 트리의 모든 노드들은 유일한 부모노드를 갖습니다.
부모가 동일한 노드들을 형제 "sibling"관계라고 부릅니다.
자식이 없는 노드들을 "leaf"노드라고 부릅니다.
“leaf” 노드가 아닌것 내부 노드라고 부릅니다.
조상-자손 관계가 있다. 부모-자식관계를 확장한것 (ancestor-descendant) 관계
루트는 레벨관계 Level 0 ~ Level N 까지 갖습니다.

트리의 기본적인 성질
- 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가집니다.
- 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일(존재,1개)합니다.(단, 같은 노드를 두 번 이상 방문하지 않는다)
- 트리의 높이는 레벨의 개수입니다.

2. 이진 트리 Binary Tree

2.1. 특징

이진 트리에서 각 노드는 최대 2개의 자식을 가집니다.
각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정됩니다.(자식이 한 명인 경우에도)
서로 다른 이진트리는 값의 위치가 다르면 서로 다른 이진트리라고 불리온다. (자식노드가 한개인 경우에도 해당됩니다)

2.2. 이진트리의 응용 Expression Tree, Huffman Code

(x+y) * ((a + b) / c) 를 이진 트리형태로 나타낼 수 있다. Expression트리에서 응용한다.
허프만 코드 ‘A’ - ‘Z’, ‘a’ - ‘z’ 파일들의 알파벳을 어떤 데이터를 압축하는 것을 뜻한다. 파일의 길이가 최소가 되도록 하는 알고리즘(파일 압축)

2.3. Full Binary Trees And Complete Binary Trees

Full Binary Trees 모든 레벨에서 노드에 채워져 있는 경우
Completr Binary Trees 맨 마지막경우에는 노드가 없을 수 있다.(단, 끝에서부터 노드가 없을 수 있다.)
높이가 h인 full binary tree는 2^h-1개의 노드를 가진다.
노드가 N개인 full 혹은 complete 이진 트리의 높이는 O(logN)이다.(노드가 N개인 이진트리의 높이는 최악의 경우 N이 될 수 있다.)

2.4. 이진트리의 표현

Heap은 Complete Binary Tree이다.
연결 구조 표현
- 각 노드에 하나에의 데이터필드와 왼쪽자식(left), 오른쪽 자식(right),그리고 부모노드§의 주소를 저장
- 부모노드는 주소는 반드시 필요한 경우가 아니면 보통 생략함

2.5. 이진트리의 순회(Traversal)

순회: 이진 트리의 모든 노드를 방문하는 일
중순위(inorder) 순회
- 왼쪽자식기준으로 루트노드를 중간에 방문한다.
- 왼쪽 자식 노드->루트->오른쪽 자식 노드
  1
  2
  3
  pre-order-tree-walk(left[x])
  print key[x]
  pre-order-tree-walk(right[x])
선순위(preorder) 순회
- 왼쪽자식기준으로 루트노드를 처음에 방문한다.
- 루트 노드->왼쪽 자식 노드->오른쪽 자식 노드
  1
  2
  3
  print key[x]
  pre-order-tree-walk(left[x])
  pre-order-tree-walk(right[x])
후순위(postorder) 순회
- 왼쪽기준으로 루트노드를 마지막에 방문한다.
- 왼쪽 자식 노드->루트 노드->중간 자식 노드
  1
  2
  3
  pre-order-tree-walk(left[x])
  pre-order-tree-walk(right[x])
  print key[x]
레벨오더(level-order) 순회
- 레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로 방문합니다.
- 큐(queue)를 이용하여 구현
  
  트리에 [1,2,3,4,5,6,7]이 순서대로 있다고하면 레벨별로 하나씩 방문한다(단, 기준은 왼쪽)
  
  Level 0: 1
  
  Level 1: 2,3
  
  Level 2: 4,5,6,7
  
  해당 순서로 방문한다고 생각하면 됩니다.

2.6. Dynamic Set

여러개의 데이터의 집합을 뜻하는 말을 일컫습니다.
여러 개의 키(Key)를 저장합니다.
다음과 같은 연산들을 지원하는 자료구조입니다.
- INSERT - 새로운 키의 삽입
- SEARCH - 키 탐색
- DELETE - 키의 삭제
예: 심볼 테이블

2.7. 배열

정렬 O
- 검색: O(logN)
- 삽입: O(N)
- 삭제: O(N)
정렬 X
- 검색: O(N)
- 삽입: O(1), O(N)
- 삭제: O(1)

2.8. 연결리스트

정렬 O
- 검색: O(N), O(logN)
- 삽입: O(N)
- 삭제: O(1)
정렬 X
- 검색: O(N)
- 삽입: O(1)
- 삭제: O(1)

정렬이 이루어지면 이진검색 O(logN)의 시간복잡도 만큼수행된다. 예를 들면, 1,2,4,8 의 형식으로 트리의 노드의 개수가 증가된다고 하면 2^k = N으로 나타낼 수 있다. k는 시행횟수이며, N은 입력된 개수입니다. 이것을 K = log2N으로 나타낼 수 있습니다. 이때 시간복잡도에서는 상수를 무시하기 때문에 K=logN으로 나타낼 수 있습니다. 따라서, 이진탐색의 시간복잡도는 O(logN) 입니다.

2.9. 다양한 방법들

정렬된 혹은 정렬되지 않은 배열 혹은 연결 리스트를 사용할 경우 INSERT, SEARCH, DELETE 중 적어도 하나는 O(N)
이진탐색트리(Binary Search Tree), 레드-블랙트리, AVL-트리 등의 트리에 기반한 구조들
Direct Address Table, 해쉬 테이블 등

2.10. 검색트리

Dynamic set을 트리의 형태로 구현
일반적으로 SEARCH, INSERT, DELETE 연산이 트리의 높이(height)에 비례하는 시간복잡도를 가짐
이진검색트리(Binary Search Tree), 레드-블랙 트리(Red-black tree), B-트리 등

3. 이진탐색트리 Binary Search Tree

3.1. 이전검색트리(BST) 특징

이진트리이면서 각노드에 하나의 키를 저장
각 노드 v에 대해서 그 노드의 왼쪽 부트리(subtree)에 있는 키들은 key[v]보다 작거나 같고, 오른쪽 부트리에 있는 값은 크거나 같다.
중위 순회의 값을 갖는다
각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
중복된 노드가 없어야 한다.
왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리이다.

3.2. 1.SEARCH

RECURSIVE

TREE-SEARCH(x,k) x = 루트노드, k = 찾는값
	// x가 null이거나 k == key[x]를 찾은 경우(원하는 값을 찾은 경우)
	if x == NULL || k == key[x]
		then return x;
		
	// 키보다 작을 경우
	if k < key[x]
		then return TREE-SEARCH(left[x],k)
	// 키보다 클경우
	else 
		then return TREE-SEARCH(right[x],k)

NONE RECURSIVE

ITERATIVE-TREE-SEARCH(x,k)
	While x != NULL and K != key[x]
		do if k < key[x]
				then x <- left[x]
				else x <- rgiht[x]
	return x;

시간복잡도: O(h), h = 트리의 높이

Algorithm자료구조론