BST   Binary Search Tree   이진 탐색 트리, 이진 검색 트리

(2020-01-11)

AVL 트리

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

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

  ㅇ 특징
     - 이진 탐색을, 보다 쉽게 효과적으로 구현할 수 있음
        . 삽입,삭제시에, 올바른 위치에 곧바로(빠르게) 넣거나 뺄 수 있음
        . 한편, 배열의 경우에는, 삽입,삭제시에 매번 다시 정렬을 해야 만 이진 탐색이 가능해 짐
     - 최대값최소값을 쉽게 찾을 수 있음
     - 검색시에 시간복잡도는, 
        . 평균적으로, Θ(log n)에 저장,검색 가능
        . 최악의 경우에, O(n)이 걸림


2. AVL 트리 (AVL Tree, Adelson-Velskii and Landis's Tree)

  ㅇ 한 노드를 중심으로 좌우 부분의 트리 높이(height)의 차가 1 이하가 되도록 하는 이진 탐색 트리
     - 가장 초기에 나온 균형 잡힌(Balanced) 이진 탐색 트리


3. B 트리 (B-Tree, Balanced Tree)이진 탐색 트리를 보다 일반화시킨 트리 자료구조를 말함
     - 데이터베이스파일시스템에 널리 쓰이는 자료구조


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

 
        요약목록     참고문헌