[Data Structure] Tree 관련 정리

• Tree
  • 비선형 자료구조
  • 계층적 관계 (Hierarchical Relationship)
  • 구성요소들
    • Node(노드) : 트리를 구성하고있는 각각의 요소를 의미한다
    • Edge(간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다
    • Root Node(루트 노드) : 트리구조에서 최상위에 있는 노드를 의미한다
    • Terminal Node(=leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어있지 않은 노드를 의미한다
    • Internal Node(내부 노드, 비단말 노드) : 단말 노드를 제외한 모든 노드, 루트 노드를 포함한다.
  • Binary Tree (이진 트리)
    • 루트노드를 중심으로 두 개의 서브 트리로 나뉘어 진다.
    • 나뉘어진 서브 트리도 모두 이진 트리여야한다.
    • 공집합도 이진 트리이다. (=노드가 하나 뿐인 것도 이진트리 정의에 만족)
    • 트리의 층을 Level이라고 일컫고 루트노드의 레벨은 0이다.
    • 트리의 최고레벨을 가리켜 해당 트리의 높이(height)라고 한다.
    • Perfect Binary Tree : 모든 레벨의 노드가 꽉 찬 이진 트리
    • Complete Binary Tree : 위→아래, 왼쪽→오른쪽으로 순서대로 차있음
    • Full Binary Tree : 모든 노드가 0 혹은 2개의 자식 노드만을 갖는 트리
  • BST(Binary Search Tree)
    • 규칙
      1. 이진 탐색의 트리의 노드에 저장된 키는 유일하다
      2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.(무조건 오른쪽이 큰 수)
      3. 부모의 킥 오른쪽 자식의 노드의 키보다 작다.
      4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다
    • 이진 탐색 트리의 탐색 연산 : O(log n) .= O(h)
    • 탐색의 Worst Case : O(n)
      • 저장되는 순서에 따라 한쪽으로만 노드가 추가되어 편향 트리(Skewed Tree)가 될 경우
      • 해결 방법 : Rebalancing (균형을 잡기 위한 트리 구조의 재조정) → Red-Black Tree에서 사용
        
        
        
        
• Binary Heap (=. Priority Queue)
  • Complete Binary Tree의 형식을 하고있는 자료구조
  • 배열의 트리의 값을 넣어줄 때, 0번은 건너뛰고 1번 index부터 루트노드가 시작
  • 최대힙(max heap), 최소힙(min heap)이 존재
    • Max heap : 각 노드의 값이 해당 children의 값보다 크거나 같은 Complete binary tree
    • Max Heap 에서는 Root node의 값이 가장 크므로, 최대 값을 찾는 연산의 time complexity는 O(1)이다.
    • heap 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하여 heapify 과정을 거친다. (맨마지막 노드를 루트 노드로 대체하여 시작) ⇒ O(log n)
  • Heapify(max-heapify)
    • root node의 값이 child node의 값보다 작으면 child node 중 값이 큰 node와 교체
    • 이 과정을 교체할 노드가 없을 때 까지 진행
      
      
      
      
      
• Red Black Tree
  • BST를 기반으로 하는 트리형식의 자료 구조
  • 검색,삽입,삭제의 시간 복잡도 : O(log n)
    • 동일한 노드의 개수일때, depth를 최소화(=complete binary tree)하여 시간 복잡도를 줄임
  • 정의
    1. 각 노드는 Red or Black 이라는 색깔을 가진다
    2. Root node의 색깔은 Black이다
    3. 각 leaf node는 Black
    4. 어떤 노드의 색깔이 red라면 두 개의 childeren의 색깔은 모두 black 이다.
    5. 각 노드에 대해, 임의의 노드로 부터 단말 노드까지의 단순 경로의 수는 모두 같은 black 노드의 개수를 지니고있다.
  • RB tree의 특징
    • BST의 특징을 모두 갖는다
    • 루트 노드로 부터 단말 노드까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다 → balanced 상태
    • 노드의 child가 없을 경우, child를 가리키는 포인터는 nil 값을 저장한다 nil은 leaf node로 간주한다.
  • 삽입
    • BST의 특성을 유지하며 노드를 삽입한다.
    • 삽입된 노드의 색깔을 RED로 지정한다.
      • 정의 5번(임의의 노드에서 nil 노드로 가는 black의 갯수는 같다)를 지키기 위해
      • = Black-Height 변경을 최소화 하기 위함
    • 삽입 결과 RBT의 특성을 위배(violation)시 노드의 색깔을 조정하고, Black-Height가 위배되었다면 rotation을 통해 height를 조정한다
      • 이러한 과정을 통해 RBT의 동일한 height에 존재하는 internal node들의 Black-height가 같아지게 되고 최소 경로와 최대 경로 크기 비율이 2미만으로 유지된다
  • 삭제
    • 삭제될 노드의 child 개수에 따라 rotation 방법이 달라지게 된다.
    • 만약 지워진 노드의 색깔이 Black인 경우, Black-Height가 1 감소한 경로에 black node가 1개 추가 되도록 rotation 하고 노드의 색깔을 조정한다.
    • 지워진 노드의 색깔이 Red인 경우 Violation이 발생하지 않으므로 RBT가 그대로 유지된다.
  • Java Collection에서 Tree map도 내부적으로 RBT로 이루어져있고 Hash map에서의 Seperate Chaining에서도 사용된다.

지식 출처

https://www.youtube.com/channel/UCReNwSTQ1RqDZDnG9Qz_gyg/featured

쉬운코드