1073.out

四个小算法。红黑树

all the operation are based on the follow intervals
(16 21)  (8 9)  (25 30)  (5 8)  (15 23)  (17 19)  (26 26)  (0 3)  (6 10)  (19 20)  

insert node (16 21)
(16 21) root
insert fix up

insert node (8 9)
(16 21) root  black
go left:insert(8 9)
insert fix up

insert node (25 30)
(16 21) root  black
go right:insert(25 30)
insert fix up

insert node (5 8)
(16 21) root  black
go left:(8 9) parent 16  red
go left:insert(5 8)
insert fix up
(5 8) parent 8
 
insert node (15 23)
(16 21) root  black
go left:(8 9) parent 16  black
go right:insert(15 23)
insert fix up

insert node (17 19)
(16 21) root  black
go right:(25 30) parent 16  black
go left:insert(17 19)
insert fix up

insert node (26 26)
(16 21) root  black
go right:(25 30) parent 16  black
go right:insert(26 26)
insert fix up

insert node (0 3)
(16 21) root  black
go left:(8 9) parent 16  black
go left:(5 8) parent 8  red
go left:insert(0 3)
insert fix up
(0 3) parent 5
 
insert node (6 10)
(16 21) root  black
go left:(8 9) parent 16  red
go left:(5 8) parent 8  black
go right:insert(6 10)
insert fix up

insert node (19 20)
(16 21) root  black
go right:(25 30) parent 16  black
go left:(17 19) parent 25  red
go right:insert(19 20)
insert fix up
(19 20) parent 17
 
delete node (17 19)
(17 19) black  parent 25
delete fix up

delete node (0 3)
(0 3) red  parent 5
it dosn't need to fix up

search interval (8 25)
the node (16 21) of the tree overlap the interval (8 25)