본문 바로가기

전체 글669

멀티웨이 탐색 트리 2 : 2-3 트리, 2-3-4 트리, 레드 블랙 트리 개관 트리 구성도 1. 2-3 트리 차수가 2 또는 3인 내부 노드를 갖는 트리를 2-3 트리라고 한다. 이때 차수가 2인 노드를 2-노드, 3인 노드를 3-노드 라고 부른다. 즉, 2-3 트리는 2-노드와 3-노드만으로 구성된 특수한 형태의 B트리이다. 다음 조건을 만족할 때 2-3트리라고 한다. 1) 각각의 내부 노드는 2-노드 이거나 3-노드이다. 2-노드는 한 개의 키값을, 3-노드는 두 개의 키값을 갖는다. 2) lchild, mchild를 각각 2-노드의 좌측 및 중간 자식이라 하고, lkey가 이 노드의 키값이라 하면, 루트가 lchild인 모든 2-3 서브트리 키값은 lkey보다 작고, 루트가 mchild인 모든 2-3 서브트리 키값은 lkey보다 크다. 3) lchild, mchild 및.. 2023. 11. 26.
멀티웨이 탐색 트리 1 - m원 탐색 트리, B 트리, B*트리, B+ 트리 멀티웨이 탐색 트리 개관 이진 탐색 트리를 발전시킨 멀티웨이 탐색 트리에 대해 알아본다. 이것은 기존 이진 탐색 트리의 장점을 활용하면서, 보다 다양한 형태의 자식 노드를 가질 수 있도록 확장한 개념이다. m원 탐색 트리: m개 이하의 가지를 가질 수 있는 확장된 형태의 탐색 트리. 이진 탐색 트리는 사실상 2-way 탐색 트리의 한 형태. 파일 인덱스 구현에 효율적으로 사용 가능하며, 빠른 레코드 참조가 장점. B, B*, B+ 트리: 이들 트리는 서로 다른 조건과 특징을 가지며, 각각의 삽입 및 삭제 방법을 이해하는 것이 중요. B 트리: 루트와 단말 노드를 제외한 모든 노드가 최소 (M/2)개의 서브트리를 가져야 함. 루트는 최소 2개의 서브트리를 보유. 모든 단말 노드는 같은 레벨에 위치. B* .. 2023. 11. 26.
이진 탐색 트리Bs) - Splay, Avl, BB 트리 Bs, Splay Avl, BB 개요 삽입, 삭제 연산을 보다 효과적으로 작업하기 위해 만든 이진 탐색 트리에 대한 정의와 순회 방법에 대해 학습한다. 이진 탐색 트리에서는 각 노드를 식별하기 위해서 별도의 일므을 붙인 '키'라는 용어를 사용한다. 노드의 데이터라고 생각해도 된다. 정해진 노드(vi)를 기준으로 왼쪽 서브트리에 있는 모든 노드는 vi의 키값보다 값이 작아야 하고, 오른쪽 서브트리의 노드들은 vi의 키값보다 값이 커야 한다는 조건을 만족하는 이진 트리를 이진 탐색 트리, 즉 BS 트리라고 한다. 균형 잡힌 트리로 Splay, AVL, BB 트리가 있다. Splay 연산을 적용한 Splay 트리는 최근에 사용한 노드 x를 다음에도 사용할 수 있다는 가정 하에 노드 x를 루트에 .. 2023. 11. 25.
선택 트리, 숲, 이진 트리 개수 선택 트리 1) 개념 선택 트리는 정렬된 여러 데이터 리스트를 효과적으로 병합하는 데 사용되는 트리 구조이다. 이는 합병 정렬 과정에서 중요한 역할을 한다. 예를 들어, 8개의 정렬된 리스트가 있을 때, 이들 중 가장 작은 값을 빠르게 찾아내어 새로운 리스트를 생성하는 과정을 단순화한다. 선택 트리는 이러한 비교 과정의 횟수를 줄이는 데 크게 기여한다. 이 트리는 주로 승자 트리와 패자 트리의 두 가지 형태로 구성된다. 승자 트리는 더 작은 값을 가진 노드가 승자가 되어 상위 노드로 올라가는 완전 이진 트리 구조이다. 이는 각 노드가 두 자식 노드 중 작은 값을 선택하여 상위 노드로 올라가는 토너먼트와 유사한 방식으로 작동한다. 반면, 패자 트리는 루트 노드 위에 최상위 0번 노드를 두어 최종 승자를 저.. 2023. 11. 25.
힙 - 개념, 우선순위 큐, 삭제 삽입 연산 힙 개요 힙은 부분적으로 정렬된 완전 이진 트리이며, 부모 노드와 자식 노드 간의 크기 관계를 통해 정의된다. 이러한 힙의 특성은 두 가지 주요 형태인 최대힙과 최소힙에서 나타난다. 최대힙에서는 부모 노드가 자식 노드보다 크며, 최소힙에서는 그 반대의 관계를 갖는다. 힙은 노드의 삽입 및 삭제 연산 시에 완전 이진 트리의 형태를 유지해야 하며, 이를 위해 노드 간의 관계를 조정한다. *피라미드 모양으로 쌓아올린 더미를 힙이라고 한다. 우선순위 큐 우선순위 큐는 데이터가 우선순위에 따라 처리되는 자료 구조이다. 이 구조에서는 가장 높은 우선순위를 갖는 데이터가 먼저 나오는 것이 특징이다. 일반적인 큐와는 달리, 우선순위에 따라 데이터의 순서가 결정된다. 정의 및 특징: 우선순위 큐는 각 요소가 우선순위를 .. 2023. 11. 24.

티스토리툴바