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

 : 이진탐색트리(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]