BST   Binary Search Tree   이진 탐색 트리

(2022-04-30)

이진 검색 트리, AVL 트리


1. 이진 탐색 트리 (Binary Search Tree, BST)이진 트리의 구조를 갖으나, 자료의 검색,삭제,삽입,정렬 등에 효율적이게 한 트리 자료구조


2. 이진 탐색 트리의 특징이진 탐색을, 보다 쉽게 효과적으로 구현할 수 있게 함
  ㅇ 최대값최소값을 쉽게 찾을 수 있음

  ㅇ 삽입,삭제시에, 올바른 위치를 찾아 곧바로(빠르게) 넣거나 뺄 수 있음
     - 한편, 배열의 경우에는, 삽입,삭제시에 매번 다시 정렬을 해야 만 이진 탐색이 가능해 짐
  ㅇ 검색시에, 루트 노드부터 시작함
     - 이곳부터 시작하여 원하는 키 값을 갖는 원소를 찾아나가는 방식임

  ㅇ 시간복잡도는, 
     - 평균적으로, Θ(log n)에 저장,검색 가능
     - 최악의 경우에, O(n)이 걸림


3. 이진 탐색 트리의 구조

  ㅇ 최상위 레벨에 루트 노드가 있음
  ㅇ 각 노드는, 1개의 키 값 만을 갖음 
     - 즉, 키 값이 모두 서로 달라야 함
  ㅇ 각 노드는, 최대 2개의 자식 노드를 갖음
     - 이들 각각을 가리키는 최대 2개의 포인터를 갖음
  ㅇ 각 노드의 키 값은 크기 순서가 있게 됨
     - (순서 앞섬) 왼쪽 자식 노드 => 부 노드 => 오른쪽 자식 노드 (순서 뒤짐)
        . 즉, 왼쪽 자식 노드 값 < 부모 노드 값 < 오른쪽 자식 노드 값
     - 例) 부모 왼쪽의 자식 노드들은, 부모 보다 앞서는(작은값) 노드들을 포함
     - 例) 부모 오른쪽 자식 노드들은, 부모 보다 뒤지는(큰값) 노드들을 포함
        


4. 이진 탐색 트리의 개선  :  균형 잡힌 이진 탐색 트리

  ㅇ AVL 트리 (AVL Tree, Adelson-Velskii and Landis's Tree)
     - 한 노드를 중심으로 좌우 부분의 트리 높이(height)의 차가 1 이하가 되도록 함

     - 가장 초기에 나온 균형 잡힌(Balanced) 이진 탐색 트리 임

  ㅇ B 트리 (B-Tree, Balanced Tree)
     - 균형 잡힌 이진 탐색 트리를 보다 일반화시킨 트리 자료구조를 말함

     - 데이터베이스파일시스템에 널리 쓰이는 자료구조

트리
   1. 트리   2. 트리 용어   3. 트리 종류   4. 트리 순회   5. 스패닝 트리   6. 이진 트리   7. 이진 트리 종류   8. 이진 탐색 트리   9. B 트리 (균형 트리)   10. 이진 힙   11. 멀티캐스트 트리   12. 결정 트리  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"