Rosetta Code

Red black tree sort/Phix: Difference between revisions

Page Discussion

Red black tree sort/Phix (view source)

Revision as of 15:12, 29 August 2022

55,522 bytes added ,  1 year ago
m
Fixed syntax highlighting.
(oops)
m (Fixed syntax highlighting.)
 
(One intermediate revision by one other user not shown)
Line 1:
{{incorrectlibheader|Phix|Oh dear/online}}
With extra validation. You can run this online [http://phix.x10.mx/p2js/rbtree.htm here]. The output will of course be different every time you open (or F5 reload) that, and not quite match that below.
Didn't check carefully enough... it seems to actally work ok about 3/4 in the 50:25 case, almost never in the 30:15 case...<br>
<!--<syntaxhighlight lang="phix">(phixonline)-->
Since I was invited to and it was about a zillion times easier, I simply added delete routines to the [[Algebraic data types#Phix]] task.<br>
<span style="color: #000080;font-style:italic;">--
Unchanged code omitted for clarity, either copy in the first hundred lines or so from the other task, or use the runnable version in the distro.
-- demo\rosetta\Red_Black_Tree.exw
<!--<lang Phix>(phixonline)-->
-- ===============================
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Red_Black_Tree.exw</span>
--</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">SENTINEL</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rbtree</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> <span style="color: #000080;font-style:italic;">-- node indices are 1(""),6,11,16,21,etc.</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">PARENT</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">COLOUR</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">VALUE</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">LEFT</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">RIGHT</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span>
<span style="color: #000080;font-style:italic;">--(also uses the builtin constants BLACK = 0 and RED = 4)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">SENTINEL</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">freelist</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
<span style="color: #008080;">enumfunction</span> <span style="color: #000000;">CLRnew_node</span><span style="color: #0000FF;">,(</span><span style="color: #004080;">object</span> <span style="color: #000000;">LEFTkey</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">DATAcolour</span><span style="color: #0000FF;">,=</span><span style="color: #004600;">RED</span><span style="color: #0000000000FF;">RIGHT)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">freelist</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">freelist</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">freelist</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">rbtree</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">res</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">res</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">colour</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">res</span><span style="color: #0000FF;">+</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">key</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">res</span><span style="color: #0000FF;">+</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">SENTINEL</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">res</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">SENTINEL</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">new_node</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #004600;">BLACK</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">SENTINEL</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">functionprocedure</span> <span style="color: #000000;">insrelease_node</span><span style="color: #0000FF;">(</span><span style="color: #004080;">objectinteger</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">leafn</span><span style="color: #0000FF;">)</span>
<span style="color: #0080807060A8;">ifassert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">treen</span><span style="color: #0000FF;">!=</span><span style="color: #004600000000;">NULLSENTINEL</span> <span style="color: #0080800000FF;">then)</span>
<span style="color: #000000;">treerbtree</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{[</span><span style="color: #000000;">Rn</span><span style="color: #0000FF;">,]</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span><span style="color: #000000;">leaf</span><span style="color: #0000FF;">,</span><span style="color: #004600;">NULL</span><span style="color: #0000FF000000;">}freelist</span>
<span style="color: #000000;">freelist</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">rotate</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- x y
-- / \ / \
-- y c == right ==&gt; a x
-- / \ &lt;== left == / \
-- a b b c
--
-- (param x is the top node, for d=LEFT
-- swap x and y in the above diagram.)
--</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">and</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">SENTINEL</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">LEFT</span> <span style="color: #008080;">or</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">LEFT</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">-</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">e</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">d</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]?</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">:</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">e</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">b</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">SENTINEL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">b</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span>
<span style="color: #008080;">else</span>
<span style="color: #004080;">object</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lrbtree</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">kp</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">rq</span><span style="color: #0000FF;">}]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">treey</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">leaf</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">kend</span> <span style="color: #008080;">thenif</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">leafrbtree</span><span style="color: #0000FF;"><[</span><span style="color: #000000;">ky</span> <span style="color: #0080800000FF;">then+</span> <span style="color: #000000;">ld</span> <span style="color: #0000FF;">=]</span> <span style="color: #000000;">ins</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">leaf</span><span style="color: #0000FF;">)x</span>
<span style="color: #008080;">else</span> <span style="color: #000000;">rrbtree</span> <span style="color: #0000FF;">=[</span> <span style="color: #000000;">insx</span><span style="color: #0000FF;">(+</span><span style="color: #000000;">rPARENT</span><span style="color: #0000FF;">,]</span> <span style="color: #0000000000FF;">leaf=</span> <span style="color: #0000FF000000;">)y</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">fix_up_insertion</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">RED</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">gp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gp</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]?</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">:</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">rd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">LEFT</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">-</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">uncle</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gp</span><span style="color: #0000FF;">+</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">uncle</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">SENTINEL</span> <span style="color: #008080;">and</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">uncle</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">RED</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">uncle</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">BLACK</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">BLACK</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gp</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">RED</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gp</span> <span style="color: #000080;font-style:italic;">// repeat with grandparent</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span>
<span style="color: #000000;">rotate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rd</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">treerbtree</span> <span style="color: #0000FF;">=[</span> <span style="color: #000000;">balancep</span><span style="color: #0000FF;">({+</span><span style="color: #000000;">cCOLOUR</span><span style="color: #0000FF;">,]</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF004600;">})BLACK</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gp</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">RED</span>
<span style="color: #000000;">rotate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">root</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080000000;">returnp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">treerbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">functionwhile</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">BLACK</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">functionprocedure</span> <span style="color: #000000;">tree_insertinsert_node</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">leafkey</span><span style="color: #0000FF;">)</span>
<span style="color: #000000004080;">treeinteger</span> <span style="color: #0000FF000000;">=node</span> <span style="color: #0000000000FF;">ins=</span><span style="color: #0000FF;">(</span><span style="color: #000000;">treenew_node</span><span style="color: #0000FF;">,(</span><span style="color: #000000;">leafkey</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">treey</span> <span style="color: #0000FF;">[=</span> <span style="color: #000000004600;">1NULL</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Broot</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span>
<span style="color: #008080000080;font-style:italic;">return</span>/ <spany style="color:= #000000;">tree</span>(sentinel) position for new node
// (nb as-is this allows duplicates, it
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
// may want to be more like delete_node)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">SENTINEL</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;"><</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]?</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">:</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080000000;">objectrbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lmy</span>
<span style="color: #008080;">functionif</span> <span style="color: #000000;">leftmosty</span> <span style="color: #0000FF;">(</span><span style="color: #004080;">object=</span> <span style="color: #000000004600;">treeNULL</span> <span style="color: #0000FF008080;">)then</span>
<span style="color: #000080000000;font-">root</span> <span style="color:italic #0000FF;">--=</span> set<span lm and returnstyle="color: tree with that removed#000000;">node</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">lm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">DATA</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">else</span>
<span style="color: #0000007060A8;">treeassert</span><span style="color: #0000FF;">[(</span><span style="color: #000000;">LEFTrbtree</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">=+</span><span style="color: #000000;">d</span><span style="color: #0046000000FF;">NULL]</span> <span style="color: #0000800000FF;font-">=</span> <span style="color:italic #000000;">--SENTINEL</span><span (killstyle="color: refcount#0000FF;">)</span>
<span style="color: #000000;">lrbtree</span> <span style="color: #0000FF;">=[</span> <span style="color: #000000;">leftmosty</span><span style="color: #0000FF;">(+</span><span style="color: #000000;">ld</span><span style="color: #0000FF;">)]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">node</span>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #000000008080;">treeif</span> <span style="color: #0000FF000000;">=y</span> <span style="color: #0000000000FF;">balance==</span> <span style="color: #0000FF004600;">(NULL</span><span style="color: #000000;">tree</span><span style="color: #0000FF008080;">)then</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">BLACK</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">!=</span> <span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">fix_up_insertion</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">returnend</span> <span style="color: #000000008080;">treeprocedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">fix_up_deletion</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (Don't think I could adequately comment this even if I tried,
-- but it is basically the same as several of the other entries.
-- This routine needs that sentinal and is why we can't use NULL)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">root</span> <span style="color: #008080;">and</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">BLACK</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">parent</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">+</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">]?</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">:</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">rd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">+</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">-</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">sibling</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">+</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sibling</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">RED</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sibling</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">BLACK</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">RED</span>
<span style="color: #000000;">rotate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rd</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">sibling</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">+</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sibling</span><span style="color: #0000FF;">+</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">BLACK</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sibling</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">BLACK</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sibling</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">RED</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">parent</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sibling</span><span style="color: #0000FF;">+</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">BLACK</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sibling</span><span style="color: #0000FF;">+</span><span style="color: #000000;">rd</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">BLACK</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sibling</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">RED</span>
<span style="color: #000000;">rotate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sibling</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">sibling</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">+</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sibling</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">BLACK</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sibling</span><span style="color: #0000FF;">+</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">BLACK</span>
<span style="color: #000000;">rotate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rd</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">root</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">BLACK</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">rb_transplant</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">v</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">=</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">v</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">v</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">v</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">find_node</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">node</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">SENTINEL</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">+</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- found!</span>
<span style="color: #000000;">node</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">+</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">:</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">)]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">node</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">delete_node</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">find_node</span><span style="color: #0000FF;">(</span><span style="color: #000000;">root</span><span style="color: #0000FF;">,</span><span style="color: #000000;">key</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">SENTINEL</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Key %d not present in Tree !!\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">key</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080004080;">functioninteger</span> <span style="color: #000000;">dely</span> <span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">treez</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">leafx</span><span style="color: #0000FF;">),</span>
<span style="color: #008080000000;">ify_original_color</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">treerbtree</span><span style="color: #0000FF;">![</span><span style="color: #000000;">y</span><span style="color: #0046000000FF;">NULL+</span><span style="color: #000000;">COLOUR</span><span style="color: #0080800000FF;">then]</span>
<span style="color: #004080008080;">objectif</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">crbtree</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">lz</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">kLEFT</span><span style="color: #0000FF;">,]</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}==</span> <span style="color: #0000FF000000;">=SENTINEL</span> <span style="color: #000000008080;">treethen</span>
<span style="color: #000000;">treex</span> <span style="color: #0000FF;">=</span> <span style="color: #004600000000;">NULLrbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">z</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080000000;">ifrb_transplant</span><span style="color: #0000FF;">(</span><span style="color: #000000;">leafz</span><span style="color: #0000FF;">=,</span> <span style="color: #000000;">kx</span> <span style="color: #0080800000FF;">then)</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #008080000000;">ifz</span><span style="color: #0000FF;">+</span><span style="color: #000000;">lRIGHT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600000000;">NULLSENTINEL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">treerbtree</span> <span style="color: #0000FF;">[</span><span style="color: #000000;">z</span><span style="color: #0000FF;">+</span><span style="color: #000000;">rLEFT</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">rb_transplant</span><span style="color: #0080800000FF;">elsif(</span> <span style="color: #000000;">rz</span><span style="color: #0000FF;">=,</span> <span style="color: #004600000000;">NULLx</span> <span style="color: #0080800000FF;">then)</span>
<span style="color: #000000008080;">treeelse</span> <span style="color: #0000FF000080;font-style:italic;">=</span>/ <spanz style="color:has #000000;">l</span>both child nodes
-- y := minimum/leftmost <spanin style="color:right #008080;">elsesubtree:</span>
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rrbtree</span> <span style="color: #0000FF;">=[</span> <span style="color: #000000;">leftmostz</span><span style="color: #0000FF;">(+</span><span style="color: #000000;">rRIGHT</span><span style="color: #0000FF;">)]</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">kLEFT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">lmSENTINEL</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">treey</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lrbtree</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">ky</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">rLEFT</span><span style="color: #0000FF;">}]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">ifwhile</span>
<span style="color: #000000;">y_original_color</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">z</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span>
<span style="color: #008080;">else</span>
<span style="color: #008080000000;">ifrb_transplant</span><span style="color: #0000FF;">(</span><span style="color: #000000;">leafy</span><span style="color: #0000FF;"><,</span> <span style="color: #000000;">kx</span> <span style="color: #0080800000FF;">then)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">delrbtree</span><span style="color: #0000FF;">([</span><span style="color: #000000;">lz</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">leafRIGHT</span><span style="color: #0000FF;">)]</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">rrbtree</span> <span style="color: #0000FF;">=[</span> <span style="color: #000000;">delr</span><span style="color: #0000FF;">(+</span><span style="color: #000000;">rPARENT</span><span style="color: #0000FF;">,]</span> <span style="color: #0000000000FF;">leaf=</span> <span style="color: #0000FF000000;">)y</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080000000;">ifrb_transplant</span><span style="color: #0000FF;">(</span><span style="color: #000000;">treez</span><span style="color: #0000FF;">!=,</span> <span style="color: #004600000000;">NULLy</span> <span style="color: #0080800000FF;">then)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">treel</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">balancerbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">z</span><span style="color: #0000FF;">(+</span><span style="color: #000000;">treeLEFT</span><span style="color: #0000FF;">)]</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">+</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span>
<span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">z</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">y_original_color</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">BLACK</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">fix_up_deletion</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">release_node</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">visualise_tree</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">=</span><span style="color: #000000;">root</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">prefix</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"+---"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">=</span><span style="color: #000000;">SENTINEL</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"&lt;empty&gt;\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">colour</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]=</span><span style="color: #004600;">RED</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"RED"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"BLACK"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">v</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">+</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">left</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">+</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">right</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">g</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prefix</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">left</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">SENTINEL</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">g4</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prefix</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">prefix</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'L'</span> <span style="color: #008080;">or</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"| "</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">visualise_tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">left</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prefix</span><span style="color: #0000FF;">&</span><span style="color: #008000;">"L---"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">prefix</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">g4</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">plus</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">left</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">SENTINEL</span> <span style="color: #008080;">or</span> <span style="color: #000000;">right</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">SENTINEL</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s%s %v (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">prefix</span><span style="color: #0000FF;">,</span><span style="color: #000000;">plus</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">colour</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">right</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">SENTINEL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">prefix</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'L'</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"| "</span><span style="color: #0000FF;">:</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">visualise_tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">right</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prefix</span><span style="color: #0000FF;">&</span><span style="color: #008000;">"R---"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">isBalanced</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">node</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">SENTINEL</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">lok</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lmxh</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lmnh</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">isBalanced</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">+</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">]),</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">rok</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rmxh</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rmnh</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">isBalanced</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">maxh</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lmxh</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rmxh</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">minh</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lmnh</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rmnh</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">lok</span> <span style="color: #008080;">and</span> <span style="color: #000000;">rok</span> <span style="color: #008080;">and</span> <span style="color: #000000;">maxh</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">minh</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxh</span><span style="color: #0000FF;">,</span><span style="color: #000000;">minh</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">treenode</span><span style="color: #0000FF;">==</span><span style="color: #000000;">SENTINEL</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">tree_deleteBlackHeight</span><span style="color: #0000FF;">(</span><span style="color: #004080;">objectinteger</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">leafnode</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">treenode</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">delSENTINEL</span> <span style="color: #0000FF008080;">(then</span> <span style="color: #000000008080;">treereturn</span> <span style="color: #0000FF000000;">,1</span> <span style="color: #000000008080;">leafend</span> <span style="color: #0000FF008080;">)if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">treeleftBlackHeight</span> <span style="color: #0000FF;">[=</span> <span style="color: #000000;">1BlackHeight</span><span style="color: #0000FF;">](</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">+</span><span style="color: #000000;">BLEFT</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">rightBlackHeight</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">BlackHeight</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">+</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">tree</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">leftBlackHeight</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">rightBlackHeight</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">leftBlackHeight</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">rightBlackHeight</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">rightBlackHeight</span> <span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">rbtree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">node</span><span style="color: #0000FF;">+</span><span style="color: #000000;">COLOUR</span><span style="color: #0000FF;">]=</span><span style="color: #004600;">BLACK</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">mainvalidate_tree</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequencestring</span> <span style="color: #000000;">stuffwhy</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8008080;">shuffleiff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8008080;">tagsetnot</span> <span style="color: #000000;">isBalanced</span><span style="color: #0000FF;">(</span><span style="color: #000000;">30root</span><span style="color: #0000FF;">))[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]?</span><span style="color: #008000;">"balance"</span><span style="color: #0000FF;">:</span>
<span style="color: #004080008080;">objectiff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">treeBlackHeight</span><span style="color: #0000FF;">(</span><span style="color: #000000;">root</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0046000000FF;">?</span><span style="color: #008000;">"height"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">NULL))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">toif</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stuffwhy</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">dothen</span>
<span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree_insertvisualise_tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #0080807060A8;">endcrash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"invalid(%s)"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">why</span><span style="color: #0080800000FF;">for})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">stuff</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">15</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree_delete</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stuff</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">visualise_tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"State of the tree after inserting 30 keys:\n"</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span> <span style="color: #008080;">in</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">30</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">insert_node</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">validate_tree</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">visualise_tree</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nState of the tree after deleting 15 keys:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span> <span style="color: #008080;">in</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">30</span><span style="color: #0000FF;">))[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">15</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">delete_node</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">validate_tree</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">visualise_tree</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
State of the tree after inserting 30 keys:
┌B3
L--- 1 (RED)
│└B4
L---+ 2 (BLACK)
│ └R5
L---+ 3 (BLACK)
┌B6
| | L--- 4 (RED)
││┌B9
| R---+ 5 (BLACK)
│└R10
L---+ 6 (RED)
│ └B11
| | L--- 7 (RED)
─B15
| | L---+ 8 (BLACK)
│┌B17
| R---+ 9 (BLACK)
└B19
| | L---+ 10 (BLACK)
│ ┌B20
| | | R--- 11 (RED)
│┌B22
| R---+ 12 (RED)
└R24
| R---+ 13 (BLACK)
└B27
| R--- 14 (RED)
└B30
+---+ 15 (BLACK)
| L--- 16 (RED)
| L---+ 17 (BLACK)
| | R--- 18 (RED)
| L---+ 19 (RED)
| | R--- 20 (BLACK)
| L---+ 21 (BLACK)
| | | L--- 22 (RED)
| | R---+ 23 (BLACK)
| | R--- 24 (RED)
R---+ 25 (RED)
| L--- 26 (RED)
| L---+ 27 (BLACK)
| | R--- 28 (RED)
R---+ 29 (BLACK)
R--- 30 (BLACK)
 
State of the tree after deleting 15 keys:
L--- 3 (BLACK)
L---+ 6 (BLACK)
| | L--- 7 (RED)
| | L---+ 8 (BLACK)
| R---+ 10 (RED)
| R--- 11 (BLACK)
+---+ 17 (BLACK)
| L--- 19 (BLACK)
| L---+ 20 (BLACK)
| | R--- 24 (BLACK)
R---+ 25 (RED)
| L--- 26 (RED)
| L---+ 27 (BLACK)
R---+ 29 (BLACK)
R--- 30 (BLACK)
</pre>
PureFox
9,482

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/321152...328857"