Binary Tree

Tree

• 계층적 관계 표현
• 루트 노드를 제외하고 모든 노드는 단 하나의 부모 노드만을 갖는다.
• 이진 트리는 배열과 연결 리스트로 표현 가능.
• 이진 트리란?
  • 루트를 기준으로 left, right subtree가 존재하고, 두 서브트리 모두 이진트리여야 한다.
  • 따라서 공집합도 노드로 인정한다.
  • 각 노드가 최대 2개 까지만 자식 노드를 갖을 수 있다.
• 이진 트리의 종류
  • 정 이진 트리 ( FULL )
    • 리프 노드를 제외하고 2개의 자식 노드를 갖는다. ( 자식이 있다면 2개고 아니면 없다! )
  • 완전 이진 트리 ( COMPLETE )
    • 왼쪽에서 오른쪽으로 순서대로 차곡 차곡 쌓인다
  • 포화 이진 트리 ( PERFECT )
    • 리프 노드 빼고 모든 노드가 2개의 자식 노드를 갖으며, 리프 노드들은 같은 레벨에 위치한다.
  • 이진 탐색 트리 ( BST )
    • 모든 키는 유일하다.
    • 어느 한 노드의 키 값은 자신의 왼쪽 부트리의 모든 노드들 보다 크다.
    • 어느 한 노드의 키 값은 자신의 오른쪽 부트리의 모든 노드들 보다 작다.
    • 왼쪽, 오른쪽 부트리 역시 위 조건들을 만족한다.
    • 이진 탐색의 빠른 검색 속도 O(log n)와 연결리스트의 장점인 삽입 삭제가 빠른 장점을 합친 것이다.
      삽입, 삭제는 O(1)이지만 위치를 찾는데에 검색 시간만큼인 log n 이 소요되어 O(log n) 이다.
  • 편향 이진 트리 ( SKEWED )
    • 한 쪽으로 편향된 트리 => AVL, Red - Black 트리로 해결할 수 있다.
  • B-tree, B+tree, AVL, Red-Black tree 등 여러 보완된 트리 구조들이 있다.