프로그래밍 기초
-
KDB 트리 알고리즘프로그래밍 기초/알고리즘 2021. 11. 30. 14:07
KDB 트리 B 트리를 다차원 검색 트리로 확장한 트리 자료구조이다. KDB 트리는 노드의 키를 통해 분기하는 게 아니라 전체 영역을 쪼개가며 진행하게 된다. KDB 트리에는 다음의 두 종류의 노드가 존재한다. 영역 노드 트리의 차원에 따라 노드가 가지는 공간을 표현하는 노드 키 노드 실제 키와 소속된 페이지 번호를 가지는 노드 이때, k 차원의 키를 사용하는 영역 노드는 다음과 같이 표현된다. (, , ... , ) ※ KDB 트리의 모든 내부 노드는 영역 노드이며, 모든 리프 노드는 키 노드이다. KD 트리에서의 검색 KD 트리의 검색은 다음의 순서를 따른다. 루트 노드에서부터 검색하려는 키가 포함된 영역을 가지는 영역 노드를 따라 진행한다. 리프 노드에 도달한 경우 리프 노드에 검색하려는 키가 존재..
-
KD 트리 알고리즘프로그래밍 기초/알고리즘 2021. 11. 18. 18:51
KD 트리 이진 검색 트리를 다차원 검색 트리로 확장한 트리 자료구조이다. KD 트리는 같은 레벨의 노드는 동등한 위치의 필드를 사용하여 분기를 진행하며 k 개의 필드를 가지는 KD 트리에서 레벨 k에 도달한 경우 다시 0 번째 필드를 사용하여 분기를 진행한다. ※ 다차원 검색 트리는 노드의 키가 하나의 필드가 아닌 여러 개의 필드로 이루어진 검색 트리를 말한다. KD 트리에서의 검색 기본적으로 이진 검색 트리와 동일한 방식으로 탐색을 진행하나 KD 트리는 각 레벨 별로 다른 필드를 사용하여 검색을 진행하는 점이 다르다. 레벨 0 에서는 첫 번째 필드를 사용하여 분기하고 레벨 1에서는 두 번째 필드를 사용하여 분기를 진행한다. 이렇게 진행하다 레벨 k 에서는 다시 첫 번째 필드를 사용하는 방식으로 검색을..
-
B 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 11. 11. 19:58
B 트리 이진 검색 트리를 기반으로 노드에 Balance Factor(이후 BF)를 추가하여 BF의 상태에 따라 트리의 균형을 유지한다. B 트리 개요 검색 트리가 방대하면 검색 트리를 메모리에 모두 올려두고 사용할 수 없게 되어 검색 트리가 디스크에 있는 상태에서 작업을 해야 한다. 이런 경우에 CPU 작업 효율성보다 디스크 접근 횟수가 효율을 좌우하게 된다. B 트리는 디스크 환경에서 사용하기 적합한 외부 다진 검색 트리로 B 트리의 한 노드에는 최대 k개까지의 키가 크기 순으로 저장되어 있다. ※ 검색 트리가 디스크에 있는 상태로 사용되면 이를 외부 검색 트리라고 한다. B 트리에 k개의 키가 존재하는 경우 k + 1 개의 자식을 가지게 된다. 이때, 주어진 키를 key 0 ~ key k - 1로 ..
-
이진 검색 트리 출력 함수 구현프로그래밍 기초/알고리즘 2021. 9. 21. 13:55
이진 검색 트리 출력 이진 검색 트리를 화면에 출력하는 함수를 구현한다. 노드 출력 알고리즘 노드를 동일한 간격으로 출력하기 위해 다음의 제약 사항이 존재해야 한다. 모든 노드는 동일한 크기를 갖는다. 최대 깊이의 노드 간의 간격은 노드의 크기와 같다. 최대 깊이에 빈 노드가 없다고 가정하여 최대 크기를 구한다. 구한 최대 크기를 모든 깊이에 사용하여 출력한다. 깊이가 n 일 때, 노드의 개수 및 공백의 개수는 다음과 같다. 노드의 수 2ⁿ - ¹ 개 공백의 수 n + 1 개 따라서 최대 깊이에서 출력에 필요한 크기는 다음의 식을 만족한다. 출력에 필요한 크기 = (공백의 수 + 노드의 수) * 노드의 크기 ※ 깊이에 따라 노드의 수가 달라지므로 공백의 크기는 출력에 필요한 크기 - (노드의 수 * 노드..
-
AVL 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 9. 20. 17:45
AVL 트리 이진 검색 트리를 기반으로 노드에 Balance Factor(이후 BF)를 추가하여 BF의 상태에 따라 트리의 균형을 유지한다. ※ AVL 트리는 노드의 수가 n일 때 최대 깊이가 Ο(logn)이 되게 된다. AVL 트리의 개념 기본적으로 삽입과 삭제는 이진 검색 트리의 알고리즘을 그대로 따르며 이후 BF에 따라 보정하는 작업을 진행하여 트리의 균형을 유지한다. BF는 노드의 왼쪽 서브 트리의 깊이와 오른쪽 서브 트리의 깊이의 차이이다. 정상 상태일 때 BF의 범위는 [-1, 1]이 되게 되며 노드의 삽입 혹은 삭제를 통해 이 범위를 넘게 되면 균형이 무너진 것으로 판단한다. AVL 트리의 회전 알고리즘 BF가 무너진 노드를 x, x의 자식을 c, c의 자식을 c²라 하면 회전이 필요한 경우..
-
레드 블랙 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 9. 19. 17:03
레드 블랙 트리 이진 검색 트리를 기반으로 노드에 색상을 추가하여 색상 규칙을 기준으로 트리의 균형을 유지한다. ※ 레드 블랙 트리는 노드의 수가 n일 때 최대 깊이가 Ο(logn)이 되게 된다. 레드 블랙 트리의 삽입 알고리즘 레드 블랙 트리의 삽입에서는 먼저 삽입하는 노드의 색상을 레드로 간주하고 삽입을 진행하며 삽입한 노드를 x, 부모 노드를 p, 형제 노드를 s라고 할 때 발생 가능한 모든 경우는 다음과 같다. p가 블랙인 경우 삽입 연산을 종료한다. s가 레드인 경우 p와 s를 블랙으로 바꾸고 p²을 레드로 바꾼다. 만약 p²가 루트면 p²를 블랙으로 바꾸고 종료한다. 연산 결과 p²이 레드이면 p²을 문제 발생 노드로 두고 재귀적으로 처리한다. s가 블랙인 경우 삽입된 위치에 따른 추가 연산을..
-
균형 잡힌 이진 검색 트리 개요프로그래밍 기초/알고리즘 2021. 8. 15. 17:59
균형 잡힌 이진 검색 트리 개요 이진 검색 트리의 문제점 이진 검색 트리의 경우 저장과 검색에 평균 Θ(logn) 시간이 소요되지만 운이 좋지 않아 트리의 균형이 깨지게 된 경우엔 Θ(n)에 가까운 시간이 소요되게 된다. 이러한 문제를 극복하기 위해 이진 검색 트리를 구성할 때 균형을 유지할 수 있도록 해야 하며 대표적으로 레드 블랙 트리와 AVL 트리가 존재한다. 이진 검색 트리의 균형 유지를 위한 각 트리의 특성은 다음과 같다. AVL 트리 높이 균형 성질을 만족한다. 높이 균형 성질 트리 내부의 모든 노드는 자식과의 높이 차이가 1 이하가 되어야 한다. 레드 블랙 트리 노드에 색상 정보를 추가하여 다음의 특성이 만족되도록 해야 한다. 루트는 블랙이다. 모든 리프(NIL)는 블랙이다. 노드가 레드이면..
-
이진 검색 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 8. 10. 12:06
이진 검색 트리 이진 검색 트리의 특성은 다음과 같다. 각 노드는 서로 다른 키 값을 하나씩 갖는다. 최상위 레벨에 루트가 있으며, 각 노드는 최대 두 개의 자식 노드를 가진다. 노드의 왼쪽 서브 트리의 모든 노드의 값은 항상 노드의 값보다 작다. 노드의 오른쪽 서브 트리의 모든 노드의 값은 항상 노드의 값보다 크다. 이진 검색 트리에서의 검색 특정 키를 가진 노드를 검색하는 방법은 다음과 같다. 이진 검색 트리의 루트 노드에서부터 비교를 시작한다. 주어진 키와 노드의 키를 비교하여 주어진 키가 노드의 키가 같으면 노드를 반환한다. 주어진 키가 노드의 키보다 작으면 왼쪽 서브 트리로 이동하여 다시 비교한다. 주어진 키가 노드의 키보다 크면 오른쪽 서브 트리로 이동하여 다시 비교한다. 위 과정을 노드를 찾..