넘치게 채우기

레드-블랙 트리는 스스로 균형을 잡는 자가 균형 이진 탐색 트리(Self - Balancing Binary Search Tree)이다. 레드-블랙 트리에는 다음과 같은 조건들이 있다: 모든 노드는 빨간색 혹은 검은색이다. 루트 노드는 검은색이다. 리프 노드(NIL : Null Leaf)는 검은색이다. 빨간 노드의 자식 노드는 검은색이다(No Double Red, 빨간 노드가 연속으로 있을 수 없다) 어떤 노드에서 리프 노드까지 가는 검은 노드의 개수는 같다. + 레드-블랙 트리에서, 어떤 노드의 두 자녀가 같은 색이면 부모와 두 자녀의 색을 바꿔도 5번 규칙이 성립된다. ++ 추가되는 노드는 무조건 빨간색 노드이다. 5번 규칙을 충족시키기 위해서이다. 레드-블랙 트리의 높이 레드-블랙 트리의 높이 중에는..

이전에 이진 탐색 트리 편에서, 균형잡힌 트리와, 그렇지 못한 트리를 보았을 것이다. 그래서 이번에는 불균형한 트리를 균형잡힌 트리로 잡아주는 AVL 트리에 대해 알아볼 것이다. AVL트리는 다음의 특징이 있다: 이진 탐색 트리의 속성을 가진다. 왼쪽, 오른쪽 서브트리의 높이 차가 최대 1이다. 높이 차이가 1보다 커지면, 회전을 통해서 균형을 잡는다. 최대높이를 logN으로 유지시켜서 O(logN)으로 유지시킨다. 여기서 회전을 알기 전에, 균형을 아는 수치인 BF값을 알아보자. BF(Balance Factor) BF(k) = height(left(k)) - height(right(k)) 값이 1이면 왼쪽이 한 단계 높은 것이고, 0이면 높이가 같다는 뜻, -1이면 오른쪽이 한 단계 높은 것이다. 만약..

