알고리즘
-
균형 잡힌 이진 검색 트리 개요프로그래밍 기초/알고리즘 2021. 8. 15. 17:59
균형 잡힌 이진 검색 트리 개요 이진 검색 트리의 문제점 이진 검색 트리의 경우 저장과 검색에 평균 Θ(logn) 시간이 소요되지만 운이 좋지 않아 트리의 균형이 깨지게 된 경우엔 Θ(n)에 가까운 시간이 소요되게 된다. 이러한 문제를 극복하기 위해 이진 검색 트리를 구성할 때 균형을 유지할 수 있도록 해야 하며 대표적으로 레드 블랙 트리와 AVL 트리가 존재한다. 이진 검색 트리의 균형 유지를 위한 각 트리의 특성은 다음과 같다. AVL 트리 높이 균형 성질을 만족한다. 높이 균형 성질 트리 내부의 모든 노드는 자식과의 높이 차이가 1 이하가 되어야 한다. 레드 블랙 트리 노드에 색상 정보를 추가하여 다음의 특성이 만족되도록 해야 한다. 루트는 블랙이다. 모든 리프(NIL)는 블랙이다. 노드가 레드이면..
-
알고리즘...34일지 2021. 8. 11. 14:21
이진 검색 트리의 문제점 이진 검색 트리의 경우 저장과 검색에 평균 Θ(logn) 시간이 소요되지만 운이 좋지 않아 트리의 균형이 깨지게 된 경우엔 Θ(n)에 가까운 시간이 소요되게 된다. 이러한 문제를 극복하기 위해 이진 검색 트리를 구성할 때 균형을 유지할 수 있도록 해야 하며 대표적으로 레드 블랙 트리와 AVL 트리가 존재한다. 레드 블랙 트리의 특성 레드 블랙 트리는 이진 검색 트리의 균형 유지를 위해 다음의 특성이 만족되도록 트리의 구성을 변경한다. 루트는 블랙이다. 모든 리프(NIL)는 블랙이다. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다. ※ 리프 노드는 NIL이라는 이름의 존재하는 노드로 색상을 ..
-
이진 검색 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 8. 10. 12:06
이진 검색 트리 이진 검색 트리의 특성은 다음과 같다. 각 노드는 서로 다른 키 값을 하나씩 갖는다. 최상위 레벨에 루트가 있으며, 각 노드는 최대 두 개의 자식 노드를 가진다. 노드의 왼쪽 서브 트리의 모든 노드의 값은 항상 노드의 값보다 작다. 노드의 오른쪽 서브 트리의 모든 노드의 값은 항상 노드의 값보다 크다. 이진 검색 트리에서의 검색 특정 키를 가진 노드를 검색하는 방법은 다음과 같다. 이진 검색 트리의 루트 노드에서부터 비교를 시작한다. 주어진 키와 노드의 키를 비교하여 주어진 키가 노드의 키가 같으면 노드를 반환한다. 주어진 키가 노드의 키보다 작으면 왼쪽 서브 트리로 이동하여 다시 비교한다. 주어진 키가 노드의 키보다 크면 오른쪽 서브 트리로 이동하여 다시 비교한다. 위 과정을 노드를 찾..
-
검색 트리 개요프로그래밍 기초/알고리즘 2021. 8. 9. 15:26
검색 트리 저장된 데이터를 빠른 시간에 검색하기 위해 트리를 사용하는 검색 알고리즘이다. 검색 트리의 요소 레코드 여러 개의 필드로 구성되는 개체의 모든 정보가 저장된 구조 ex) 사람의 레코드: 주민 번호, 이름, 집 주소, 직장 주소, 집 전화번호 등이 포함될 수 있다. 필드 레코드의 각 정보를 나타내는 부분 검색 키(또는 키) 다른 레코드와 중복되지 않고 레코드를 대표할 수 있는 필드 검색 트리의 종류 자식의 수에 따른 분류 이진 검색 트리 최대 두 개의 자식 노드를 가지는 트리 다진 검색 트리 세 개 이상의 자식 노드를 가지는 트리 저장되는 장소에 따른 분류 내부 검색 트리 메인 메모리 내에 모든 데이터가 존재하는 트리 외부 검색 트리 디스크에 저장된 상태로 검색을 진행하는 트리 검색 키가 포함하..
-
알고리즘...33일지 2021. 8. 6. 11:43
이진 검색 트리 구현 연결 자료구조를 이용하여 이진 검색 트리를 구현한다. BinarySearchTree.h #pragma once #include "../Common.h" /// /// 이진 검색 트리에 사용할 노드 /// struct BinarySearchNode { BinarySearchNode() : data{ 0 }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} BinarySearchNode(int data) : data{ data }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} void Clear() { data = 0; parent = nullptr; left = nullptr; ..
-
알고리즘...32일지 2021. 8. 5. 10:29
이진 검색 트리에서의 삭제 이진 검색 트리서 노드를 삭제할 때에는 다음과 같이 케이스를 나눠서 진행해야 한다. 삭제할 노드에 자식이 없는 경우 삭제할 노드에 자식이 하나 있는 경우 삭제할 노드에 자식이 둘 있는 경우 - 자식이 없는 경우 해당 노드를 바로 삭제한다. - 자식이 하나 있는 경우 해당 노드를 삭제한 뒤 자식 노드를 삭제한 노드의 위치에 놓아준다. - 자식이 둘 있는 경우 해당 노도를 삭제한 뒤 이진 검색 트리의 서브 트리의 조건을 깨지 않는 자식 노드를 골라 삭제한 노드의 위치에 놓아준다. 이때, 서브 트리의 조건을 깨지 않는 조건은 다음과 같다. 오른쪽 자식의 서브 트리에서 가장 작은 값을 가진 노드 왼쪽 자식의 서브 트리에서 가장 큰 값을 가진 노드 ※ 선택된 노드에 자식이 존재하는 경우..
-
알고리즘...31일지 2021. 8. 4. 13:18
이진 검색 트리에서의 삽입 이진 검색 트리에 노드를 삽입하는 방법은 다음과 같다. 삽입하려는 값이 이진 검색 트리에 존재하는지 확인하기 위해 검색을 진행한다. 값이 이미 존재하는 경우 종료한다. 값이 존재하지 않아 말단 노드에 도달한 경우 해당 노드에 삽입하려는 값을 가진 노드를 추가한 뒤 종료한다. 이진 검색 트리에서의 삽입 알고리즘 TreeInsert(t, x) { if (t = NIL) then { r = NEW_NODE; key[r] ← x; left[r] ← NIL; right[r] ← NIL; return r; } if (x < key[t]) then { left[t] ← TreeInsert(left[t], x); return t; } else { right[t] ← TreeInsert(rig..
-
알고리즘...30일지 2021. 8. 3. 14:48
이진 검색 트리에서의 검색 특정 키를 가진 노드를 검색하는 방법은 다음과 같다. 이진 검색 트리의 루트 노드에서부터 비교를 시작한다. 주어진 키와 노드의 키를 비교하여 주어진 키가 노드의 키가 같으면 노드를 반환한다. 주어진 키가 노드의 키보다 작으면 왼쪽 서브 트리로 이동하여 다시 비교한다. 주어진 키가 노드의 키보다 크면 오른쪽 서브 트리로 이동하여 다시 비교한다. 위 과정을 노드를 찾거나 말단 노드에 도달할 때까지 반복한다. 이진 검색 트리에서의 검색 알고리즘 TreeSearch(t, x) { if (t = NIL or key[t] = x) then return t; if (x < key[t]) then { return TreeSearch(left[t], x); } else { return Tree..