RBT
-
[알고리즘] 레드-블랙트리(Red-BlackTree) -Insert프로그래밍/알고리즘 2019. 4. 8. 23:20
이진탐색트리(BST)를 기반으로 구성된 자료구조입니다. BST의 설명은 여기에 있습니다. 따라서 BST의 설명은 본 게시물에서는 하지 않습니다. 개념설명 : 우선 이진탐색트리를 잠깐 봅시다. 이진탐색트리는 Search, Insert, Delete 가 가능한 이진트리였습니다. 이때, 평균 시간복잡도는 O(log n) 이였죠. 하ㄴ지만 이진트리가 극단적으로 편향됬을때시간복잡도는 O(N) 이 됩니다. 이건 이진트리의 깊이(h) 많큼 탐색을 한다는 의미입니다. 이러한 문제들을 해결하기 위해 나온 것이 바로 레드-블랙트리(Red-BlackTree) 입니다. 다른 말로 Balanced Binary Search Tree 라고도 합니다. 이유는 이진탐색트리의 깊이를 항상 log N 으로 유지시켜주기 때문입니다. 따라서..