Red Black Tree
- Data structure
- 2020년 10월 23일
BST (이진 탐색 트리)를 기반으로 둔 Tree. Tree의 Rebalancing 방법 중 하나로 balanced한 트리이다. 각 노드는 값(key)말고도 색을 갖고 있으며, 색은 레드 or 블랙 2종류이다. 1. Red Black Tree가 갖는 특성 Root Property : 루트(root)노드는 블랙(black)이다. External Property : 모든 외부 노드 (external node)는 블랙이다. Depth Property : 모든 단말 노드(leaf n...
Read MoreSplay Tree
- Data structure
- 2021년 6월 3일
Splaying이라는 기법이 사용되며, 이는 특정 노드에 대해 접근을 하면, 이를 루트로 위치하도록 재배치 하는 기법의 트리 1. 특징 구현이 단순 많이 접근한 노드에 대해서 빠른 접근이 가능하다 접근 빈도가 불균등하거나 비 랜덤 패턴의 경우 O(lgn)보다 더 유리하다. AVL-Tree와 RB-Tree와 달리 추가 데이터 저장 필요 없다. 최악의 경...
Read MoreAA Tree
- Data structure
- 2021년 6월 3일
RB-Tree를 응용한 트리로 RB-Tree의 많은 조건을 일부 제거하여 구현을 더 간단하게 만든 트리로 균형을 맞추기 위해 레벨의 개념을 사용한 트리이다. 부모와 레벨이 같은 자식 노드의 연결을 수평 링크라고 하며, 이 노드를 구분하기 위해 RED라는 개념을 이용한다. 1. 특징 왼쪽 자식은 RED가 될 수 없다. 연속으로 RED가 올 수 없다. (이중 RED...
Read MoreAVL Tree
- Data structure
- 2020년 10월 23일
BST (이진 탐색 트리)를 기반으로 둔 Tree. 어떤 노드를 기준으로 하더라도 왼쪽자식의 깊이와 오른쪽 자식의 깊이 차이가 1을 넘지 않는 트리 1. 용어 개념 정리 균형치 (Balance factor) : 자식노드의 깊이 차이 ( 왼쪽 서브트리의 높이 – 오른쪽 서브트리의 높이 ) BF는 -1, 0, 1이 기준이며, 이 범위를 벗어난다면, 그 트리의 균형은 깨진것이다. 2. 특징 BST의 모든 특징을 갖는다...
Read MoreTree
- Data structure
- 2020년 9월 20일
그래프의 일종으로, 여러 노드가 한개의 노드를 가리킬 수 없는 구조 선형구조가 아닌 (비선형), 부모자식의 관계를 가지는 계층형 구조 1. 용어 개념 (설명) Node (노드): 트리를 구성하고 있는 각각의 요소를 의미한다. Edge (= link, 간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다. Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의...
Read More