Algorithm_14(Tree)

이진 탐색 트리

• 탐색 작업을 효율적으로 하기 위한 자료구조
• 모든 원소는 서로 다른 유일한 키를 갖는다
• key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)
• 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리다.
• 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

탐색 연산

• 루트에서 시작한다.
• 탐색할 키 값 x를 루트 노드의 키 값과 비교한다.
• 서브트리에 대해서 순환적으로 탐색 연산을 반복한다

삽입 연산

• 먼저 탐색 연산을 수행
  • 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인한다.
  • 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 된다.
• 탐색 실패한 위치에 원소를 삽입한다

이진 탐색 트리 성능

• 탐색, 삽입, 삭제 시간은 트리의 높이 만큼 시간이 걸린다.
  • O(h),h : BST의 깊이(height)
• 평균의 경우
  • 이진트리가 균형적으로 생성되어 있는 경우
  • O(log n)
• 최악의 경우
  • 한쪽으로 치우친 경사 이진트리의 경우
  • O(n)
  • 순차탐색과 시간복잡도가 같다

이진 탐색 트리 - 성능

검색알고리즘	성능
배열에서 순차 검색	O(N)
정렬된 배열에서의 순차 검색	O(N)
정렬된 배열에서의 이진 탐색 - 고정 배열 크기와 삽입, 삭제 시 추가 연산 필요	O(logN)
이진탐색 트리에서의 평균 최악의 경우 - 완전 이진 트리 또는 균형트리로 바꿀수 있다면 최악의 경우를 없앨 수 있다.	O(logN) O(N)

heap

• 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조
• 최대 힙
  • 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리
  • {부모노드의 키 값 > 자식노드의 키 값}
  • 루트노드 : 키 값이 가장 큰 노드
• 최소 힙
  • 키값이 가장 작은 노드를 찾기위한 완전 이진 트리
  • {부모노드의 키 값 < 자식노드의 키값}
  • 루트 노드 : 키 값이 가장 작은 노드
• 힙에서는 루트 노드의 원소만을 삭제 할 수 있다.
• 루트 노드의 원소를 삭제하여 반환한다.
• 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.