: 이진탐색트리(Binary Search Tree)
이진 탐색 트리에는 자신의 왼쪽 서브 트리에는 현재 노드보다 key값이 작은 것, 오른쪽 서브 트리에는 현재 노드보다 key값이 큰 것, 을 배치해 탐색이 가능. 이진 탐색 트리에서 중위순회를 하게되면, 오름차순으로 정렬된 순서로 key값을 얻을 수 있다.
이렇게 되어 있을때, 중위순회란
7->3->8->1->9->4->10->0->11->5->2->6
이런 순서로 참조하는 것을 말하고, 왼쪽에는 현재보다 key값이 작은 원소,
오른쪽에는 현재보다 key값이 큰 원소가 위치하기에
오름차순으로 정렬되게 된다.
그래서 탐색의 시간 복잡도는 O(h) ( h = 트리의 높이 ) 가 된다.
: 레드 블랙 트리
이 역시도 이진 탐색 트리의 일종이다.
그런고로 동일하게 왼쪽에는 key값이 작은 원소가
오른쪽에는 key값이 큰 원소가 위치하게 된다.
대신 다른 특징이 존재하기에 레드 블랙 트리는 balanced binary search tree가 된다. ( 균형있는 이진 탐색 트리? )
균형이 잡힌 이진 탐색 트리다. -> 레드블랙트리의 높이는 logn에 바운드 된다 -> 레드블랙트리에서 search연산은 O(logn)의 시간복잡도를 가지게 된다.
그래서 O(h) 이지만, h= log n 이기 때문에 O(log n)이 된다.
어떻게 균형을 맞추어 높이를 최적화 시킬 수 있는지 보자.
레드 블랙 트리는 4가지 규칙이 있다.
1. Root Property : 루트노드의 색깔은 검정(Black)이다.
2. External Property : 모든 external node들은 검정(Black)이다.
3. Internal Property : 빨강(Red)노드의 자식은 검정(Black)이다.
== No Double Red(빨간색 노드가 연속으로 나올 수 없다.)
4. Depth Property : 모든 리프노드에서 Black Depth는 같다.
== 리프노드에서 루트노드까지 가는 경로에서 만나는 블랙노드의 개수는 같다.
(그냥 노드의 수는 다를 수 있음.)
출처: https://zeddios.tistory.com/237 [ZeddiOS]
레드 블랙트리의 구조를 유지시키고, 생성하는 과정은 복잡하고 길다.
출처의 설명보다 잘 기재할 자신이 없기에 출처를 참고할 것을 권한다.
자료구조에대한 부분을 다루고 있지만, 알고리즘을 위한 포스팅이기에 생략하겠다.
Restructuring, Recoloring을 이용해 레드 블랙 트리의 법칙을 적용하게 되는데,
알고리즘 적으로는 둘 모두 최대 O(log n)의 시간복잡도를 갖고, 현재 사용되는 이진 탐색 트리 중
가장 속도면에서도 효율적인 트리라는 점만 포스팅 하겠다.
Restructuring과 마찬가지로 Recoloring
출처: https://zeddios.tistory.com/237 [ZeddiOS]
출처: https://zeddios.tistory.com/237 [ZeddiOS]
'알고리즘' 카테고리의 다른 글
자바의 자료구조 - Stack (0) | 2021.11.19 |
---|---|
자바의 자료구조 - Map (0) | 2021.11.19 |
자바의 자료구조 - List (0) | 2021.11.18 |
공간복잡도 (0) | 2021.11.17 |
시간복잡도 (0) | 2021.11.17 |