본문 바로가기

Computer Science/자료구조 (Data Structure)

 (14)
Red-Black Tree (RB 트리) | 삭제 연산 RB 트리의 삽입 연산에 이어 삭제 연산 ! RB트리의 연산을 이해할 때는 색깔이라는 속성이 특정 노드에 귀속적인 게 아니라, 자유롭게 날아갈 수도 있는 속성임을 이해하는게 중요하다. 색깔은 말 그대로 노드의 구조를 파악하고 컨트롤하기 위해 붙여놓은 인덱스같은 거다. 색깔을 붙인 것도 우리 마음대로였고, 색깔을 바꾸거나 하는 것도 RB트리의 속성 유지에 도움이 된다면 아무렇게나 해도 된다. 그저 약속일 뿐이다. 우리가 배우는 방법론은 그 중 효율적인 방법일 뿐이다. 바로 들어가기에 앞서 RB 트리의 5가지 속성을 다시 복기하자: 모든 노드의 색은 red 또는 black 이다. 루트 노드는 black이다. nil 노드는 black이다. nil 노드: null과 통하는 의미라고 생각하면 된다. 특정 노드가 ..
BST 기반 자료구조들의 우선순위 라는 논문 결과 (2004년 스탠퍼드대 연구) (논문 링크: https://web.stanford.edu/~blp/papers/libavl.pdf) Abstract 1. 논문 작성 당시, BST(이진 검색 트리) 기반 자료구조의 선택을 돕는 경험적 연구가 부족함 2. 현실세계의 시나리오를 가정한 후, 해당 환경에서 20가지의 BST 변형 성능을 측정하고 비교함 3. 결론 입력이 무작위 순서로 제공되는게 확실할 경우, unbalanced한 일반적인 BST가 우수 입력이 무작위 순서로 제공되고 가끔 정렬된 순서가 있는 경우 RB 트리가 우수 정렬된 순서로 삽입 후 무작위 접근이 필요할 때는 AVL 트리가 우수 삽입 후 순차적 또는 군집된(clustered) 접근에는 splay 트리가 우수 응용 사례를 위주..
Red-Black Tree (RB 트리) | 기본 개념, 삽입 연산 RB 트리를 C 프로그래밍으로 구현한 과제 링크: https://github.com/Vacayy/Red-Black-Tree GitHub - Vacayy/Red-Black-Tree: C 프로그래밍으로 Red-Black Tree를 구현하는 과제입니다. C 프로그래밍으로 Red-Black Tree를 구현하는 과제입니다. Contribute to Vacayy/Red-Black-Tree development by creating an account on GitHub. github.com 절대 완벽한 코드는 아니지만 만약 이 포스팅을 보는 분 중에 RB 트리 내부 구조가 궁금하신 분은 들어가보시면 참고가 될 듯! C 언어를 처음 다뤄봤는데, 복잡한 자료구조를 직접 구현해보면서 C언어에도 익숙해질 수 있었던 과제였다..
자료구조 | 힙(Heap), 우선순위 큐(Priority Queue) 우선순위 큐는 대표적으로 다익스트라 알고리즘에서 사용된다. (또 A* 알고리즘, 허프만 코딩 알고리즘 등에서도 쓰인다고 한다) 큐, 데큐가 선형 자료구조인 것과 달리, 우선순위 큐는 주로 힙(Heap)으로 구현되는 경우가 많기 때문에 비선형으로 분류된다. 우선순위 큐를 구현하는데 필요한 힙(Heap)이라는 자료구조가 무엇인지 알아보고, 우선순위 큐에 대해서 알아보자. 힙(Heap) Heap은 완전 이진 트리의 일종으로, 1) 최소 힙 또는 2) 최대 힙으로 나뉜다. 힙 속성(Heap Property) 최소 힙(Min-Heap): 각 노드의 값이 그 자식 노드의 값보다 작거나 같음 (루트 노드가 최소값) 최대 힙(Max-Heap): 각 노드의 값이 그 자식 노드의 값보다 크거나 같음 (루트 노드가 최대값)..
자료구조 | 유니온-파인드(Union-Find) Union-Find Union-Find는 Kruskal 알고리즘을 구현하기 위해 핵심적으로 알아야 할 자료구조이다. Disjoint Set(서로소 집합 자료구조)을 표현할 때 사용하는 자료구조이다. 서로소 집합은 공통 요소가 하나도 없는, 즉 교집합이 전혀 없는 서로 다른 부분집합들을 의미한다. 그리고 Union-Find는 이 Disjoint-Set을 구성하고 각 요소에 대한 조작, 검색을 수행하도록 설계된 개념이다. 구현 해당 자료구조는 언어 자체에 내장되어 있거나 그렇진 않고, 일반적으로 딕셔너리(트리 구조)로 구현한다. Key = 노드 Value = 해당 노드의 부모 노드 (* 루트 노드는 부모 노드로 자기 자신을 가리킨다.) 트리 구조의 부모-자식 관계를 이용하여 어떠한 부분집합의 개별 요소들을..
자료구조 | 신장 트리(ST), 최소 신장 트리(MST) 그래프와 트리의 개념을 배우고나면, 그 다음으로 딱 봐도 '실생활에서도 자주 응용되겠는데?' 싶은 개념이 등장한다. 바로 '신장 트리'와 여기서 파생되는 '최소 신장 트리' 개념이다. 신장 트리(Spanning Tree, ST) 신장 트리의 정의 그래프는 V(정점)와 E(간선)의 집합이다. 그리고 어떤 한 그래프에는 수많은 조합의 하위 그래프가 존재할 것이다. 이중에서 특별한 조건을 만족한 하위 그래프를 '신장 트리'라고 부른다. [신장 트리의 조건] 1. 주어진 연결 그래프의 모든 정점을 지나야 한다. 2. 동시에 트리여야 한다. 1) 사이클을 포함하지 않아야 한다. 2) V = E+1 이어야 한다. (V: 정점의 수, E: 간선의 수) 신장 트리(Spanning Tree)에서 '신장'은 원래 이름인 ..
자료구조 | 그래프 기초(Graph) 그래프를 사용하는 이유 현실의 객체들은 언제나 다른 객체와의 연관성을 갖는다. 예를 들면, 사람과 사람은 혈연 학연 지연 등 다양한 기준으로 서로의 관계를 나타낼 수 있고, 도시와 도시는 위치와 거리를 기준으로 연결할 수 있다. 이처럼 그래프는 객체들 간의 이진 관계를 모델링하는데 사용되는 구조이다. [이진 관계 (Binary Relations)] 두 개의 요소 사이에 성립하는 관계. 집합 A와 집합 B에 대해, 이진 관계는 A의 요소와 B의 요소 사이에 존재하는 관계를 나타낸다. 이 관계는 주로 집합 A *B의 부분집합으로 표현되며, 이 부분집합의 각 원소는 순서쌍 (a,b)로 나타낼 수 있다. 예를 들어, 집합 A = {1,2,3}와 집합 B = {a,b}가 있다고 하면, 이진 관계의 예는 다음과 같..
자료구조 | 이진 탐색 트리(Binary Search Tree, BST) 이진 탐색 트리(Binary Search Tree, BST) 이진 탐색 트리는 이진 트리의 한 종류로, 효율적인 탐색이 가능하도록 노드를 배치한 형태이다. 1. 기본 개념 이진 탐색 트리의 모든 노드에는 다음 두 가지 조건이 재귀적으로 적용된다. 왼쪽 서브트리의 모든 노드의 Key는 자신의 Key보다 작고, 오른쪽 서브트리의 모든 노드의 Key는 자신의 Key보다 크다. 위 이미지를 보면, 어떠한 노드이든 자기자신을 기준으로 반을 나누면 왼쪽은 자신보다 Key 값이 작고, 오른쪽은 자신보다 Key 값이 크다. BST의 특성 이진 탐색 트리는 다음과 같은 특성이 있다. 데이터의 정렬된 순서를 유지하는 속성을 갖는다. BST의 최소값 -> 트리의 가장 왼쪽 값 BST의 최대값 -> 트리의 가장 오른쪽 값 ..

티스토리툴바