Tree

Red Black Tree

Red Black Tree

BST (이진 탐색 트리)를 기반으로 둔 Tree. Tree의 Rebalancing 방법 중 하나로 balanced한 트리이다. 각 노드는 값(key)말고도 색을 갖고 있으며, 색은 레드 or 블랙 2종류이다. 1. Red Black Tree가 갖는 특성 Root Property : 루트(root)노드는 블랙(black)이다. External Property : 모든 외부 노드 (external node)는 블랙이다. Depth Property : 모든 단말 노드(leaf node)의 경우 루트부터 외부 노드 까지 방문하는 블랙 노드의 수가 같다. Internal Property : 빨강 노드의 자식은 블랙이다. == No Double Red : 레드 노드는 두개가 연속해서 올 수 없다....

Read More
Splay Tree

Splay Tree

Splaying이라는 기법이 사용되며, 이는 특정 노드에 대해 접근을 하면, 이를 루트로 위치하도록 재배치 하는 기법의 트리 1. 특징 구현이 단순 많이 접근한 노드에 대해서 빠른 접근이 가능하다 접근 빈도가 불균등하거나 비 랜덤 패턴의 경우 O(lgn)보다 더 유리하다. AVL-Tree와 RB-Tree와 달리 추가 데이터 저장 필요 없다. 최악의 경우 높이가 선형, 즉 O(n)이 나올 수 있다. 세그먼트 트리로 이용이 가능하다. k번째 원소 찾기, 구간 합, lazy Propagation, 구간 뒤집기 모두 쉽게 할 수 있다. x노드를 접근한다면, splay를 통해 root로 올라오면서 x보다 작은 노드들은 Left에, 큰 노드들은 Right에 모이는 특성을 이용...

Read More
AA Tree

AA Tree

RB-Tree를 응용한 트리로 RB-Tree의 많은 조건을 일부 제거하여 구현을 더 간단하게 만든 트리로 균형을 맞추기 위해 레벨의 개념을 사용한 트리이다. 부모와 레벨이 같은 자식 노드의 연결을 수평 링크라고 하며, 이 노드를 구분하기 위해 RED라는 개념을 이용한다. 1. 특징 왼쪽 자식은 RED가 될 수 없다. 연속으로 RED가 올 수 없다. (이중 RED 불가 == 이중 수평 링크) 루트에서 null가지 leafnode까지의 경로에는 동일한 수의 블랙 노드가 존재한다. (RB Tree의 규칙) 모든 leaf node의 레벨은 1이다. 모든 왼쪽 자식의 레벨은 부모의 레벨보다 1 낮다. 모든 오른쪽 자식의 레벨은 부모와 같거나 1 낮다. 모든 오른쪽 손자의 레벨은 할아버지 노드보다 낮다. 1보다 큰 레벨의 모든 노드들은 2개의 자식을 갖는다. 왼쪽 트리를 얼핏 보면 RB-Tree같지만 왼쪽 자식은 RED를 갖지 않는 AA-Tree이고, 이를 레벨을 기준으로 보면 오른쪽과 같이 그려 볼 수 있다....

Read More
AVL Tree

AVL Tree

BST (이진 탐색 트리)를 기반으로 둔 Tree. 어떤 노드를 기준으로 하더라도 왼쪽자식의 깊이와 오른쪽 자식의 깊이 차이가 1을 넘지 않는 트리 1. 용어 개념 정리 균형치 (Balance factor) : 자식노드의 깊이 차이 ( 왼쪽 서브트리의 높이 – 오른쪽 서브트리의 높이 ) BF는 -1, 0, 1이 기준이며, 이 범위를 벗어난다면, 그 트리의 균형은 깨진것이다. 2. 특징 BST의 모든 특징을 갖는다....

Read More
Tree

Tree

그래프의 일종으로, 여러 노드가 한개의 노드를 가리킬 수 없는 구조 선형구조가 아닌 (비선형), 부모자식의 관계를 가지는 계층형 구조 1. 용어 개념 (설명) Node (노드): 트리를 구성하고 있는 각각의 요소를 의미한다. Edge (= link, 간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다. Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다. Sibling (형제 노드) : 같은 부모를 갖는 노드 Degree (차수) : 해당 노드의 자식노드 개수 Depth (깊이) : 루트 노드 부터 현재 노드까지의 간선의 개수 Level (레벨) : 같은 깊이를 갖는 노드들의 집합 루트 노드의 레벨을 1이 아닌 0으로 시작할 수도 있다. 편한대로 하면 된다. Height (높이) : 트리의 최대 레벨 Terminal Node (= leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다. Internal Node (내부노드, 비단말 노드) : 노드를 제외한 모든 노드로 루트 노드를 포함한다. https://www.gowoonsori.com/images/datastructure/tree/perfect2.png does not exist 위의 트리로 예를 들어 설명하자면, 아래와 같이 된다....

Read More