Tree

Tree

• Tree
  • 스택이나 Queue와 다르게 비선형 & 계층적 관계 자료 구조
  • 트리는 표현에 집중한다
  • Node, Edge, Root Node,
    Terminal Node(Leaf Node, 단말 노드) => 하위에 다른 노드가 없는 최하위 노드,
    Internal Node(내부 노드, 비단말 노드) => 단말 노드를 제외한 모든 노드(루트 포함)
• Binary Tree
  • 루트 노드를 중심으로 두 개의 서브 트리를 가지는 자료구조
    • 서브 트리 또한 모두 이진 트리여야함 (공집합 포함)
  • 트리의 depth를 숫자로 매겨서 레벨(Level)이라고 함( 0부터 시작 <- 루트 노드 )
  • 트리의 최고 높이를 Height(높이) 라고 함
  • 포화 이진 트리 (Perfect Binary Tree)
    • 모든 레벨이 꽉 찬 이진 트리
  • 완전 이진 트리 (Complete Binary Tree)
    • 위에서 아래로, 왼쪽에서 오른쪽 순서로 채워진 이진 트리
  • 정 이진 트리 (Full Binary Tree)
    • 모든 노드가 0개 or 2개의 자식 노드만을 가진 트리
• Binary Search Tree(BST)
  • 효율적인 탐색을 위한 저장 방법이 무엇일까 고안해서 나온 이진 트리
  • 데이터 저장 규칙
    • 이진 탐색 트리의 노드에 저장된 키는 유일하다 (키 중복 X)
    • 부모의 키가 왼쪽 자식 노드의 키보다 크다. (parent key > left child key)
    • 부모의 키가 오른쪽 자식 노드의 키보다 작다. (parent key < right child key)
    • 서브 트리도 모두 이진 탐색 트리
  • 탐색 => O(log n) (O(h => 높이)라고 하는게 좀 더 정확함)
    • 트리 높이를 하나씩 더해갈수록 추가하는 노드가 2개씩 증가하기 때문
  • 데이터 저장 규칙에 의해 한 쪽 노드에만 저장되는 편향 트리(Skewed Tree)가 발생할 수 있음
    • 성능이 좋지 않은 경우이며, Worst Case의 경우 O(n)의 탐색 시간이 걸림
    • 배열보다 많은 메모리를 사용하며 데이터를 저장했는데, 시간 복잡도가 같으면 비효율적인 상황이 발생함
    • 이를 해결하기 위해 Rebalancing 기법이 등장 ~> 균형을 잡기 위한 트리 구조의 재조정 ~> Red Black Tree가 이 기법을 통해 저장함
• Binary Heap
  • 일종의 Tree 형식, 배열에 기반한 Complete Binary Tree
    • 루트 노드의 인덱스가 0번이 아닌 1번부터 시작함
      • 고유 번호 값과 배열의 index를 일치(고유 번호가 1부터 보통 시작)
  • 힙에는 Max Heap과 Min Heap이 있음
  • 최대 힙(Max Heap)
    • 각 노드의 값이 children의 값보다 크거나 같은 Complete Binary Tree
    • Root Node가 가장 크기 때문에, 값을 찾는 연산이 O(1)
  • 최소 힙(Min Heap)
    • 각 노드의 값이 children의 값보다 작거나 같은 Complete Binary Tree
    • Root Node가 가장 작기 때문에, 값을 찾는 연산이 O(1)
  • 힙 구조를 유지하려면 재 정렬이 필요함
    • 특정 노드가 제거됐을 때, heap은 맨 마지막 노드를 root와 swap한 후, heapify에 따라 정렬
    • 노드를 추가할 때, 새로 들어온 노드의 값이 제일 작다고 가정하여 마지막에 삽입한 뒤 역 heapify를 함
• Red Black Tree
  • BST 를 기반으로하는 트리 형식의 자료구조
  • 탐색, 삽입, 삭제가 O(log n)의 시간 복잡도를 가짐
  • 동일한 노드 개수일 때, depth를 최소화해서 시간 복잡도를 줄이는 것이 핵심
  • 동일한 노드 개수일 때, depth가 최소가 되는 경우는 complete binary tree인 경우
  • 조건
    • 각 노드는 Red or Black의 색을 가짐
    • Root Node는 Black
    • 각 Leaf Node는 Black
    • 어떤 노드 색이 Red면 하위 두 children의 색은 모두 Black
    • 각 노드에 대해서 노드로부터 자손들(descendant leaves) 까지의 단순 경로는 모두 같은 수의 black nodes 들을 포함
      • 이를 해당 노드의 Black-Height라고 함
      • cf) Black-Height: 노드 x 로부터 노드 x 를 포함하지 않은 leaf node 까지의 simple path 상에 있는 black nodes 들의 개수
  • 특징
    • BST이므로 BST의 성질을 가짐
    • Root Node부터 Leaf Node까지 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 작음 ~> 이러한 상태를 balanced 상태라 함
    • 노드의 child가 없는 경우 child 포인터에 NULL 값을 저장 ~> NULL들을 Leaf Node로 간주
  • 삽입
    • BST 특성을 유지하며 노드를 삽입하면서, RED로 색을 지정한다.
      • Black-Height 변경을 최소화하기 위함
    • 삽입 결과 위의 RBT의 특징에 위배되면 색을 조정하고, Black-Height가 위배되면 rotation을 통해 height를 조정
    • 이 과정을 통해 RBT의 동일한 height에 존재하는 internal node들의 Black-height가 같아짐 ~> 최소 경로와 최대 경로 비율 유지