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. 멀티캐스트 트리
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
            1. 자료구조
            2. 자료구조 종류
        1.   선형 자료구조 (리스트 등)
        2.   비선형 자료구조 (트리,그래프)
          1.   그래프
          2.   트리
            1.   1. 트리
                2. 트리 용어
                3. 트리 종류
                4. 이진 트리
                5. 이진 탐색 트리
                6. 스패닝 트리
                7. 트리 순회
                8. B 트리
                9.
                10. 멀티캐스트 트리
        3.   기타 자료구조
        4.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     요약목록     참고문헌