Binary Tree   이진 트리

(2019-12-05)

Complete Binary Tree, 완전 이진 트리

1. 이진 트리 (Binary Tree)

  ㅇ 모든 노드차수/자식이 2 이하(최대 2)인 특수한 형태의 순서 트리

  ㅇ 특징
     - 각 노드가 최대 2개의 자식 노드를 갖으며, 좌 우 자식 노드로 구분됨
     - 이진 트리순서 트리로써, 노드 위치 및 순서가 중요한 의미를 갖음
        
     - 루트 노드 레벨(level)은 0 으로 함
     - 레벨 깊이(depth) i일 경우, 갖을 수 있는 최대 노드 수는 2i - 1


2. 이진 트리 종류

  ㅇ 전 이진 트리 (Full Binary Tree)
     - 각 레벨에 노드들이 꽉 차있는 이진 트리
        . 모든 노드차수/자식이 2 이어야 함

  ㅇ 포화 이진 트리 (Perfect Binary Tree)
     - 모든 단말 노드의 레벨이 동일하며, 최하위 자식 노드들이 모두 차 있음

  ㅇ 완전 이진 트리 (Complete Binary Tree)
     - 부모,왼쪽 자식,오른쪽 자식 순으로, 채워지며 만들어지는 이진 트리
        . 또는, 포화 이진 트리의 단말 노드들을 오른쪽에서부터 제거하여 얻어진 트리
     - 마지막 레벨을 제외하고는, 각 레벨의 노드들이 모두 차 있음
        . 마지막 레벨에서는, 노드가 꽉 차있지 않아도 되지만, 중간에 빈 곳이 있으면 안됨
     - 여기서, 완전(complete)은, 
        . 부모가 자식을 왼쪽부터 채운다는 말임 ☞ 순서 트리 참조

  ㅇ 이진 힙 (Binary Heap)
     - 완전 이진 트리의 일종
        . 부모,자식 간에는 대소 관계가 있으나, 형제들 간에 대소 관계가 정해지지 않음
        . 이에따라, 부분 순서 트리(Partial Ordered Tree) 라고도 함

  ㅇ 균형 트리 (Balanced Tree)
     - 이진 트리에서 하위 노드 구조가 좌우 대칭이 되도록 한 것 (例, B-tree)


3. 이진 트리 표현선형 자료구조인 일차원 배열 표현
     - 저장 공간 활용 비효율적, 부모 자식 노드 구분이 어려움, 프로그램 구현 용이
     - 완전이진트리에는 좋은 성능을 갖음

  ㅇ 비선형 자료구조연결 리스트 표현 (보다 유용함)


4. 이진 트리 순회 (Binary Tree Traversal)

  ㅇ 각 노드를 한번씩 만 방문하며 저장 정보를 확인하는 것

  ㅇ 순회 종류 : 방문 순서에 따른 구분
     - 중위(Inorder) 순회   : 왼쪽 서브트리 → 자신 → 오른쪽 서브트리
     - 후위(Postorder) 순회
     - 전위(Preorder) 순회


5. 자료의 검색,삭제,삽입에 효율적이게 한 트리 자료구조이진 검색 트리 (Binary Search Tree, BST)
     - 이진 트리 구조를 갖으나, 자료의 검색,삭제,삽입에 효율적이게 한 트리 자료구조
     - 각 노드는 2개의 자식 노드를 각각 가리키는 2개의 포인터를 갖음

  ㅇ AVL 트리 (AVL Tree, Adelson-Velskii and Landis's Tree)
     - 한 노드를 중심으로 좌우 부분의 트리 높이(height)의 차가 1 이하가 되도록 하는 이진 탐색 트리
     - 가장 초기에 나온 균형 잡힌(Balanced) 이진 탐색 트리B 트리 (B-Tree, Balanced Tree)
     - 이진 탐색 트리를 보다 일반화시킨 트리 자료구조를 말함
     - 데이터베이스파일시스템에 널리 쓰이는 자료구조

  ㅇ 한편, 
     - 이진 검색 트리 : 최대 2개의 자식 노드를 가질 수 있음
     - 다진 검색 트리 : 최대 3 이상의 자식 노드를 갖는 검색 트리 (k진 검색 트리)


[트리] 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.   기술경영

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