자바의 자료구조 - 이진 탐색 트리, 레드 블랙 트리

: 이진탐색트리(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는 같다.

== 리프노드에서 루트노드까지 가는 경로에서 만나는 블랙노드의 개수는 같다.

(그냥 노드의 수는 다를 수 있음.)

레드 블랙트리의 구조를 유지시키고, 생성하는 과정은 복잡하고 길다.

출처의 설명보다 잘 기재할 자신이 없기에 출처를 참고할 것을 권한다.

자료구조에대한 부분을 다루고 있지만, 알고리즘을 위한 포스팅이기에 생략하겠다.

Restructuring, Recoloring을 이용해 레드 블랙 트리의 법칙을 적용하게 되는데,

알고리즘 적으로는 둘 모두 최대 O(log n)의 시간복잡도를 갖고, 현재 사용되는 이진 탐색 트리 중

가장 속도면에서도 효율적인 트리라는 점만 포스팅 하겠다.

Restructuring과 마찬가지로 Recoloring

출처: https://zeddios.tistory.com/237 [ZeddiOS]

출처: https://zeddios.tistory.com/237 [ZeddiOS]

이름은 훌륭한 마커가 되지