CS/자료구조

레드 블랙 트리(Red-Black Tree)

Red-Black Tree란? Red-Black 트리는 이진 탐색 트리(BST)의 한 종류입니다. BST는 루트 노드의 값이 왼쪽 노드 보다는 크고 오른쪽 노드 보다는 작은 이진 트리입니다. Red-Black트리와 BST와의 가장 큰 차이는 스스로 균형을 잡는 다는 점입니다. BST의 경우 만약 값의 삽입이 2 - 3 - 5 - 7 과 같이 오름차순으로 삽입이 된다면 아래 그림과 같이 최악의 경우 O(n)의 탐색 시간복잡도를 지니게 됩니다. Red-Black 트리는다음과 같은 문제를 해결하여 탐색 시 최악의 경우에도 O(logN)의 시간복잡도를 지닙니다. Red-Black Tree의 속성 Red-Black 트리는 총 5가지의 속성을 지니고 있습니다. 하나씩 살펴보도록 하겠습니다. 1. 모든 노드는 red..

이진 탐색 트리(BST)에 대하여

이진 탐색 트리란? 이진트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리를 뜻합니다. 이진탐색 트리(Binary Search Tree)는 이진 탐색(Binary Search)와 연결 리스트(Linked list)를 결합한 이진트리입니다. 이진 탐색은 시간복잡도가 O(logN)이지만 정렬된 상태를 유지해야 함으로 삽입이나 삭제가 불가능합니다. 연결 리스트는 삽입이나 삭제시 O(1)의 상수 시간복잡도로 처리 가능하지만, 탐색 시간복잡도가 O(N)입니다. 정리하자면 이 둘의 장점을 챙긴 자료구조가 이진 탐색트리입니다. 이진 탐색 트리의 특징 - 모든 왼쪽 자식의 노드의 값이 부모 노드의 값보다 작습니다. - 모든 오른쪽 자식의 노드의 값이 부모 노드의 값보다 큽니다. - 각 노드들은 서로 유일한 값을 가..

Array와 List의 차이는?

배열(Array)과 리스트(List)는 모두 선형 자료구조입니다. 선형 자료구조란 원소들을 순서대로 나열한 집합을 뜻합니다. 지금 부터 각각에 대해서 특징과 차이가 무엇인지 살펴보도록 하겠습니다! 배열 (Array) 배열이란 같은 성질을 같은 항목들의 집합을 뜻합니다. 아래 그림과 같이 모든 요소들이 정수(int)를 자료형으로 갖고 있는 것을 확인할 수 있습니다. 중간에 문자열이나 다른 성질을 갖는 요소들이 들어올 수 없습니다. 또한 메모리 상에 연속적으로 데이터가 저장됩니다. 순차적으로 저장된 데이터를 참조하는데 Index가 사용됩니다. 이러한 배열에는 몇가지 특징들이 있습니다. 차례대로 살펴보도록 하겠습니다. 배열은 고정된 크기를 같습니다. 배열을 사용하기 전에 크기를 미리 지정을 하고 사용하기 때문..

Heap(힙)에 대하여

Heap(힙) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조입니다. 여러 개의 값중에 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조입니다. 힙은 반정렬 상태(느슨한 정렬 상태)를 유지합니다. [ 완전 이진 트리의 의미 ] 완전 이진 트리에서 완전이라는 말의 의미는 마지막 레벨을 제외한 모든 노드가 채워져 있으면서 모든 노드가 왼쪽부터 채워져 있어야 하는 것을 의미합니다. 위 그림에서 완전 이진트리는 마지막 레벨을 제외한 모든 노드가 채워져 있고 왼쪽부터 채워진 형태를 볼 수 있습니다. 만약 마지막 레벨의 노드가 모두 채워져 있으면 이를 포화 이진트리라고 부르게 됩니다. [ 힙의 반정렬(느슨한 정렬) 상태 ] 힙은 어떻게 최댓값 또는 최솟값을 빠르게 찾아낼 수 있을까요? 힙이 ..