알고리즘
-
알고리즘...42일지 2021. 8. 29. 12:31
AVL 트리의 회전 레드 블랙 트리의 회전의 경우 자식 노드를 신경 써서 옮겨줘야 했으나 AVL 트리의 회전은 균형이 무너진 경우 진행하게 되므로 자식 노드가 존재하지 않는 상황에 진행된다. 이때, BF가 무너진 노드를 x, x의 자식을 c, c의 자식을 c²라 하면 회전이 필요한 경우는 다음과 같이 구분된다. c가 x의 왼쪽 자식이고, c²가 c의 왼쪽 자식인 경우(LL) x를 오른쪽 회전 c가 x의 오른쪽 자식이고, c²가 c의 오른쪽 자식인 경우(RR) x를 왼쪽 회전 c가 x의 왼쪽 자식이고, c²가 c의 오른쪽 자식인 경우(LR) c를 오른쪽 회전 후 x를 왼쪽 회전 c가 x의 오른쪽 자식이고, c²가 c의 왼쪽 자식인 경우(RL) c를 왼쪽 회전 후 x를 오른쪽 회전 ※ AVL 트리의 회전 명..
-
알고리즘...41일지 2021. 8. 28. 02:54
AVL 트리 기본 개념 이진 검색 트리의 삽입 알고리즘에 따라 삽입을 진행하면 삽입된 노드의 조상 노드들은 균형이 깨지게 된다. 불균형 상태는 각 노드가 가진 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이를 비교하여 높이의 차이가 1보다 커지게 된 경우를 말하며 이때 비교 결과 값을 Balance Factor(이후 BF)라고 한다. 위와 같이 각 노드가 가진 BF의 값이 [-1, 1]의 범위로 존재하는 경우엔 트리의 균형이 잘 잡힌 상태로 본다. 이 상태에서 15를 삽입하고 BF를 확인하면 14의 BF를 보면 -2가 되게 되며 이 경우 문제가 발생한 것으로 판정하게 된다. 더보기 참고문헌 Wikipedia.AVL tree yoongrammer.(2021.04.20).[자료구조] AVL 트리(Tree)
-
알고리즘...40일지 2021. 8. 26. 18:45
레드 블랙 트리 삭제 메서드 구현 RedBlackTree.h #pragma once #include "../Common.h" enum class NodeColor { Red, Black }; /// /// 레드 블랙 트리에 사용할 노드 /// struct RedBlackNode { RedBlackNode() : data{ 0 }, color{ NodeColor::Red }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} RedBlackNode(int data) : data{ data }, color{ NodeColor::Red }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} void Clear(..
-
알고리즘...39일지 2021. 8. 25. 14:57
레드 블랙 트리 삽입 메서드 구현 RedBlackTree.h #pragma once #include "../Common.h" enum class NodeColor { Red, Black }; /// /// 레드 블랙 트리에 사용할 노드 /// struct RedBlackNode { RedBlackNode() : data{ 0 }, color{ NodeColor::Red }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} RedBlackNode(int data) : data{ data }, color{ NodeColor::Red }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} void Clear(..
-
알고리즘...38일지 2021. 8. 24. 21:29
레드 블랙 트리 삽입 메서드 구현 진행 RedBlackTree.h #pragma once #include "../Common.h" enum class NodeColor { Red, Black }; /// /// 레드 블랙 트리에 사용할 노드 /// struct RedBlackNode { RedBlackNode() : data{ 0 }, color{ NodeColor::Red }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} RedBlackNode(int data) : data{ data }, color{ NodeColor::Red }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} void Cle..
-
알고리즘...37일지 2021. 8. 19. 16:04
레드 블랙 트리를 재정렬해야 하는 경우 자식 노드를 x, 부모 노드를 p, 형제 노드를 s, 형제의 왼쪽 자식을 l, 형제의 오른쪽 자식을 r이라고 할 때 다음과 같은 경우들이 존재한다. p가 레드, s는 블랙인 경우 Case 1-1 Case 1-2 Case 1-3 p가 블랙 Case 2-1 Case 2-2 Case 2-3 Case 2-4 ※ Case 1-2와 Case 2-2 그리고 Case 1-3과 Case 2-3은 p의 색상이 처리 방법에 영향을 미치지 않으므로 통합한다. 각각의 경우에 처리하는 방법은 다음과 같다. Case 1-1 p와 s의 색상을 맞바꾼다. Case *-2 p를 중심으로 왼쪽으로 회전시키고, p와 s의 색상을 바꾼 다음 r의 색상을 레드에서 블랙으로 바꾼다. Case *-3 s를 ..
-
알고리즘...36일지 2021. 8. 18. 14:16
레드 블랙 트리에서의 삭제 레드 블랙 트리의 삭제는 기본적으로 이진 검색 트리의 삭제 방법에 따라 삭제한 뒤 색상에 맞게 다시 정렬하는 방식을 사용하게 된다. 자식이 두 개인 경우 오른쪽 자식의 최소 노드의 값과 삭제하려는 노드의 값을 교환한 뒤 최소 노드를 삭제하는 연산을 진행하는데 이때 값의 교환은 레드 블랙 트리의 속성을 바꾸지 않으므로 노드의 색상을 다시 정렬하는 것은 자식이 없거나 하나만 존재하는 경우만 진행한다고 생각해도 된다. 삭제하려는 노드를 m, 자식 노드를 x, 부모 노드를 p, 형제 노드를 s라고 할 때 처할 수 있는 상황은 다음과 같다. m이 레드인 경우 삭제 연산을 종료한다. m이 블랙이지만 x가 레드인 경우 삭제 연산을 종료한다. m이 블랙이고 x도 블랙인 경우 주변 상황에 따라..
-
알고리즘...35일지 2021. 8. 17. 17:01
레드 블랙 트리에서의 삽입 레드 블랙 트리의 삽입에서는 먼저 삽입하는 노드의 색상을 레드로 간주하고 삽입을 진행한다. 이때, 삽입한 노드를 x, 부모 노드를 p, 형제 노드를 s라고 할 때 다음과 같이 경우를 나눠 진행을 하게 된다. p가 블랙인 경우 삽입 연산을 종료한다. s가 레드인 경우 p와 s를 블랙으로 바꾸고 p²을 레드로 바꾼다. 만약 p²가 루트면 p²를 블랙으로 바꾸고 종료한다. 연산 결과 p²이 레드이면 p²을 문제 발생 노드로 두고 재귀적으로 처리한다. s가 블랙인 경우 삽입된 위치에 따른 추가 연산을 진행한다. x가 p의 오른쪽 자식인 경우(Case 2.1) p를 중심으로 왼쪽으로 회전한 뒤 Case 2.2를 진행한다. x가 p의 왼쪽 자식인 경우(Case 2.1) p²을 중심으로 오..