Tree

트리는 스택이나 큐 같은 선형 구조가 아닌 비선형 자료구조이다.

계층적 관계를 표현한다.

삽입 삭제 같은 사고보다는 자료구조 자체로 바라보는 것이 좋다.

 

• Binary Tree
  • 자식 노드가 최대 두 개인 노드들로 구성된 트리
  • 층별로 level을 표현하고 최고레벨을 height라 한다.
    • 포화 이진 트리(Perfect Binary Tree)
      • 모든 레벨이 꽉 찬 이진트리
    • 완전 이진 트리(Complete Binary Tree) 
      • 왼쪽부터 차례로 채워져 있는 이진트리
        • 이진 힙(Binary Heap)
          • Max Heap
            • 각 노드의 값이 해당 children 보다 크거나 같음
            • 최대값을 찾을 때 O(1)
          • Min Heap
            • 각 노드의 값이 해당 children 보다 작거나 같음
            • 최소값을 찾을 때 O(1)
          • 삽입 삭제?
    • 정 이진 트리(Full Binary Tree)
      • 모든 노드가 0개 혹은 2개의 자식을 가진 트리
• BST (Binary Search Tree)
  • 이진 트리의 일종이다.
  • 노드에 저장된 키는 유일하다
  • 부모의 키가 왼쪽 자식 노드보다 크다
  • 부모의 키가 오른쪽 자식 노드보다 작다.
  • 왼쪽과 오른쪽 서브트리도 이진 탐색트리이다.
  • 트리의 높이가 하나씩 증가할때마다 노드의 수가 두배씩 증가하므로 탐색연산은 O(logN) = O(h) 
  •  Worst Case : 편향트리가 된다면, O(n) 이 될수있다.
    • Rebalancing : Red-Black Tree
    • Red-Black Tree
      • BST를 기반으로 하는 자료구조이다.
      • Search, Insert, Delete 모두 O(logN)의 시간복잡도가 소요된다.
      • 노드 개수 대비 depth를 최소화하는 것이 핵심이다. (완전 이진 트리와 depth가 같음. 구조는 다르다)
      • 각 노드는 Red or Black 의 색깔을 갖는다
      • Root = black
      • leaf node = red
      • 노드가 red 이면 자식은 모두 black 이다
      • 각 노드에 대해서 descendant leaves 까지의 단순 경로는 모두 같은 수의 black node를 포함하고 이를 Black-Height라 한다. ex) 노드 A로 부터 A를 포함하지 않은 leaf node 까지의 simple path 상에 있는 black node의 개수는 같고 이를 Black-Height라 한다.
      • 삽입
        • 삽인된 노드를 Red로 저장한다. - Black-Height 변경을 최소화하기 위해
        • 위의 특성에 위배될 시에 색깔을 조정하고 Black-Height에 위배되었다면 rotation을 통해 height를 조정한다.
      • 삭제
        • 지워진 노드의 색이 black이면 Black-Height가 감소한 경로에 black node가 1개 추가되도록 rotation하고 노드의 색깔을 조정한다.
        • 지워진 노드의 색이 red이면 그대로 유지한다.