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

red_black_tree (과정분석)

left root right  parent   color

---------- run ----------           

l: 0 | 1|  0:r  >p: 2  ><  red

l: 1 | 2|  3:r  >p: 4  >< black

l: 0 | 3|  0:r  >p: 2  ><  red

l: 2 | 4|  8:r  >p: 0  >< black

l: 0 | 5|  0:r  >p: 6  ><  red

l: 5 | 6|  7:r  >p: 8  >< black

l: 0 | 7|  0:r  >p: 6  ><  red

l: 6 | 8|  9:r  >p: 4  ><  red

l: 0 | 9| 10:r  >p: 8  >< black

l: 0 |10|  0:r  >p: 9  ><  red

del = 1

l: 0 | 2|  3:r  >p: 4  >< black

l: 0 | 3|  0:r  >p: 2  ><  red

l: 2 | 4|  8:r  >p: 0  >< black

l: 0 | 5|  0:r  >p: 6  ><  red

l: 5 | 6|  7:r  >p: 8  >< black

l: 0 | 7|  0:r  >p: 6  ><  red

l: 6 | 8|  9:r  >p: 4  ><  red

l: 0 | 9| 10:r  >p: 8  >< black

l: 0 |10|  0:r  >p: 9  ><  red

 

=============

del = 2

l: 0 | 3|  0:r  >p: 4  >< black

l: 3 | 4|  8:r  >p: 0  >< black

l: 0 | 5|  0:r  >p: 6  ><  red

l: 5 | 6|  7:r  >p: 8  >< black

l: 0 | 7|  0:r  >p: 6  ><  red

l: 6 | 8|  9:r  >p: 4  ><  red

l: 0 | 9| 10:r  >p: 8  >< black

l: 0 |10|  0:r  >p: 9  ><  red

 

=============                    

del = 3

l: 0 | 4|  5:r  >p: 6  >< black

l: 0 | 5|  0:r  >p: 4  ><  red

l: 4 | 6|  7:r  >p: 8  ><  red

l: 0 | 7|  0:r  >p: 6  >< black

l: 6 | 8|  9:r  >p: 0  >< black

l: 0 | 9| 10:r  >p: 8  >< black

l: 0 |10|  0:r  >p: 9  ><  red

 

=============

del = 4

l: 0 | 5|  0:r  >p: 6  >< black

l: 5 | 6|  7:r  >p: 8  ><  red

l: 0 | 7|  0:r  >p: 6  >< black

l: 6 | 8|  9:r  >p: 0  >< black

l: 0 | 9| 10:r  >p: 8  >< black

l: 0 |10|  0:r  >p: 9  ><  red

 

=============

del = 5

l: 0 | 6|  7:r  >p: 8  >< black

l: 0 | 7|  0:r  >p: 6  ><  red

l: 6 | 8|  9:r  >p: 0  >< black

l: 0 | 9| 10:r  >p: 8  >< black

l: 0 |10|  0:r  >p: 9  ><  red

 

=============

del = 6

l: 0 | 7|  0:r  >p: 8  >< black

l: 7 | 8|  9:r  >p: 0  >< black

l: 0 | 9| 10:r  >p: 8  >< black

l: 0 |10|  0:r  >p: 9  ><  red

 

=============

del = 7

l: 0 | 8|  0:r  >p: 9  >< black

l: 8 | 9| 10:r  >p: 0  >< black

l: 0 |10|  0:r  >p: 9  >< black

 

=============

del = 8

l: 0 | 9| 10:r  >p: 0  >< black

l: 0 |10|  0:r  >p: 9  ><  red

 

=============

del = 9

l: 0 |10|  0:r  >p: 0  >< black

 

=============

del = 10

 

=============

 

출력 완료 (0초 경과)



트리내 원소를 제거하거나 생성할때

 

높이를 최소한으로 될수있는한 낮추겜.

 

좌우 균형이 잡힐 수록 높이는 낮아짐


저작자표시

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

동적프로그래밍 (concept)  (0) 2009.09.17
RB_tree (동적순서통계)  (0) 2009.09.17
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
Posted by 멍충한아싸
Trackback 0 Comment 0

댓글을 달아 주세요