Red-Black 트리는 red-black properties를 모두 만족하는 이중 탐색 트리이다. 1. 모든 노드는 빨간색 혹은 검은색이다.2. 루트노드는 검은색이다.3. 모든 리프노드(NIL 노드)는 검은색이다.4. 빨간색 노드의 자식은 검은색이다. (빨간색 노드가 연속적으로 존재할 수 없다.)5. 임의의 노드에서 자손 NIL노드까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외) Red-Black 트리도 BST의 한 종류이므로,먼저 BST를 기본적으로 구현하되(1) rbNode 구조체 멤버로 color와 parent를 추가한다.(2) rbTree 구조체를 새롭게 도입하여 NIL 노드를 활용할 수 있도록 한다. (t->NIL->color = Black) 다음은 Insertion..

정점 집합 V와 이들 사이에 존재하는 간선집합 E로 구성된 그래프 G를 보통 G = (V, E)로 표시한다.정점의 총 수 |v|는 흔히 소문자 n으로 표기한다.정점 u와 정점 v를 잇는 간선은 관행적으로 {u, v}는 주로 무방향 간선을, (u,v)는 방향 간선을 나타낼 때 쓰인다.그래프의 표현1) 인접 행렬n x n 행렬을 준비하고, 정점 i 와 정점 j 사이에 간선이 있으면 행렬 (i, j)원소, (j, i) 원소 값을 1로 할당한다. 나머지 자리에는 0을 할당한다.(무방향 그래프, 가중치가 없는 경우)가중치가 있는 경우 행렬의 각 원소에 1 대신 가중치를 저장한다.정점 i에서 정점 j로 향하는 방향이 있는 간선일 경우 (방향 그래프일 경우) 행렬(i, j)에 값을 (1 또는 가중치) 할당한다.간선의..

1. 선택 정렬 (Selection Sort)for (last : n-1 --> 1) 내려가면서 반복 A[0~last] 중 가장 큰 수 A[k]를 찾는다. A[k]와 A[last]를 교환한다.# 선택 정렬(selectionSort)def selectionSort(A): for last in range(len(A)-1, 0, -1): max = 0; index = -12345 for k in range(last+1): if A[k] > max: max = A[k] index = k A[index], A[last] = A[last], A[index]2. 버블 정렬 (B..

해시 테이블해시 테이블은 자료를 검색, 삽입, 삭제하는데 평균 O(1)(상수시간)이 가능하게 하여 극단적 효율에 다다른 자료구조이다.적재율(Load Factor): 해시 테이블에 원소가 차 있는 비율해시 테이블의 크기가 m이고 저장된 키의 총 수가 n이면, 적재율은 n/m이고 보통 알파로 표기한다.적제율이 높을수록 충돌 확률이 높아져 해시 테이블의 성능이 나빠진다. 1. 해시 함수(1) 나누기 방법h(x) = x % mm은 2의 멱수에 가깝지 않은 소수를 택하는 것이 좋다나누기 방법은 해시 테이블 크기보다 큰 수를 해시 테이블 크기 범위에 들어 오도록 수축시킨다.(2) 곱하기 방법h(x) = lower(m*(x*A % 1))곱하기 방법에서는 먼저 입력 값을 0과 1 사이의 소수로 대응시킨 다음 해시 테이..

힙의 조건1. 완전 이진 트리2. 힙 특성 : 모든 노드는 값을 갖고, 자식 노드(들) 값 보다 크거나 같다.* 리스트가 A[0]부터 시작된다면, A[k]의 자식은 A[2*k+1]과 A[2*k+2], A[k]의 부모 노드는 A[(k-1)//2]이 된다.스며 오르기 (percolateUp) : 원소 삽입스며 내리기 (percolateDown) : 원소 삭제, 힙 생성힙의 구현 (Python)class Heap: def __init__(self, *args): if len(args) != 0: self.__A = args[0] # 파라미터로 온 리스틓 else: self.__A = [] def percolateUp(self, i):..

이진 검색 트리의 특성1. 각 노드는 킷 값을 하나씩 갖는다. 각 노드의 킷 값은 모두 다르다.2. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 갖는다.3. 임의 노드의 킷 값은 자신의 왼쪽 아래에 있는 모든 노드의 킷 값보다 크고, 오른쪽 아래에 있는 모든 노드의 킷 값보다 작다.* 검색 트리의 높이는 효율성에 큰 영향을 미친다. 1. 원소 검색 Search(tNode, x): if tNode == None or x == tNode.item: return tNode; elif x # 검색 def search(self, x): return self.__searchItem(self.__root, x) def __searchItem(self, tN..

AVL 트리 트리 내의 어떤 노드도 좌서브 트리와 우서브 트리의 높이 차가 1보다 크지 않은 상태로 유지되는 이진 검색 트리AVL 트리의 회전1. 좌회전def rotateLeft(self, t): tR = t.right; tRL = tR.left tR.left = t; t.right = tRL t.height = max(t.left.height, t.right.height) + 1 tR.height = max(tR.left.height, tR.right.height) + 1 # 밑에서 부터 올라가면서 높이를 수정해 주어야 한다! return tR2. 우회전def rotateRight(self, t): tL = t.left; tLR = tL.right tL.right = t; t.le..

파이썬 내장 리스트로 구현한 큐class ListQueue: def __init__(self): self.__queue = [] def enqueue(self, x): self.__queue.append(x) def dequeue(self): return self.__queue.pop(0) def front(self): if self.isEmpty(): return None else: return self.__queue[0] def isEmpty(self): return len(self.__queue) == 0 def dequeueAll(self): ..