이진 탐색 트리? 이진 탐색 트리는 다음과 같은 조건이 있다: 같은 key값을 가지는 노드는 없다. 루트노드의 왼쪽 서브트리는 루트노드보다 작은 값들만 있어야 한다. 루트노드의 오른쪽 서브트리는 루트노드보다 큰 값들만 있어야 한다. 루트노드의 서브트리들 모두 이진 탐색 트리여야 한다. 이 조건들로, 이진 탐색 트리를 순회할 때 에는 보통 중위 순회를 이용한다. 이진 탐색 트리에는 세 가지 연산이 있다. 탐색(Search) 삽입(Insert) 삭제(Delete) 탐색 만약, 루트와 같은 값을 가진다면, 탐색을 멈춘다. 루트가 없는 경우 역시 탐색을 멈춘다. 만약, 루트보다 작은 값을 가진다면 왼쪽 서브트리에서, 더 큰 값을 가지면 오른쪽 서브트리에서 재귀한다. 구현 def _search(self, root..

트리의 모든 노드들을 방문하는 과정을 트리의 순회라고 한다. 스택, 큐, 연결 리스트와 같은 선형 자료구조에서는 순차적으로 노드들을 방문하지만, 비선형 자료구조인 트리에서는 다음과 같은 재귀적인 방법들이 있다: 전위 순회(Preorder) 중위 순회(Inorder) 후위 순회(Postorder) 전위 순회 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순으로 순회. 코드 구현 def preorder_traversal(self, node): #전위 순회 print(node.data, end=" ") if node.left: self.preorder_traversal(node.left) if node.right: self.preorder_traversal(node.right) cs A B D E C F G cs..

트리는 계층적 관계를 표현하는 자료 구조이다. 뿌리에서 가지를 늘려가며 뻗어가는 모양을 그리는 완전 그래프여서 트리라고 부른다. 회사의 조직도나, 컴퓨터 폴더의 구조에서 트리를 볼 수 있다. 용어 정리 ·노드 node 트리의 구성요소가 되는 정점(A, B, C, D, E, F) ·간선 edge 노드와 노드를 연결하는 연결선 ·루트 root 트리의 최상위 노드(A). 나무의 뿌리와 같은 위치에 있어서 이름이 루트이다. ·단말 노드 terminal node 아래로 또 다른 노드가 연결되어있지 않은 노드이다. 나무의 구조상 잎의 위치여서 잎사귀 노드(leaf node)라고도 한다. ·내부 노드 internal node 단말 노드를 제외한 모든 노드, 비단말 노드(nonterminal node)라고 한다. ·부..

해시 테이블(Hash Table)은 해시 함수를 통해서 얻은 인덱스에 key 와 value값을 저장하는 자료 구조이다. 해시 함수는 같은 key값을 받으면 같은 인덱스값으로 반환시킨다. 해시 함수 해싱을 하는 해시 함수에는 다음과 같은 것들이 있다: 1. Division Method: 가장 쉽고 간단한 방법이다. key값을 해시 테이블의 크기로 나눈 나머지를 인덱스로 정하는 것이다. h(k) = k mod m (k = key, m = size of hash table) m값은 소수이고, 2의 제곱수와 먼 값을 사용해야 효율적이라고 한다. 2. Multiplication Method: key값과 A(0 < A < 1)의 곱의 소수 부분에 테이블의 크기 m을 곱한 값의 정수값을 인덱스로 한다. h(k) = ..

덱 덱(deque)는 double - ended - queue의 줄임말로, 앞뒤로 빼고, 넣는 것이 가능한 자료구조이다. 큐와 스택을 합친 자료구조라고 볼 수도 있다. 파이썬에서는 collections 라는 모듈에서 쉽게 사용할 수 있다. 리스트와 비슷해보이는 연산들이 있지만, 들여다보면 차이가 존재한다. 리스트는 맨 앞 데이터를 빼면, 뒤에 있는 데이터들이 다 앞으로 당겨져서 시간복잡도가 O(n)이 된다. 덱은 이중 연결리스트 기반으로 구현되어, 맨 앞 데이터를 빼더라도 시간복잡도가 O(1)이다. 덱의 연산 appendleft(): 앞쪽으로 데이터 enqueue popleft(): 앞쪽에서 데이터 dequeue append(data): 뒤쪽으로 데이터 enqueue pop(): 뒤쪽에서 데이터 dequ..

지난 2-2 글에서, 내가 구현한 배열을 이용한 큐는, 엄밀히 따지면 파이썬의 리스트를 이용한 것이다. '배열'이랑 구현한 것과 다른 점은, 큐의 크기를 정하지 않는다.(append하면 뒤에 새 칸을 만들고, pop하면, 칸이 줄어든다) pop 했을 때, 뒤 데이터들이 빈 자리를 채우러 앞으로 당겨진다. 그래서, '배열스러운' 큐를 다시 구현해보았다. 큐 - '배열'을 이용한 구현(Python) class queue(): #큐 선언 def __init__(self, size): self.size = size self.arr = [None] * self.size self.first = 0 self.last = 0 def isEmpty(self): #큐가 비어있는지 확인 if self.first >= sel..

큐(Queue) 큐 자료구조는 우리가 평소에 줄을 서듯, 먼저 들어온 사람이 먼저 나가는, 선입선출(先入先出, First in First out)의 형식을 따른다. 큐의 연산 큐의 연산은 다음 5가지가 있다: isEmpty(): 큐가 비어있는지를 판단한다. True 또는 False값으로 반환된다. enqueue(data): 큐에 값을 입력시킨다. dequeue(): 큐의 제일 먼저온 값을 내보낸다. rear(): 큐의 맨 뒤에 있는 값을 반환한다. front(): 큐의 제일 반저온 값을 반환한다(큐에서 pop하지는 않는다) 큐의 구현 - 배열을 이용한 구현(Python) class queue(): #큐 선언 def __init__(self): self.arr = [] def isEmpty(self): #..

스택(Stack) 스택 자료구조는 탄창에 총알을 넣고 빼듯, 먼저 넣은 데이터를 늦게 꺼내는 선입후출(先入後出, FILO(First in Last out)), 후입선출(後入先出, LIFO(Last in First Out))을 따른다. 스택의 연산 스택의 연산은 다음 4가지가 있다: isEmpty() : 스택이 비어있는지를 판단한다. push(data) : 스택의 맨 위에 데이터를 쌓는다 pop() : 스택의 맨 위 데이터를 스택에서 뺀다. top() : 스택의 맨 위의 값을 확인한다. 스택의 구현 - 배열을 이용한 구현(Python) class stack(): #스택 선언 def __init__(self): self.arr = [] def _len_(self): return len(self.arr) de..