Binary Tree   이진 트리

(2018-10-16)

Complete Binary Tree, 완전 이진 트리, Heap, 힙, Binary Search Tree, 이진 탐색 트리, B-Tree, B-tree, B 트리

1. 이진 트리 (Binary Tree)

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

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


2. 이진 트리 종류

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

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

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

  ㅇ 힙 (Heap)
     - 부모의 값이 자식 보다 항상 크다 또는 작다 라는 조건을 만족하는 완전 이진 트리
        . 형제 간에는 값의 크고작음이 상관 없음
     - 형제들 간에 대소 관계가 정해지지 않으므로, 
        . 부분 순서 트리(Partial Ordered Tree) 라고도 함

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


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

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


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

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

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


5. 이진 탐색 트리 (Binary Search Tree, BST)

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

  ㅇ (순서 앞섬) 왼쪽 자식 노드 => 부 노드 => 오른쪽 자식 노드 (순서 뒤짐)
     - 例) 부모 왼쪽의 노드들은 부모 보다 앞서는 모든 노드들을 포함
     - 例) 부모 오른쪽 노드들은 부모 보다 뒤지는 모든 노드들을 포함

  ㅇ 데이터 집합에서 최대값최소값을 쉽게 찾을 수 있게 만든 자료구조


6. B 트리 (B-Tree, Balanced Tree)

  ㅇ 이진 탐색 트리를 보다 일반화시킨 트리 자료구조를 말함
     - 데이터베이스파일시스템에 널리 쓰이는 자료구조

  ㅇ 성능 및 공간 활용을 위해 이진 탐색 트리에 제약조건을 부가시켜 확장한 것
     - 트리가 항상 균형을 유지하고, 
     - 삭제로 인한 공간 낭비 최소화

  ㅇ DBMS에서 B-Tree
     - 특정 레코드 검색 시에,
        . 정확한 인덱스 키 값, 패턴 매칭, 부분 매칭, 범위 매칭 등으로도 검색 가능
     - 순차 접근 및 임의 접근 모두 가능
     - 색인순차접근방식과는 달리, 색인 키를 갱신하더라도 성능 저하가 발생하지 않음
     - 인덱스화된 컬럼의 원래 값을 변형시키지 않고, 
       인덱스 자료구조체 내에서 항상 정렬된 상태를 유지함


[트리] 1. 트리 2. 트리 관련 용어 3. 트리 종류 4. 멀티캐스트 트리 5. 스패닝 트리 6. 이진 트리 7. 트리 순회

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