알고리즘2009. 9. 17. 00:00

레드 블랙 트리는  이진 검색 트리로서 노드당 한비트의 추가적인 기억 공간을

 

지닌다. 비트는 노드의 색깔을 나타내는데. 적색(red) 이나 흑색 (black) 될수 있다.

 

레드 블랙 트리는 루트에서 리프 까지의 경로 내에 나타나는 노드들의 색깔을 제한함으로서 그러한 경로 어떠한 것도 다른것보다 두배 이상 길지 않음을 보장하게 되는데

 

이로써 트리는 근사적으로 균형을 이룬 트리 된다.

트리는 color, key, left, right, p 등의 필드를 가진다. 만약 노드의 자식 또는

 

부모가 존재하지 않으면 그에 대응되는 노드의 포인터 필드는 Nil 값으로 채워진다.

 

이러한 NIL들은 이진 검색 트리의 리프 노드들에 대한 포인터들로 간주하고 키를 가지는 정상적인 노드들은 트리의 내부 노드로 간주할 것이다.

 

다음의 레드블랙 특성을 만족하는 이진 검색 트리를 레드블랙 트리라고 한다.

  1. 모든 노드는 적색이거나 흑색이다.
  2. 루트는 흑색이다.
  3. 모든 리프(NIL) 흑색이다.
  4. 노드가 적색이면 노드의 자식은 모두 흑색이다.
  5. 각각의 노드로부터 노드의 자손인 리프들로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.



레드-블랙 트리의 읽기 전용(read-only) 동작(검색 )은 이진탐색트리의 읽기 전용 동작의 구현을 변경하지 않아도 되는데, 이는 레드-블랙 트리가 이진탐색트리의 특수한 한 형태이기 때문이다. 그러나 삽입(insertion)과 삭제(removal)의 경우 이진탐색트리의 구현에 따른 동작만으로는 레드-블랙 트리의 특성을 만족하지 못하게 된다. 레드-블랙 트리의 특성을 다시 만족하게 만들기 위해서는 O(log n) 또는 amortized O(1)번의 색 변환과(실제로는 매우 빨리 이루어진다) 최대 3회의 트리 회전(tree rotation)이 필요하다(삽입의 경우 2회). 삽입과 삭제는 복잡한 동작이지만, 그 복잡도는 여전히 O(log n)이다.

좌회전함수

우회전함수

 

삽입함수

삽입시 레드블랙특성만족함수

 

빼내는함수

빼낼때 레드블랙특성만족함수


'알고리즘' 카테고리의 다른 글

red_black_tree (과정분석)  (0) 2009.09.17
red_black_tree (func)  (0) 2009.09.17
red_black_tree (concept)  (0) 2009.09.17
BST (평가)  (0) 2009.09.16
BST (func)  (0) 2009.09.16
binary search tree (concept)  (0) 2009.09.16
Posted by 멍충한아싸

댓글을 달아 주세요