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,537 bytes added ,  1 year ago
m
Fixed syntax highlighting.
(Created page with "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> Unchanged code omitted for clari...")
 
m (Fixed syntax highlighting.)
 
(3 intermediate revisions by one other user not shown)
Line 1:
{{libheader|Phix/online}}
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>
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.
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.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Red_Black_Tree.exw</span>
-- demo\rosetta\Red_Black_Tree.exw
-- ===============================
--</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;">50root</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;">25</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)
┌B7
L---+ 2 (BLACK)
│└R10
L---+ 3 (BLACK)
│ └B11
| | L--- 4 (RED)
┌B12
| R---+ 5 (BLACK)
││ ┌B13
L---+ 6 (RED)
││┌B15
| | L--- 7 (RED)
│└B19
| | L---+ 8 (BLACK)
│ └B20
| R---+ 9 (BLACK)
─B23
| | L---+ 10 (BLACK)
│ ┌B24
| | | R--- 11 (RED)
│ │└R25
| R---+ 12 (RED)
│┌B31
| R---+ 13 (BLACK)
│││┌B32
| R--- 14 (RED)
││└R33
+---+ 15 (BLACK)
││ └B34
| L--- 16 (RED)
└B35
| L---+ 17 (BLACK)
│ ┌R36
| | R--- 18 (RED)
│ ┌B37
| L---+ 19 (RED)
│┌B40
| | R--- 20 (BLACK)
└B43
| L---+ 21 (BLACK)
│┌B45
| | | L--- 22 (RED)
└R48
| | R---+ 23 (BLACK)
└B49
| | R--- 24 (RED)
└B50
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,477

edits

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