14장 노드 기반 자료 구조
-
연결 리스트
- 연결 리스트는 항목의 리스트를 표현하는 자료구조로, 메모리 곳곳에 흩어진 데이터(노드)들이 다음 노드의 메모리 주소를 포함하고 있는 구조이다.
class Node attr_accessor :data, :next_node def initialize(data) @data = data end end class LinkedList attr_accessor :first_node def initialize(first_node) @first_node = first_node end end- Node 클래스에 노드의 값과 다음 노드로의 링크인 next_node를 저장하여 연결 리스트를 구현하였다. 또한 연결 리스트가 어디서부터 시작하는 지 쉽게 알려주기 위해 LinkedList 클래스를 생성하여 다음과 같이 코드를 작성해 LinkedList 클래스로 리스트를 참조할 수 있다.
list = LinkedList.new(node_1)- 연결 리스트를 다룰 때는 첫 번째 노드에만 즉시 접근할 수 있다.
-
읽기
def read(index) current_node = first_node current_index = 0 while current_index < index do current_node = current_node.next_node current_index += 1 return nil unless current_node end return current_node.data end- 배열의 읽기가 O(1)인데 반해 연결 리스트는 항상 첫 번째 노드부터 순차적으로 노드 사슬을 따라서 조회해야하기 때문에 최악의 경우에 O(N)의 단계가 걸린다.
-
검색
def index_of(value) current_node = first_node current_index = 0 begin if current_node.data == value return current_index end current_node = current_node.next_node current_index += 1 end while current_node return nil end- 배열과 동일하게 연결 리스트의 검색 속도도 O(N)으로 첫 번째 노드에서 시작해 각 노드의 링크를 따라 다음 노드로 가며, 찾고 있는 값을 찾을 때까지 매 값을 검사한다.
-
삽입
def insert_at_index(index, value) new_node = Node.new(value) if index == 0 new_node.next_node = first_node self.first_node = new_node return end current_node = first_node current_index = 0 while current_index < (index - 1) do current_node = current_node.next_node current_index += 1 end new_node.next_node = current_node.next_node current_node.next_node = new_node end- 연결 리스트는 배열처럼 삽입하려는 인덱스 이후의 데이터를 쉬프트하는 과정 없이 노드의 연결을 끊고 새로운 노드와 연결만 해주면 되기 때문에 인덱스 0에 삽입할 때 O(1)의 단계가 걸린다.
- 노드를 연결하기 위해서는 첫번째 인덱스부터 삽입하려는 인덱스까지 조회하는 과정이 필요하기 때문에 맨 마지막에 삽입할 경우 N + 1 => O(N)의 단계가 걸리며 배열과 최선/최악의 시나리오가 반대이다.
-
삭제
def delete_at_index(index) if index == 0 self.first_node = first_node.next_node return end current_node = first_node current_index = 0 while current_index < (index - 1) do current_node = current_node.next_node current_index += 1 end node_after_deleted_node = current_node.next_node.next_node current_node.next_node = node_after_deleted_node end-
삽입과 마찬가지고 맨 앞의 노드를 삭제할 경우에 O(1)이 걸리지만 맨 마지막 인덱스의 노드를 삭제할 경우 N + 1 => O(N)의 단계가 걸린다.
연산 배열 연결 리스트 읽기 O(1) O(N) 검색 O(N) O(N) 삽입 O(N)(끝에서 하면 O(1)) O(N)(앞에서 하면 O(1)) 삭제 O(N)(끝에서 하면 O(1)) O(N)(앞에서 하면 O(1)) -
전체적으로 보면 시간 복잡도 면에서 연결 리스트는 그다지 매력적이지 않지만 조회를 제외한 실제 삽입, 삭제 단계는 O(1)이기 때문에 이미 올바른 노드에 접근해 있는 시나리오에서 효과적으로 사용할 수 있다.
-
1,000개의 이메일 리스트를 검토해서 유효하지 않은 형식의 이메일을 삭제한다고 할때 배열의 경우 리스트를 조회하는데 1,000단계, 만약 유효하지 않은 주소가 100개일때 삭제할 때 천개를 시프트해야 할 수 있으니 삭제에 추가로 약 100,000단계가 걸린다.
-
연결 리스트는 1,000단계의 읽기 단계와 100개의 삭제 단계 딱 1,100단계만 걸린다.
-
-
이중 연결 리스트
class Node attr_accessor :data, :next_node, :previous_node def initialize(data) @data = data end end class DoublyLinkedList attr_accessor :first_node, :last_node def initialize(first_node=nil, last_node=nil) @first_node = first_node @last_node = last_node end end-
이중 연결 리스트(doubly linked list)는 노드 하나에 앞 노드의 링크와 다음 노드의 링크를 가지고 있는 연결 리스트로 첫 번째 노드외에 마지막 노드도 항상 기록되는 자료구조이다.
-
삽입
//이중 연결 리스트의 끝에 노드를 삽입하는 합수 def insert_at_end(value) new_node = Node.new(value) if !first_node @first_node = new_node @last_node = new_node else new_node.previous_node = @last_node @last_node.next_node = new_node @last_node = new_node end end -
연결 리스트는 앞으로만 이동할 수 있지만 이중 연결 리스트는 노드에 이전 노드와 다음 노드의 링크가 저장되어 있기 때문에 앞과 뒤 모두 이동이 가능하다.
-
-
이중 연결 리스트 기반 큐
class Queue attr_accessor :queue def initialize @data = DoublyLinkedList.new end def enqueue(element) @data.insert_at_end(element) end def dequeue removed_node = @data.remove_from_front return removed_node.data end def read return nil unless @data.first_node return @data.first_node.data end end- 이중 연결 리스트는 앞과 끝 모두에 바로 접근할 수 있고 양 끝에 데이터를 바로 삽입/삭제 할 수 있기 때문에 큐를 위한 완벽한 자료구조이다.
- 배열은 끝에 삽입하는 데 O(1) 앞에서 삭제하는데 O(N)의 단계가 걸리지만 이중 연결 리스트는 삽입/삭제 모두 O(1)의 시간복잡도를 가진다.
15장 이진 탐색 트리로 속도 향상
-
트리
- 트리는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결하는 자료구조로, 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다.
- 트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)이라고 한다.
- 트리의 프로퍼티(property)는 균형 잡힌 정도를 말하며, 모든 노드에서 하위 트리의 노드 개수가 같은 그 트리는 균형 트리이고 그렇지 않는 트리는 불균형 트리이다.
-
이진 탐색 트리(binary search tree)
- 이진 트리는 각 노드에 자식이 0개나 1개, 2개인 트리이고 이진 탐색 트리는 이 규칙에 다음 규칙이 추가된 트리이다.
- 각 노드의 자식은 최대 왼쪽에 하나 오른쪽에 하나이다.
- 한 노드의 왼쪽 자손은 그 노드보다 작은 값만 포함할 수 있다. 마찬가지로 오른쪽 자손은 그 노드보다 큰 값만 포함할 수 있다.
- 이진 트리는 각 노드에 자식이 0개나 1개, 2개인 트리이고 이진 탐색 트리는 이 규칙에 다음 규칙이 추가된 트리이다.
-
검색
- 다음은 이진 탐색 트리를 검색하는 알고리즘이다.
- 노드를 현재 노드로 지정한다.(알고리즘을 시작할 때는 루트 노드가 첫 번째 현재 노드이다.)
- 현재 노드의 값을 확인한다.
- 찾고 있는 값이면 검색을 멈춘다.
- 찾고 있는 값이 현재 노드보다 작으면 왼쪽 하위 트리를 검색한다.
- 찾고 있는 값이 현재 노드보다 크면 오른쪽 하위 트리를 검색한다.
- 찾고 있는 값을 찾았거나 트리 바닥에 닿을 때까지 1~5 단계를 반복한다.
- 각 단계마다 남은 값 중 반을 제거하므로 이진 탐색 트리의 검색 알고리즘은 O(logN)이다.
- 다음은 이진 탐색 트리를 검색하는 알고리즘이다.
-
삽입
- 이진 탐색 트리에서 삽입은 logN의 검색 + 삽입 1 단계로 (logN) + 1 => O(logN)의 시간복잡도를 가진다.
- 정렬된 배열에서는 검색에 동일한 시간복잡도인 O(logN)이 걸리지만 삽입에는 데이터를 오른쪽으로 시프트 해야 하기 때문에 O(N)이 걸리므로 이진 탐색 트리가 더 효율적이다.
-
삽입 순서
- 무작위로 정렬된 데이터로 트리를 생성해야 대개 균형 잡힌 트리가 생성되고 균형잡힌 트리일 때만 검색에 O(logN)이 걸린다.
- 1,2,3,4,5 의 순서대로 트리를 생성할때 오른쪽 자식의 노드들이 이어져 있는 불균형 트리가 생성되고 검색에 O(N)의 단계가 걸린다.
//부트캠프에서 구현한 이진 탐색 트리 구현 class
class BinarySearchTree {
//BST의 constructor를 구현합니다.
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
// tree에 value를 추가합니다.
insert(value) {
// 인자의 value가 this.value보다 작을 경우, 왼쪽 노드에서 진행합니다.
if (value < this.value) {
// this.left에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
if (this.left === null) {
this.left = new BinarySearchTree(value);
}
// this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
else {
this.left.insert(value);
}
}
// 인자의 value가 this.value보다 클 경우, 오른쪽 노드에서 진행합니다.
else if (value > this.value) {
// this.right에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
if (this.right === null) {
this.right = new BinarySearchTree(value);
}
// this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
else {
this.right.insert(value);
}
} else {
// 이미 value값을 포함하고 있습니다.
}
}
// tree의 value값을 탐색합니다.
contains(value) {
// 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
if (value === this.value) {
return true;
}
// 찾는 value값이 노드의 value 보다 작다면, 왼쪽에서 contains의 재귀를 진행합니다.
if (value < this.value) {
if (this.left !== null && this.left.contains(value)) return true;
else return
}
// 찾는 value값이 노드의 value 보다 크다면, 오른쪽에서 contains의 재귀를 진행합니다.
if (value > this.value) {
if (this.right !== null && this.right.contains(value)) return true;
else return false
}
}
//tree를 전위 순회 합니다.
preorder(callback) {
callback(this.value);
if (this.left !== null) {
this.left.preorder(callback);
}
if (this.right !== null) {
this.right.preorder(callback);
}
}
// tree를 중위 순회 합니다
inorder(callback) {
if (this.left !== null) {
this.left.inorder(callback);
}
callback(this.value);
if (this.right !== null) {
this.right.inorder(callback);
}
}
//tree를 후위 순회 합니다
postorder(callback) {
if (this.left !== null) {
this.left.postorder(callback);
}
if (this.right !== null) {
this.right.postorder(callback);
}
callback(this.value);
}
}-
삭제
- 이진 탐색 트리의 삭제 알고리즘은 다음과 같다.
- 삭제할 노드에 자식이 없으면 그냥 삭제한다.
- 삭제할 노드에 자식이 하나면 삭제된 노드를 후속자 노드로 대체한다. 후속자 노드란 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드이다.
- 후속자 노드를 찾으려면 삭제된 값의 오른쪽 자식을 방문해서 그 자식의 왼쪽 자식을 따라 계속해서 방문하며 더 이상 왼쪽 자식이 없을 때까지 내려간다. 바닥 값이 후속자 노드이다.
- 만약 후속자 노드에 오른쪽 자식이 있으면 후속자 노드를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.
def delete(valueToDelete, node): if node is None: return None elif valueToDelete < node.value: node.leftChild = delete(valueToDelete, node.leftChild) return node elif valueToDelete > node.value: node.rightChild = delete(valueToDelete, node.rightChild) return node elif valueToDelete == node.value: if node.leftChild is None: return node.rightChild elif node.rightChild is None: return node.leftChild else: node.rightChild = lift(node.rightChild, node) return node def lift(node, nodeToDelete): if node.leftChild: node.leftChild = lift(node.leftChild, nodeToDelete) return node else: nodeToDelete.value = node.value return node.rightChild- lift 함수 실행 순서
- 후속자 노드를 찾는다.
- nodeToDelete의 값을 후속자 노드의 값으로 덮어쓴다.
- 실제 후속자 노드 객체를 삭제하기 위해 함수는 원래 후속자 노드의 오른쪽 자식을 후속자 노드 부모의 왼쪽 자식으로 넣는다.
- 재귀가 모두 끝나면 처음에 전달받은 원래 rightChild를 반환하거나 혹은 (원래 rightChild에 왼쪽 자식이 없어) 원래 rightChild가 후속자 노드가 됐으면 None을 반환한다.
- 이진 탐색 트리의 삭제 알고리즘은 다음과 같다.
-
이진 탐색 트리 삭제의 효율성
- 트리 삭제는 검색 한번과 연결이 끊긴 자식을 처리하는 단계가 추가로 필요하기 때문에 O(logN)의 시간 복잡도를 가진다.
-
이진 탐색 트리 순회
- 중위 순회 :
- 노드의 왼쪽 자식에 함수를 재귀적으로 호출한다. 왼쪽 자식이 없는 노드에 닿을 때까지 함수를 계속 호출한다.
- 노드를 방문한다.
- 노드의 오른쪽 자식에 함수를 재귀족으로 호출한다. 오른쪽 자식이 없는 노드에 닿을 때까지 함수를 계속 호출한다.
- 중위 순회 :
16장 힙으로 우선순위 정하기
-
우선순위 큐
- 우선순위 큐는 일반 큐처럼 앞에서만 데이터에 접근하고 삭제하되 데이터를 삽입할 때는 늘 특정 순서대로 정렬시킨다.
- 대표적인 예로 병원 응급실의 중증도 분류체계 관리 애플리케이션이 있다.
- 배열의 끝을 우선순위 큐 앞으로 정해서 구현시 삭제가 O(1), 삽입은 새 데이터를 넣을 자리를 알아내고 쉬프트하는 과정이 필요하므로 O(N)의 단계가 걸린다.
-
힙
- 힙은 다음의 조건을 따르는 이진 트리이다.
- 각 노드의 값은 그 노드의 모든 자손 노드의 값보다 커야한다.(최대 힙)
- 완전 트리여야 한다.
- 각 노드가 자손보다 작은 값을 갖도록 구현하는 것이 최소 힙이며 최대 힙과 조건만 반대일 뿐 모든 면에서 동일하다.
- 완전트리는 빠진 노드 없이 노드가 완전히 채워진 트리이다.
- 힙은 다음의 조건을 따르는 이진 트리이다.
-
힙 속성
- 이진 탐색 트리라면 찾으려는 값이 왼쪽 자손에 있는지 오른쪽 자손에 있는지 알 수 있지만 힙은 자손이 조상보다 클 수 없다는 순서만 있기 때문에 약한 정렬이다.
- 힙은 루트 노드가 항상 최댓값이기 때문에 우선순위 큐를 구현하는 훌륭한 도구이다.
-
힙 삽입
-
힙에 새 값을 삽입하려면 다음 알고리즘을 수행한다.
- 새 값을 포함하는 노드를 생성하고 바닥 레벨의 가장 오른쪽 노드 옆에 삽입한다.
- 이어서 새로 삽입한 노드와 그 부모 노드를 비교한다.
- 새 노드가 부모 노드보다 크면 새 노드와 부모 노드를 스왑한다.
- 새 노드보다 큰 부모 노드를 만날 때까지 3단계를 반복하며 새 노드를 힙 위로 올린다.
//1차원 배열로 구현한 최대 힙 구현 함수 //루트 노드가 0번째 인덱스 값, 다음 자식 노드가 1,2, 그다음 자식이 3,4,5,6... function swap(idx1, idx2, arr) { [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]; } function getParentIdx(idx) { return Math.floor((idx - 1) / 2); } function insert(heap, item) { heap.push(item); let childId = heap.length - 1 let parentId = getParentIdx(childId) while(parentId >= 0 && heap[childId] > heap[parentId]) { swap(childId, parentId, heap); childId = parentId; parentId = getParentIdx(childId) } return heap } const binaryHeap = function (arr) { return arr.reduce((heap, item) => { return insert(heap, item); }, []); }; -
새 노드를 위로 올리는 과정을 트리클링(trickling)이라고 표현하며 약 log(N)개의 줄을 갖는 트리 꼭대기까지 트리클링해야 하므로 O(logN)의 시간 복잡도를 가진다.
-
-
힙 삭제
- 힙에서 값을 삭제하려면 큐의 동작 방식처럼 가장 높은 우선순위를 갖는 루트 노드만 삭제할 수 있으며, 다음의 알고리즘을 따른다.
- 마지막 노드를 루트 노드 자리로 옯긴다. 원래 루트 노드는 삭제된다.
- 루트 노드를 적절한 자리까지 아래로 트리클링한다.
1) 트리클 노드의 두 자식을 확인해 어느 쪽이 더 큰지 본다.
2) 트리클 노드가 두 자식 노드 중 큰 노드보다 작으면 큰 노드와 트리클 노드를 스왑한다.
3) 트리클 노드에 그 노드보다 큰 자식이 없을 때까지 1, 2단계를 반복한다.
- 힙에서 삭제하려면 루트부터 시작해 log(N)개 레벨을 거쳐 노드를 트리클링해야 하므로 삽입과 마찬가지로 시간 복잡도가 O(logN)이다.
- 힙에서 값을 삭제하려면 큐의 동작 방식처럼 가장 높은 우선순위를 갖는 루트 노드만 삭제할 수 있으며, 다음의 알고리즘을 따른다.
-
힙 대 정렬된 배열
정렬된 배열 힙 삽입 O(N) O(logN) 삭제 O(1) O(logN) 정렬된 배열은 삽입에 있어 힙보다 느리지만 삭제는 힙보다 빠르다.
정렬된 배열 힙 삽입 느림 매우 빠름 삭제 엄청나게 빠름 매우 빠름 그러나 O(N)의 시간복잡도가 상대적으로 느리기 때문에 삽입, 삭제가 모두 빠른 힙을 사용하는 것이 효율적이다.
-
마지막 노드 문제
- 힙의 완전성(completeness)이 중요한 이유는 노드가 불균형하게 되면 O(logN) 안에 가능했던 연산이 최악의 경우에 순회에 O(N)이 걸리기 때문이다.
마치며
이번 파트를 통해 연결 리스트와 이진 탐색트리, 힙의 구조와 연산의 효율성에 대해서 알아보고 어떤 장단점을 가지고 있는지를 알 수 있었다. 연결 리스트는 처음 배우는 자료구조였고 다른 자료 구조는 함수로 구현한 적이 있지만 알고리즘의 효율성에 대해서는 책을 통해서 처음 알게 되었다. 실제 현업에서 활용할때 삽입이나 삭제 중 어떤 연산이 자주 일어나는지 또는 정렬이 중요한 기능인지 등을 생각해서 적절한 자료구조를 선택해야 한다고 느꼈다.
개발자로 성장하기