자료구조

1. Intro- RBTree는 노드의 속성중 색상을 정의하여 Red or Black으로 나타낸 후, BBST를 유지한다는 독특한 개념의 트리라고 말할 수 있다.- 이러한 RBTree는 탐색, 삽입,삭제 연산의 수행시간이 O(logN)을 넘지않는 특징을 가진다. 2. RBTree의 문제점- RBTree에 대한 설명은 13-2에서 했고, 이러한 RBTree의 문제점은 BBST를 유지하기 위해 까다로운 조건들을 고려해야한다는 것이다.- 그로인해, 프로그램이 복잡해지고, 길이는 증가한다. 즉, 프로그래머가 상대적으로 더 많은 노력을 하게 된다.- 이러한 RBTree을 간단하게 구현하고자 나온게 바로 LLRBTree이다.  3. LLRB Tree(Left-Leaning Red-Black Tree)- 일반적인 R..

1. Red-Black Tree?- Red-Black Tree는 균형 이진 탐색 트리(BBST)의 한 종류로, 삽입과 삭제 연산 후에도 트리가 균형상태를 유지- 이진 탐색 트리의 시간복잡도를 O(log n)으로 보장함- 각 노드에 색깔 속성을 추가하여, BBST를 만족하도록 트리를 유지함- 현재 포스팅에선 RB-Tree을 구현하진 않을 것이고, 그 다음 포스팅 LLRB Tree을 설명할 때 그때 구현하고자 한다.2. RBTree의 특징I) 노드는 Red or Black이다.II) Root Node는 항상 Black이다.III) Red 노드의 자식 노드는 모두 Black이다.--> No Double RedIV) 모든 leaf node는 모드 Black이다.V) Root에서 left node까지의 Black..

1. Intro- CLRS에서의 13챕터는 Red-Black Tree에 대해서 서술한다.- 하지만, 나는 AVL Tree(13-1) -> Red-Black Tree(13-2) -> LLRB Tree(13-3) 순으로 포스팅하고자 한다.- 이 순으로 이해해야 비교적 순조롭게 이해가 가능하다. 2. AVL Tree?- AVL Tree는 스스로 균형을 잡는 BST이다. 즉, BBST의 한 종류라고 생각하면 된다.- 한쪽으로 편향을 가진 이진트리가 되는 것을 방지해준다. 3. AVL Tree 특징I) AVL Tree는 BST의 속성을 가진다.II) left subtree와 right subtree의 높이 차이가 최대 1이다. --> Balance Factor의 절댓값이 1이하이다.--> Balance Facto..

1. Binary Search Tree?- 이진 탐색(Binary Search)의 개념을 트리 형태의 구조에 점목한 자료구조- 각 노드 키가 왼쪽 서브트리에 있는 키들보다 크고, 오른쪽 서브트리에 있는 키들보다 작다.- 일반적으로 키값이 같은 노드는 복수로 존재하지 않아야 한다.  2. BST의 구조- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.- 노드의 오른쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.- 루트의 왼쪽 서브트리와 오른쪽 서브트리는 BST이다. 3. BST CODE구현3.1. BST에 사용되는 클래스 class Node: def __init__(self, key, value): self.key = ke..