트리는 계층적 관계(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개의 자식 노드만 갖는 이진트리를 가리켜 정 이진 트리라고 한다.
배열로 구성된 Binary Tree는 노드의 개수가 n 개이고 root가 0이 아닌 1에서 시작할 때, i 번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖는다.
BST (Binary Search Tree)
규칙1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
규칙2. 부모의 키가 왼쪽 자식노드의 키보다 크다.
규칙3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
규칙4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
이진 탐색트리의 탐색 연산은 O(logn). 정확히 말하자면 O(h) 트리의 높이를 하나씩 더해 갈수록 추가할 수 있는 노드의 수가 두배씩 증가.
편향트리(Skewed Tree)일 경우 Worst Case이며 시간복잡도는 O(n)이 된다.
Binary Heap
배열에 기반한 Complete Binary Tree
배열에 트리의 값들을 넣어줄 때, 0번째는 건너 뛰고 1번 index부터 루트노드가 시작됨(노드의 고유번호와 배열의 index를 일치 시켜 혼동을 줄이기 위함)
Max Heap
각 노드의 값이 해당 children의 값보다 크거나 같은 complete binary tree (Min Heap은 반대)
Max heap에서는 루트노드가 가장 크므로, 최대값 찾는데 O(1), complete binary tree이기 때문에 배열을 사용하여 Random Access 가능
Max heap에서 최소값을 찾으려면 O(logn)으로 접근할 수 있다.
Heap연산
삽입 : heap에 데이터를 삽입하고 heap 속성을 충족하는지 확인한 뒤 위반할 경우 heap속성을 충족하도록 재구성을함(heapify)
삭제 : 삭제하려는 항목을 제거한 뒤 그 자리에 마지막 항목을 놓고 다시 heapify 과정을 거친다.
Red Black Tree
RBT(Red-Black Tree)는 BST를 기반으로 하는 트리 형식의 자료구조
Search, Insert, Delete에 O(logn)의 시간복잡도
동일 갯수의 노드일 때, Depth를 최소화하여 시간복잡도를 줄임 (depth가 최소가 되려면 complete binary tree)
Red-Black Tree의 정의
각 노드는 Red 또는 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 들의 개수
Red-Black Tree의 특징
Binary Search Tree이므로 BST의 특징을 모두 같는다.
Root node부터 leaf node까지의 모든 경로 중 최소 경로와 최대경로의 크기비율은 2보다 크지 않다. 이러한 상태를 balanced상태라고 함
노드의 child가 없을 경우 child를 가리키는 포인터는 NIL값을 저장한다. 이러한 NIL들을 leaf node로 간주한다.
삽입
BST의 특성을 유지하면서 노드를 삽입.
삽입된 노드의 색은 Red. (Black-Height변경을 최소화 하기 위함)
RBT의 특성에 위배(violation)시 노드의 색을 조정하고, Black-Height가 위배되었다면 rotation을 통해 height를 조정.
-> 이러한 과정으로 RBT의 동일한 height를 가진 internal node들의 Black-Height가 같아지고 최소, 최대 경로의 크기 비율이 두배 이상이 될 수 없다.
삭제
BST 특성을 유지하면서 해당 노드를 삭제.
삭제될 노드의 child의 갯수에 따라 rotation 방법이 달라짐
지워진 노드의 색이 Black이면 Black-Height가 1 감소한 경로에 black node가 1개 추가되도록 rotation 하고 노드의 색을 조정
지워진 노드의 색이 Red면 Violation이 발생하지 않으므로 RBT가 그대로 유지된다.