넘치게 채우기

힙 힙(Heap)은 다음과 같은 특성을 가지고 있다: 1. 완전 이진 트리이다. 2. (부모 노드의 index) = (자식 노드의 index) // 2 3. (왼쪽 자식의 index) = (부모 노드의 index) * 2 4. (오른쪽 자식의 index) = (부모 노드의 index) *2 +1 5. 루트의 index는 1이다. (구현의 편의상 1부터 시작한다.) 힙은 이러한 특성때문에 보통 배열로 많이 구현한다. 힙의 삽입과 삭제는 O(log N)이 걸리고, 탐색에는 O(N)이 걸린다. 힙은 두 가지의 종류가 있다. 최대 힙과 최소 힙이다. 최대 힙(max heap)은 부모 노드의 key값이 자식 노드의 key 값보다 큰 힙이고, 최소 힙(min heap)은 부모 노드의 key값이 자식 노드의 key ..

트라이란? 트라이는 문자열의 저장과 탐색을 효율적으로 하기 위한 k진 탐색 트리이다. 단어들이 공동으로 가지는 접두사들을 이용해서 문자열을 저장하고 탐색한다. 트라이의 특징 1. 트라이의 루트에는 빈 문자열을 나타내는 노드부터 시작한다. 루트 노드부서 시작해서 문자열의 접두사부터 따라가기 시작한다. 2. 각 노드는 문자와 자식 노드에 대한 포인터를 가지고 있다. 3. 종료 노드는 해당 문자열이 Trie에 존재함을 나타낸다. 4. 문자열 검색은 루트에서 시작하여 해당 문자열의 모든 문자를 따라 이동한다.(문자열의 접두사를 얻을 수 있다) 트라이의 시간복잡도는 O(n)(문자열의 길이만큼) 이다.트라이는 검색이나 사전 등에서 사용된다. 각 노드는 다음 자손의 포인터와 nil을 모두 포함하는 배열을 가지고 있다..

레드블랙트리의 삭제의 순서는 다음과 같다: 1. 삭제할 노드를 찾는다 2. 삭제할 노드의 자식이 a. 둘인 경우 - 없앨 노드의 오른쪽 서브트리의 가장 왼쪽 노드(또는 왼쪽 서브트리의 가장 오른쪽 노드)로 노드를 바꾸고, 그 잎 노드를 없애준다. b. 하나인 경우 - 삭제되는 노드의 부모노드와 자식노드를 연결시킨다. c. 없는 경우 - 노드를 없애주면 된다. 여기까지는 이진탐색트리의 노드제거와 같다. 3. 삭제되는 노드의 색깔이 빨간색인 경우, 여전히 레드블랙트리의 규칙을 만족하므로 삭제가 완료된다. 그러나, 삭제되는 노드의 색이 검은색인 경우, 그 자리를 대체하는 노드를 검은색으로 칠한다. 여기서, 대체하는 노드 역시 검은색인 경우, 이중 흑색노드가 생긴다. 그럼, 이중 흑색노드를 어떻게 해결하냐? C..

레드블랙트리의 삽입 레드-블랙트리의 삽입에서, 다음과 같은 과정을 거친다: 1.이진 탐색 트리와 같이 노드를 삽입하고, 삽입한 노드의 색은 빨간색으로 한다. 2.트리에 문제가 생기진 않는지 확인해주고, 문제가 있으면 고쳐준다. 레드블랙트리의 삽입에서의 문제 해결은 다음과 같은 경우들이 있다: 삽입되는 노드를 편의상 z라고 가정해보자. 1. z가 루트인 경우 z가 루트인 경우는 쉽다. 루트 노드의 색은 검정색이여야 하므로 빨간색을 검은색으로 칠해주면 된다. 이 경우를 제외한 나머지 경우는 모두 부모 노드가 빨간색이라 Double Red가 생긴 경우이다. 2. z의 삼촌이 빨간색인 경우 z의 삼촌이 빨간색일 땐, 조부모 노드(부모노드의 부모노드)의 색을 빨간색으로 칠해주고, 부모노드와 삼촌노드를 검은색으..

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

vice versa. 지난 글처럼, 라틴어에서 온 표현이다. 뜻은 그 반대(도 마찬가지이다)라는 뜻이다. 순영어로는"the other way round"라고 할 수 있다. vice는 자리, 위치, versa는 돌다라는 뜻을 가지고 있다. 예시: We can't go forward without her and vice versa. 우린 그녀없이는 나아갈 수 없고, 그녀도 마찬가지야.

영문으로 글을 읽다보면, e.g.와 i.e. 둘 다 많이 봤을 것이다. 뜻부터 말하자면, e.g.는 라틴어 "exempli gratia"에서 따온 말로, 영어로는 "for example", "예를 들어서"의 의미를 가진다. i.e.는 라틴어 "id est"의 약자로, 영어로는 "in other words", "that is to say", "다시 말해서"의 의미를 가진다. 둘 다 소문자로 써야 하며, 자모 사이에 점을, 맨 끝에도 점을 찍어줘야 한다. 예시: Recolouring is the change in colour of the node i.e. if it is red then change it to black and vice versa. 리컬러링은 노드의 색을 바꾸는 것이다. 다시 말해서, 만약 ..

이전에 이진 탐색 트리 편에서, 균형잡힌 트리와, 그렇지 못한 트리를 보았을 것이다. 그래서 이번에는 불균형한 트리를 균형잡힌 트리로 잡아주는 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..