[자료구조론] 트리

트리

 트리 또한 그래프와 마찬가지로 비선형 자료구조이고, 순환 사이클을 갖지 않아 계층적 구조를 표현할 수 있는 그래프의 일종이다.

 

Node: 트리를 구성하고 있는 원소 그 자체를 말한다.

Edge: 노드와 노드 사이를 연결하고 있는 선을 말한다.
Root: 트리의 최상위 노드이다.

Terminal: 자식이 없는 노드를 말하고, Leaf Node라고도 불린다.

Internal: 트리의 최하위를 제외한 모든 노드를 말한다. (자식이 있는 노드)

Degree: 트리가 가질 수 있는 최대 자식의 수

Successor node: 현재 key값보다 큰 노드 중 가장 작은 노드 

Predecessor node: 현재 key값보다 작은 노드 중 가장 큰 노드

 

Binary Tree 

  잎노드를 제외한 모든 노드의 자식이 두 개 이하인 것을 말한다. 공집합 역시 노드로 인정한다. 노드로 이루어진 각 층을 Level 이라고 하며, Level의 수가 이 트리의 height가 된다. 

  이진트리의 종류

   1. Full. BInary Tree

       모든 Level이 가득 찬 이진트리

   2. Complete BInary Tree

       왼쪽에서 오른쪽으로 순서대로 채워진 트리

 

BST, Binary Search Tree

 이진트리이며, 데이터를 저장하는 특별한 규칙이 있다. (따라서 찾기 쉬움) 

 왼쪽 서브트리의 키값은 루트의 키값보다 작다.

 오른쪽 서브트리의 키값은 루트의 키값보다 크다.

 그리고 각각의 서브트리는 이러한 규칙을 만족한다. 

 *그러나 편향 트리가 될 가능성이 높다.

 

Red Black Tree

  편향트리의 문제를 해결하기 위해 Rebalancing이라는 기법을 사용하여 트리의 레벨을 재조정하게 된다. RBT는 위에서 그에 해당하는 기법의 하나로, 기존 이진트리탐색의 삽입,삭제,탐색의 비효율성을 개선한 방법이다. 

    각 노드는 Red 또는 Black이라는 색깔을 가진다.

    루트 노드는 Black이다.

    각 말단 노드는 Black이다

    어떤 노드의 색이 Red라면, 두 자식 노드의 색은 모두 Black이다.

    어떤 한 노드로부터 리프노드까지의 Black의 수는 리프노드를 제외하면 모드 같다. 

 * BST의 특징을 모두 가지고 있으며, 루트로부터 말단 노드까지의 최소 경로는 최대 경로의 두 배보다 크지 않다. (Balanaced node) 노드에게 자식이 없을 경우, Null값을 저장한다.