Skip to main content
Go to Latest
File
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547
import { assertEquals, assertStrictEquals } from "../testing/asserts.ts";import { ascend, descend, RBTree } from "./rb_tree.ts";import { Container, MyMath } from "./_test_utils.ts";
Deno.test("[collections/RBTree] with default ascend comparator", () => { const trees: RBTree<number>[] = [new RBTree(), new RBTree()]; const values: number[] = [-10, 9, -1, 100, 1, 0, -100, 10, -9];
const expectedMin: number[][] = [ [-10, -10, -10, -10, -10, -10, -100, -100, -100], [-9, -9, -100, -100, -100, -100, -100, -100, -100], ]; const expectedMax: number[][] = [ [-10, 9, 9, 100, 100, 100, 100, 100, 100], [-9, 10, 10, 10, 10, 100, 100, 100, 100], ]; for (let i = 0; i < 2; i++) { assertEquals(trees[i].size, 0); assertEquals(trees[i].isEmpty(), true); for (let j = 0; j < values.length; j++) { assertEquals(trees[i].find(values[j]), null); assertEquals(trees[i].insert(values[j]), true); assertEquals(trees[i].find(values[j]), values[j]); assertEquals(trees[i].size, j + 1); assertEquals(trees[i].isEmpty(), false); assertEquals(trees[i].min(), expectedMin[i][j]); assertEquals(trees[i].max(), expectedMax[i][j]); } for (let j = 0; j < values.length; j++) { assertEquals(trees[i].insert(values[j]), false); assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false); assertEquals(trees[i].min(), -100); assertEquals(trees[i].max(), 100); } values.reverse(); }
for (let i = 0; i < 2; i++) { assertEquals( [...trees[i].lnrValues()], [-100, -10, -9, -1, 0, 1, 9, 10, 100], ); assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false);
assertEquals( [...trees[i]], [-100, -10, -9, -1, 0, 1, 9, 10, 100], ); assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false);
assertEquals( [...trees[i].rnlValues()], [100, 10, 9, 1, 0, -1, -9, -10, -100], ); assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false); }
assertEquals( [...trees[0].nlrValues()], [-1, -10, -100, -9, 9, 1, 0, 100, 10], ); assertEquals( [...trees[1].nlrValues()], [-9, -100, -10, 1, 0, -1, 10, 9, 100], ); for (let i = 0; i < 2; i++) { assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false); }
assertEquals( [...trees[0].lrnValues()], [-100, -9, -10, 0, 1, 10, 100, 9, -1], ); assertEquals( [...trees[1].lrnValues()], [-10, -100, -1, 0, 9, 100, 10, 1, -9], ); for (let i = 0; i < 2; i++) { assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false); }
assertEquals( [...trees[0].lvlValues()], [-1, -10, 9, -100, -9, 1, 100, 0, 10], ); assertEquals( [...trees[1].lvlValues()], [-9, -100, 1, -10, 0, 10, -1, 9, 100], ); for (let i = 0; i < 2; i++) { assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false); }
for (let i = 0; i < 2; i++) { const expected: number[] = [-100, -10, -9, -1, 0, 1, 9, 10, 100]; for (let j = 0; j < values.length; j++) { assertEquals(trees[i].size, values.length - j); assertEquals(trees[i].isEmpty(), false); assertEquals(trees[i].find(values[j]), values[j]);
assertEquals(trees[i].remove(values[j]), true); expected.splice(expected.indexOf(values[j]), 1); assertEquals([...trees[i]], expected); assertEquals(trees[i].find(values[j]), null);
assertEquals(trees[i].remove(values[j]), false); assertEquals([...trees[i]], expected); assertEquals(trees[i].find(values[j]), null); } assertEquals(trees[i].size, 0); assertEquals(trees[i].isEmpty(), true); }});
Deno.test("[collections/RBTree] with descend comparator", () => { const trees: RBTree<number>[] = [new RBTree(descend), new RBTree(descend)]; const values: number[] = [-10, 9, -1, 100, 1, 0, -100, 10, -9];
const expectedMin: number[][] = [ [-10, 9, 9, 100, 100, 100, 100, 100, 100], [-9, 10, 10, 10, 10, 100, 100, 100, 100, 100], ]; const expectedMax: number[][] = [ [-10, -10, -10, -10, -10, -10, -100, -100, -100], [-9, -9, -100, -100, -100, -100, -100, -100, -100], ]; for (let i = 0; i < 2; i++) { assertEquals(trees[i].size, 0); assertEquals(trees[i].isEmpty(), true); for (let j = 0; j < values.length; j++) { assertEquals(trees[i].find(values[j]), null); assertEquals(trees[i].insert(values[j]), true); assertEquals(trees[i].find(values[j]), values[j]); assertEquals(trees[i].size, j + 1); assertEquals(trees[i].isEmpty(), false); assertEquals(trees[i].min(), expectedMin[i][j]); assertEquals(trees[i].max(), expectedMax[i][j]); } for (let j = 0; j < values.length; j++) { assertEquals(trees[i].insert(values[j]), false); assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false); assertEquals(trees[i].min(), 100); assertEquals(trees[i].max(), -100); } values.reverse(); }
for (let i = 0; i < 2; i++) { assertEquals( [...trees[i].lnrValues()], [100, 10, 9, 1, 0, -1, -9, -10, -100], ); assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false);
assertEquals( [...trees[i]], [100, 10, 9, 1, 0, -1, -9, -10, -100], ); assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false);
assertEquals( [...trees[i].rnlValues()], [-100, -10, -9, -1, 0, 1, 9, 10, 100], ); assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false); }
assertEquals( [...trees[0].nlrValues()], [-1, 9, 100, 10, 1, 0, -10, -9, -100], ); assertEquals( [...trees[1].nlrValues()], [-9, 1, 10, 100, 9, 0, -1, -100, -10], ); for (let i = 0; i < 2; i++) { assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false); }
assertEquals( [...trees[0].lrnValues()], [10, 100, 0, 1, 9, -9, -100, -10, -1], ); assertEquals( [...trees[1].lrnValues()], [100, 9, 10, -1, 0, 1, -10, -100, -9], ); for (let i = 0; i < 2; i++) { assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false); }
assertEquals( [...trees[0].lvlValues()], [-1, 9, -10, 100, 1, -9, -100, 10, 0], ); assertEquals( [...trees[1].lvlValues()], [-9, 1, -100, 10, 0, -10, 100, 9, -1], ); for (let i = 0; i < 2; i++) { assertEquals(trees[i].size, values.length); assertEquals(trees[i].isEmpty(), false); }
for (let i = 0; i < 2; i++) { const expected: number[] = [100, 10, 9, 1, 0, -1, -9, -10, -100]; for (let j = 0; j < values.length; j++) { assertEquals(trees[i].size, values.length - j); assertEquals(trees[i].isEmpty(), false); assertEquals(trees[i].find(values[j]), values[j]);
assertEquals(trees[i].remove(values[j]), true); expected.splice(expected.indexOf(values[j]), 1); assertEquals([...trees[i]], expected); assertEquals(trees[i].find(values[j]), null);
assertEquals(trees[i].remove(values[j]), false); assertEquals([...trees[i]], expected); assertEquals(trees[i].find(values[j]), null); } assertEquals(trees[i].size, 0); assertEquals(trees[i].isEmpty(), true); }});
Deno.test("[collections/RBTree] containing objects", () => { const tree: RBTree<Container> = new RBTree(( a: Container, b: Container, ) => ascend(a.id, b.id)); const ids: number[] = [-10, 9, -1, 100, 1, 0, -100, 10, -9];
for (let i = 0; i < ids.length; i++) { const newContainer: Container = { id: ids[i], values: [] }; assertEquals(tree.find(newContainer), null); assertEquals(tree.insert(newContainer), true); newContainer.values.push(i - 1, i, i + 1); assertStrictEquals(tree.find({ id: ids[i], values: [] }), newContainer); assertEquals(tree.size, i + 1); assertEquals(tree.isEmpty(), false); } for (let i = 0; i < ids.length; i++) { const newContainer: Container = { id: ids[i], values: [] }; assertEquals( tree.find({ id: ids[i] } as Container), { id: ids[i], values: [i - 1, i, i + 1] }, ); assertEquals(tree.insert(newContainer), false); assertEquals( tree.find({ id: ids[i], values: [] }), { id: ids[i], values: [i - 1, i, i + 1] }, ); assertEquals(tree.size, ids.length); assertEquals(tree.isEmpty(), false); }
assertEquals( [...tree].map((container) => container.id), [-100, -10, -9, -1, 0, 1, 9, 10, 100], ); assertEquals(tree.size, ids.length); assertEquals(tree.isEmpty(), false);
const expected: number[] = [-100, -10, -9, -1, 0, 1, 9, 10, 100]; for (let i = 0; i < ids.length; i++) { assertEquals(tree.size, ids.length - i); assertEquals(tree.isEmpty(), false); assertEquals( tree.find({ id: ids[i], values: [] }), { id: ids[i], values: [i - 1, i, i + 1] }, );
assertEquals(tree.remove({ id: ids[i], values: [] }), true); expected.splice(expected.indexOf(ids[i]), 1); assertEquals([...tree].map((container) => container.id), expected); assertEquals(tree.find({ id: ids[i], values: [] }), null);
assertEquals(tree.remove({ id: ids[i], values: [] }), false); assertEquals([...tree].map((container) => container.id), expected); assertEquals(tree.find({ id: ids[i], values: [] }), null); } assertEquals(tree.size, 0); assertEquals(tree.isEmpty(), true);});
Deno.test("[collections/RBTree] from Iterable", () => { const values: number[] = [-10, 9, -1, 100, 9, 1, 0, 9, -100, 10, -9]; const originalValues: number[] = Array.from(values); const expected: number[] = [-100, -10, -9, -1, 0, 1, 9, 10, 100]; let tree: RBTree<number> = RBTree.from(values); assertEquals(values, originalValues); assertEquals([...tree], expected); assertEquals([...tree.nlrValues()], [-1, -10, -100, -9, 9, 1, 0, 100, 10]); assertEquals([...tree.lvlValues()], [-1, -10, 9, -100, -9, 1, 100, 0, 10]);
tree = RBTree.from(values, { compare: descend }); assertEquals(values, originalValues); assertEquals([...tree].reverse(), expected); assertEquals([...tree.nlrValues()], [-1, 9, 100, 10, 1, 0, -10, -9, -100]); assertEquals([...tree.lvlValues()], [-1, 9, -10, 100, 1, -9, -100, 10, 0]);
tree = RBTree.from(values, { map: (v: number) => 2 * v, }); assertEquals([...tree], expected.map((v: number) => 2 * v)); assertEquals([...tree.nlrValues()], [-2, -20, -200, -18, 18, 2, 0, 200, 20]); assertEquals([...tree.lvlValues()], [-2, -20, 18, -200, -18, 2, 200, 0, 20]);
const math = new MyMath(); tree = RBTree.from(values, { map: function (this: MyMath, v: number) { return this.multiply(3, v); }, thisArg: math, }); assertEquals(values, originalValues); assertEquals([...tree], expected.map((v: number) => 3 * v)); assertEquals([...tree.nlrValues()], [-3, -30, -300, -27, 27, 3, 0, 300, 30]); assertEquals([...tree.lvlValues()], [-3, -30, 27, -300, -27, 3, 300, 0, 30]);
tree = RBTree.from(values, { compare: descend, map: (v: number) => 2 * v, }); assertEquals(values, originalValues); assertEquals([...tree].reverse(), expected.map((v: number) => 2 * v)); assertEquals([...tree.nlrValues()], [-2, 18, 200, 20, 2, 0, -20, -18, -200]); assertEquals([...tree.lvlValues()], [-2, 18, -20, 200, 2, -18, -200, 20, 0]);
tree = RBTree.from(values, { compare: descend, map: function (this: MyMath, v: number) { return this.multiply(3, v); }, thisArg: math, }); assertEquals(values, originalValues); assertEquals([...tree].reverse(), expected.map((v: number) => 3 * v)); assertEquals([...tree.nlrValues()], [-3, 27, 300, 30, 3, 0, -30, -27, -300]); assertEquals([...tree.lvlValues()], [-3, 27, -30, 300, 3, -27, -300, 30, 0]);});
Deno.test("[collections/RBTree] from RBTree with default ascend comparator", () => { const values: number[] = [-10, 9, -1, 100, 9, 1, 0, 9, -100, 10, -9]; const expected: number[] = [-100, -10, -9, -1, 0, 1, 9, 10, 100]; const originalTree: RBTree<number> = new RBTree(); for (const value of values) originalTree.insert(value); let tree: RBTree<number> = RBTree.from(originalTree); assertEquals([...originalTree], expected); assertEquals([...tree], expected); assertEquals([...tree.nlrValues()], [...originalTree.nlrValues()]); assertEquals([...tree.lvlValues()], [...originalTree.lvlValues()]);
tree = RBTree.from(originalTree, { compare: descend }); assertEquals([...originalTree], expected); assertEquals([...tree].reverse(), expected); assertEquals([...tree.nlrValues()], [-1, 1, 10, 100, 9, 0, -10, -9, -100]); assertEquals([...tree.lvlValues()], [-1, 1, -10, 10, 0, -9, -100, 100, 9]);
tree = RBTree.from(originalTree, { map: (v: number) => 2 * v, }); assertEquals([...originalTree], expected); assertEquals([...tree], expected.map((v: number) => 2 * v)); assertEquals([...tree.nlrValues()], [-2, -20, -200, -18, 2, 0, 20, 18, 200]); assertEquals([...tree.lvlValues()], [-2, -20, 2, -200, -18, 0, 20, 18, 200]);
const math = new MyMath(); tree = RBTree.from(originalTree, { map: function (this: MyMath, v: number) { return this.multiply(3, v); }, thisArg: math, }); assertEquals([...originalTree], expected); assertEquals([...tree], expected.map((v: number) => 3 * v)); assertEquals([...tree.nlrValues()], [-3, -30, -300, -27, 3, 0, 30, 27, 300]); assertEquals([...tree.lvlValues()], [-3, -30, 3, -300, -27, 0, 30, 27, 300]);
tree = RBTree.from(originalTree, { compare: descend, map: (v: number) => 2 * v, }); assertEquals([...originalTree], expected); assertEquals([...tree].reverse(), expected.map((v: number) => 2 * v)); assertEquals([...tree.nlrValues()], [-2, 2, 20, 200, 18, 0, -20, -18, -200]); assertEquals([...tree.lvlValues()], [-2, 2, -20, 20, 0, -18, -200, 200, 18]);
tree = RBTree.from(originalTree, { compare: descend, map: function (this: MyMath, v: number) { return this.multiply(3, v); }, thisArg: math, }); assertEquals([...originalTree], expected); assertEquals([...tree].reverse(), expected.map((v: number) => 3 * v)); assertEquals([...tree.nlrValues()], [-3, 3, 30, 300, 27, 0, -30, -27, -300]); assertEquals([...tree.lvlValues()], [-3, 3, -30, 30, 0, -27, -300, 300, 27]);});
Deno.test("[collections/RBTree] from RBTree with descend comparator", () => { const values: number[] = [-10, 9, -1, 100, 9, 1, 0, 9, -100, 10, -9]; const expected: number[] = [100, 10, 9, 1, 0, -1, -9, -10, -100]; const originalTree: RBTree<number> = new RBTree(descend); for (const value of values) originalTree.insert(value); let tree: RBTree<number> = RBTree.from(originalTree); assertEquals([...originalTree], expected); assertEquals([...tree], expected); assertEquals([...tree.nlrValues()], [...originalTree.nlrValues()]); assertEquals([...tree.lvlValues()], [...originalTree.lvlValues()]);
tree = RBTree.from(originalTree, { compare: ascend }); assertEquals([...originalTree], expected); assertEquals([...tree].reverse(), expected); assertEquals([...tree.nlrValues()], [1, -1, -10, -100, -9, 0, 10, 9, 100]); assertEquals([...tree.lvlValues()], [1, -1, 10, -10, 0, 9, 100, -100, -9]);
tree = RBTree.from(originalTree, { map: (v: number) => 2 * v, }); assertEquals([...originalTree], expected); assertEquals([...tree], expected.map((v: number) => 2 * v)); assertEquals([...tree.nlrValues()], [2, 20, 200, 18, -2, 0, -20, -18, -200]); assertEquals([...tree.lvlValues()], [2, 20, -2, 200, 18, 0, -20, -18, -200]);
const math = new MyMath(); tree = RBTree.from(originalTree, { map: function (this: MyMath, v: number) { return this.multiply(3, v); }, thisArg: math, }); assertEquals([...originalTree], expected); assertEquals([...tree], expected.map((v: number) => 3 * v)); assertEquals([...tree.nlrValues()], [3, 30, 300, 27, -3, 0, -30, -27, -300]); assertEquals([...tree.lvlValues()], [3, 30, -3, 300, 27, 0, -30, -27, -300]);
tree = RBTree.from(originalTree, { compare: ascend, map: (v: number) => 2 * v, }); assertEquals([...originalTree], expected); assertEquals([...tree].reverse(), expected.map((v: number) => 2 * v)); assertEquals([...tree.nlrValues()], [2, -2, -20, -200, -18, 0, 20, 18, 200]); assertEquals([...tree.lvlValues()], [2, -2, 20, -20, 0, 18, 200, -200, -18]);
tree = RBTree.from(originalTree, { compare: ascend, map: function (this: MyMath, v: number) { return this.multiply(3, v); }, thisArg: math, }); assertEquals([...originalTree], expected); assertEquals([...tree].reverse(), expected.map((v: number) => 3 * v)); assertEquals([...tree.nlrValues()], [3, -3, -30, -300, -27, 0, 30, 27, 300]); assertEquals([...tree.lvlValues()], [3, -3, 30, -30, 0, 27, 300, -300, -27]);});
Deno.test("[collections/RBTree] insert rebalance left", () => { let values: number[] = [8, 4, 10, 0, 6, 11, -2, 2]; let tree: RBTree<number> = RBTree.from(values); assertEquals([...tree.nlrValues()], [8, 4, 0, -2, 2, 6, 10, 11]); assertEquals([...tree.lvlValues()], [8, 4, 10, 0, 6, 11, -2, 2]); assertEquals(tree.insert(-3), true); assertEquals([...tree.nlrValues()], [4, 0, -2, -3, 2, 8, 6, 10, 11]); assertEquals([...tree.lvlValues()], [4, 0, 8, -2, 2, 6, 10, -3, 11]);
tree = RBTree.from(values); assertEquals(tree.insert(-1), true); assertEquals([...tree.nlrValues()], [4, 0, -2, -1, 2, 8, 6, 10, 11]); assertEquals([...tree.lvlValues()], [4, 0, 8, -2, 2, 6, 10, -1, 11]);
tree = RBTree.from(values); assertEquals(tree.insert(1), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 1, 8, 6, 10, 11]); assertEquals([...tree.lvlValues()], [4, 0, 8, -2, 2, 6, 10, 1, 11]);
tree = RBTree.from(values); assertEquals(tree.insert(3), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 3, 8, 6, 10, 11]); assertEquals([...tree.lvlValues()], [4, 0, 8, -2, 2, 6, 10, 3, 11]);
values = [4, -4, 6, -5, 0, 7, -2, 2]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, -4, -5, 0, -2, 2, 6, 7]); assertEquals([...tree.lvlValues()], [4, -4, 6, -5, 0, 7, -2, 2]); assertEquals(tree.insert(-3), true); assertEquals([...tree.nlrValues()], [0, -4, -5, -2, -3, 4, 2, 6, 7]); assertEquals([...tree.lvlValues()], [0, -4, 4, -5, -2, 2, 6, -3, 7]);
tree = RBTree.from(values); assertEquals(tree.insert(-1), true); assertEquals([...tree.nlrValues()], [0, -4, -5, -2, -1, 4, 2, 6, 7]); assertEquals([...tree.lvlValues()], [0, -4, 4, -5, -2, 2, 6, -1, 7]);
tree = RBTree.from(values); assertEquals(tree.insert(1), true); assertEquals([...tree.nlrValues()], [0, -4, -5, -2, 4, 2, 1, 6, 7]); assertEquals([...tree.lvlValues()], [0, -4, 4, -5, -2, 2, 6, 1, 7]);
tree = RBTree.from(values); assertEquals(tree.insert(3), true); assertEquals([...tree.nlrValues()], [0, -4, -5, -2, 4, 2, 3, 6, 7]); assertEquals([...tree.lvlValues()], [0, -4, 4, -5, -2, 2, 6, 3, 7]);});
Deno.test("[collections/RBTree] insert rebalance right", () => { let values: number[] = [-4, -6, 4, 0, 6, -7, -2, 2]; let tree: RBTree<number> = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -6, -7, 4, 0, -2, 2, 6]); assertEquals([...tree.lvlValues()], [-4, -6, 4, -7, 0, 6, -2, 2]); assertEquals(tree.insert(-3), true); assertEquals([...tree.nlrValues()], [0, -4, -6, -7, -2, -3, 4, 2, 6]); assertEquals([...tree.lvlValues()], [0, -4, 4, -6, -2, 2, 6, -7, -3]);
tree = RBTree.from(values); assertEquals(tree.insert(-1), true); assertEquals([...tree.nlrValues()], [0, -4, -6, -7, -2, -1, 4, 2, 6]); assertEquals([...tree.lvlValues()], [0, -4, 4, -6, -2, 2, 6, -7, -1]);
tree = RBTree.from(values); assertEquals(tree.insert(1), true); assertEquals([...tree.nlrValues()], [0, -4, -6, -7, -2, 4, 2, 1, 6]); assertEquals([...tree.lvlValues()], [0, -4, 4, -6, -2, 2, 6, -7, 1]);
tree = RBTree.from(values); assertEquals(tree.insert(3), true); assertEquals([...tree.nlrValues()], [0, -4, -6, -7, -2, 4, 2, 3, 6]); assertEquals([...tree.lvlValues()], [0, -4, 4, -6, -2, 2, 6, -7, 3]);
values = [-8, -10, -4, -11, -6, 0, -2, 2]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-8, -10, -11, -4, -6, 0, -2, 2]); assertEquals([...tree.lvlValues()], [-8, -10, -4, -11, -6, 0, -2, 2]); assertEquals(tree.insert(-3), true); assertEquals([...tree.nlrValues()], [-4, -8, -10, -11, -6, 0, -2, -3, 2]); assertEquals([...tree.lvlValues()], [-4, -8, 0, -10, -6, -2, 2, -11, -3]);
tree = RBTree.from(values); assertEquals(tree.insert(-1), true); assertEquals([...tree.nlrValues()], [-4, -8, -10, -11, -6, 0, -2, -1, 2]); assertEquals([...tree.lvlValues()], [-4, -8, 0, -10, -6, -2, 2, -11, -1]);
tree = RBTree.from(values); assertEquals(tree.insert(1), true); assertEquals([...tree.nlrValues()], [-4, -8, -10, -11, -6, 0, -2, 2, 1]); assertEquals([...tree.lvlValues()], [-4, -8, 0, -10, -6, -2, 2, -11, 1]);
tree = RBTree.from(values); assertEquals(tree.insert(3), true); assertEquals([...tree.nlrValues()], [-4, -8, -10, -11, -6, 0, -2, 2, 3]); assertEquals([...tree.lvlValues()], [-4, -8, 0, -10, -6, -2, 2, -11, 3]);});
Deno.test("[collections/RBTree] remove rebalance root", () => { let values: number[] = [0]; let tree: RBTree<number> = RBTree.from(values); assertEquals([...tree.nlrValues()], [0]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], []);
values = [0, -1, 1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [0, -1, 1]); assertEquals([...tree.lvlValues()], [0, -1, 1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [1, -1]); assertEquals([...tree.lvlValues()], [1, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [0, 1]); assertEquals([...tree.lvlValues()], [0, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [0, -1]); assertEquals([...tree.lvlValues()], [0, -1]);
values = [0, -2, 2, -3, -1, 1, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [0, -2, -3, -1, 2, 1, 3]); assertEquals([...tree.lvlValues()], [0, -2, 2, -3, -1, 1, 3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [1, -2, -3, -1, 2, 3]); assertEquals([...tree.lvlValues()], [1, -2, 2, -3, -1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [0, -1, -3, 2, 1, 3]); assertEquals([...tree.lvlValues()], [0, -1, 2, -3, 1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [0, -2, -3, -1, 3, 1]); assertEquals([...tree.lvlValues()], [0, -2, 3, -3, -1, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [0, -2, -1, 2, 1, 3]); assertEquals([...tree.lvlValues()], [0, -2, 2, -1, 1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [0, -2, -3, 2, 1, 3]); assertEquals([...tree.lvlValues()], [0, -2, 2, -3, 1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [0, -2, -3, -1, 2, 3]); assertEquals([...tree.lvlValues()], [0, -2, 2, -3, -1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [0, -2, -3, -1, 2, 1]); assertEquals([...tree.lvlValues()], [0, -2, 2, -3, -1, 1]);
values = [0, -2, 2, -3, -1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [0, -2, -3, -1, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2, -3, -1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-2, -3, 2, -1]); assertEquals([...tree.lvlValues()], [-2, -3, 2, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [0, -1, -3, 2]); assertEquals([...tree.lvlValues()], [0, -1, 2, -3]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-2, -3, 0, -1]); assertEquals([...tree.lvlValues()], [-2, -3, 0, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [0, -2, -1, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [0, -2, -3, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2, -3]);
values = [0, -2, 2, 1, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [0, -2, 2, 1, 3]); assertEquals([...tree.lvlValues()], [0, -2, 2, 1, 3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [1, -2, 2, 3]); assertEquals([...tree.lvlValues()], [1, -2, 2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [2, 0, 1, 3]); assertEquals([...tree.lvlValues()], [2, 0, 3, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [0, -2, 3, 1]); assertEquals([...tree.lvlValues()], [0, -2, 3, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [0, -2, 2, 3]); assertEquals([...tree.lvlValues()], [0, -2, 2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [0, -2, 2, 1]); assertEquals([...tree.lvlValues()], [0, -2, 2, 1]);
values = [0, -2, 2, -3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [0, -2, -3, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2, -3]); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [0, -2, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [2, -2]); assertEquals([...tree.lvlValues()], [2, -2]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [0, 2]); assertEquals([...tree.lvlValues()], [0, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [0, -2]); assertEquals([...tree.lvlValues()], [0, -2]);
values = [0, -2, 2, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [0, -2, 2, 3]); assertEquals([...tree.lvlValues()], [0, -2, 2, 3]); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [0, -2, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [2, -2]); assertEquals([...tree.lvlValues()], [2, -2]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [0, 2]); assertEquals([...tree.lvlValues()], [0, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [0, -2]); assertEquals([...tree.lvlValues()], [0, -2]);
values = [0, -2, 2, -3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [0, -2, -3, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2, -3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-2, -3, 2]); assertEquals([...tree.lvlValues()], [-2, -3, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [0, -3, 2]); assertEquals([...tree.lvlValues()], [0, -3, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-2, -3, 0]); assertEquals([...tree.lvlValues()], [-2, -3, 0]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [0, -2, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2]);
values = [0, -2, 2, -1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [0, -2, -1, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2, -1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-1, -2, 2]); assertEquals([...tree.lvlValues()], [-1, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [0, -1, 2]); assertEquals([...tree.lvlValues()], [0, -1, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-1, -2, 0]); assertEquals([...tree.lvlValues()], [-1, -2, 0]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [0, -2, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2]);
values = [0, -2, 2, 1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [0, -2, 2, 1]); assertEquals([...tree.lvlValues()], [0, -2, 2, 1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [1, -2, 2]); assertEquals([...tree.lvlValues()], [1, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [1, 0, 2]); assertEquals([...tree.lvlValues()], [1, 0, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [0, -2, 1]); assertEquals([...tree.lvlValues()], [0, -2, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [0, -2, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2]);
values = [0, -2, 2, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [0, -2, 2, 3]); assertEquals([...tree.lvlValues()], [0, -2, 2, 3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [2, -2, 3]); assertEquals([...tree.lvlValues()], [2, -2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [2, 0, 3]); assertEquals([...tree.lvlValues()], [2, 0, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [0, -2, 3]); assertEquals([...tree.lvlValues()], [0, -2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [0, -2, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2]);});
Deno.test("[collections/RBTree] remove rebalance left", () => { let values = [4, 5, 0]; let tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, 0, 5]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [4, 5]);
values = [4, 5, 0, -1, 1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, 0, -1, 1, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -1, 1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [4, 1, -1, 5]); assertEquals([...tree.lvlValues()], [4, 1, 5, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [4, 0, 1, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [4, 0, -1, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -1]);
values = [4, 5, 0, -2, 2, -3, -1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, 0, -2, -3, -1, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, -3, -1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [4, -2, -3, 2, -1, 5]); assertEquals([...tree.lvlValues()], [4, -2, 5, -3, 2, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [4, 0, -1, -3, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -1, 2, -3]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [4, -2, -3, 0, -1, 5]); assertEquals([...tree.lvlValues()], [4, -2, 5, -3, 0, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [4, 0, -2, -1, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [4, 0, -2, -3, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, -3]);
values = [4, 5, 0, -2, 2, 1, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 1, 3, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, 1, 3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [4, 1, -2, 2, 3, 5]); assertEquals([...tree.lvlValues()], [4, 1, 5, -2, 2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [4, 2, 0, 1, 3, 5]); assertEquals([...tree.lvlValues()], [4, 2, 5, 0, 3, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 3, 1, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 3, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 3, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 1, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, 1]);
values = [4, 5, 0, -2, 2, -3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, 0, -2, -3, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, -3]); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [4, 2, -2, 5]); assertEquals([...tree.lvlValues()], [4, 2, 5, -2]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [4, 0, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals(tree.remove(4), true); assertEquals([...tree.nlrValues()], [0, -2, 5, 2]); assertEquals([...tree.lvlValues()], [0, -2, 5, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals(tree.remove(5), true); assertEquals([...tree.nlrValues()], [0, -2, 4, 2]); assertEquals([...tree.lvlValues()], [0, -2, 4, 2]);
values = [4, 5, 0, -2, 2, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 3, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, 3]); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [4, 2, -2, 5]); assertEquals([...tree.lvlValues()], [4, 2, 5, -2]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [4, 0, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals(tree.remove(4), true); assertEquals([...tree.nlrValues()], [0, -2, 5, 2]); assertEquals([...tree.lvlValues()], [0, -2, 5, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals(tree.remove(5), true); assertEquals([...tree.nlrValues()], [0, -2, 4, 2]); assertEquals([...tree.lvlValues()], [0, -2, 4, 2]);
values = [4, 5, 0, -2, 2, -3, -1, 1, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, 0, -2, -3, -1, 2, 1, 3, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, -3, -1, 1, 3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [4, 1, -2, -3, -1, 2, 3, 5]); assertEquals([...tree.lvlValues()], [4, 1, 5, -2, 2, -3, -1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [4, 0, -1, -3, 2, 1, 3, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -1, 2, -3, 1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [4, 0, -2, -3, -1, 3, 1, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 3, -3, -1, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [4, 0, -2, -1, 2, 1, 3, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, -1, 1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [4, 0, -2, -3, 2, 1, 3, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, -3, 1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [4, 0, -2, -3, -1, 2, 3, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, -3, -1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [4, 0, -2, -3, -1, 2, 1, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, -3, -1, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(4), true); assertEquals([...tree.nlrValues()], [0, -2, -3, -1, 2, 1, 5, 3]); assertEquals([...tree.lvlValues()], [0, -2, 2, -3, -1, 1, 5, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(5), true); assertEquals([...tree.nlrValues()], [0, -2, -3, -1, 2, 1, 4, 3]); assertEquals([...tree.lvlValues()], [0, -2, 2, -3, -1, 1, 4, 3]);
values = [4, 5, 0, -2, 2, -3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, 0, -2, -3, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, -3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [4, -2, -3, 2, 5]); assertEquals([...tree.lvlValues()], [4, -2, 5, -3, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [4, 0, -3, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -3, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [4, -2, -3, 0, 5]); assertEquals([...tree.lvlValues()], [4, -2, 5, -3, 0]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(4), true); assertEquals([...tree.nlrValues()], [0, -2, -3, 5, 2]); assertEquals([...tree.lvlValues()], [0, -2, 5, -3, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(5), true); assertEquals([...tree.nlrValues()], [0, -2, -3, 4, 2]); assertEquals([...tree.lvlValues()], [0, -2, 4, -3, 2]);
values = [4, 5, 0, -2, 2, -1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, 0, -2, -1, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, -1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [4, -1, -2, 2, 5]); assertEquals([...tree.lvlValues()], [4, -1, 5, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [4, 0, -1, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -1, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [4, -1, -2, 0, 5]); assertEquals([...tree.lvlValues()], [4, -1, 5, -2, 0]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(4), true); assertEquals([...tree.nlrValues()], [0, -2, -1, 5, 2]); assertEquals([...tree.lvlValues()], [0, -2, 5, -1, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(5), true); assertEquals([...tree.nlrValues()], [0, -2, -1, 4, 2]); assertEquals([...tree.lvlValues()], [0, -2, 4, -1, 2]);
values = [4, 5, 0, -2, 2, 1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 1, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, 1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [4, 1, -2, 2, 5]); assertEquals([...tree.lvlValues()], [4, 1, 5, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [4, 1, 0, 2, 5]); assertEquals([...tree.lvlValues()], [4, 1, 5, 0, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 1, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(4), true); assertEquals([...tree.nlrValues()], [0, -2, 2, 1, 5]); assertEquals([...tree.lvlValues()], [0, -2, 2, 1, 5]);
tree = RBTree.from(values); assertEquals(tree.remove(5), true); assertEquals([...tree.nlrValues()], [0, -2, 2, 1, 4]); assertEquals([...tree.lvlValues()], [0, -2, 2, 1, 4]);
values = [4, 5, 0, -2, 2, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 3, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2, 3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [4, 2, -2, 3, 5]); assertEquals([...tree.lvlValues()], [4, 2, 5, -2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [4, 2, 0, 3, 5]); assertEquals([...tree.lvlValues()], [4, 2, 5, 0, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 3, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [4, 0, -2, 2, 5]); assertEquals([...tree.lvlValues()], [4, 0, 5, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(4), true); assertEquals([...tree.nlrValues()], [0, -2, 3, 2, 5]); assertEquals([...tree.lvlValues()], [0, -2, 3, 2, 5]);
tree = RBTree.from(values); assertEquals(tree.remove(5), true); assertEquals([...tree.nlrValues()], [0, -2, 3, 2, 4]); assertEquals([...tree.lvlValues()], [0, -2, 3, 2, 4]);});
Deno.test("[collections/RBTree] remove rebalance right", () => { let values = [-4, -5, 0]; let tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -5, 0]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-4, -5]);
values = [-4, -5, 0, -1, 1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -5, 0, -1, 1]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -1, 1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-4, -5, 1, -1]); assertEquals([...tree.lvlValues()], [-4, -5, 1, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, 1]); assertEquals([...tree.lvlValues()], [-4, -5, 0, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -1]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -1]);
values = [-4, -5, 0, -2, 2, -3, -1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -3, -1, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, -3, -1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-4, -5, -2, -3, 2, -1]); assertEquals([...tree.lvlValues()], [-4, -5, -2, -3, 2, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -1, -3, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -1, 2, -3]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-4, -5, -2, -3, 0, -1]); assertEquals([...tree.lvlValues()], [-4, -5, -2, -3, 0, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -1, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, -1]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -3, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, -3]);
values = [-4, -5, 0, -2, 2, 1, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2, 1, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, 1, 3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-4, -5, 1, -2, 2, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 1, -2, 2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [-4, -5, 2, 0, 1, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 2, 0, 3, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 3, 1]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 3, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2, 1]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, 1]);
values = [-4, -5, 0, -2, 2, -3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -3, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, -3]); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-4, -5, 2, -2]); assertEquals([...tree.lvlValues()], [-4, -5, 2, -2]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals(tree.remove(-4), true); assertEquals([...tree.nlrValues()], [-2, -5, 0, 2]); assertEquals([...tree.lvlValues()], [-2, -5, 0, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals(tree.remove(-5), true); assertEquals([...tree.nlrValues()], [0, -4, -2, 2]); assertEquals([...tree.lvlValues()], [0, -4, 2, -2]);
values = [-4, -5, 0, -2, 2, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, 3]); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-4, -5, 2, -2]); assertEquals([...tree.lvlValues()], [-4, -5, 2, -2]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals(tree.remove(-4), true); assertEquals([...tree.nlrValues()], [-2, -5, 0, 2]); assertEquals([...tree.lvlValues()], [-2, -5, 0, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals(tree.remove(-5), true); assertEquals([...tree.nlrValues()], [0, -4, -2, 2]); assertEquals([...tree.lvlValues()], [0, -4, 2, -2]);
values = [-4, -5, 0, -2, 2, -3, -1, 1, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -3, -1, 2, 1, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, -3, -1, 1, 3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-4, -5, 1, -2, -3, -1, 2, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 1, -2, 2, -3, -1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -1, -3, 2, 1, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -1, 2, -3, 1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -3, -1, 3, 1]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 3, -3, -1, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -1, 2, 1, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, -1, 1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -3, 2, 1, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, -3, 1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -3, -1, 2, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, -3, -1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -3, -1, 2, 1]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, -3, -1, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(-4), true); assertEquals([...tree.nlrValues()], [-3, -5, 0, -2, -1, 2, 1, 3]); assertEquals([...tree.lvlValues()], [-3, -5, 0, -2, 2, -1, 1, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-5), true); assertEquals([...tree.nlrValues()], [0, -2, -4, -3, -1, 2, 1, 3]); assertEquals([...tree.lvlValues()], [0, -2, 2, -4, -1, 1, 3, -3]);
values = [-4, -5, 0, -2, 2, -3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -3, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, -3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-4, -5, -2, -3, 2]); assertEquals([...tree.lvlValues()], [-4, -5, -2, -3, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -3, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -3, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-4, -5, -2, -3, 0]); assertEquals([...tree.lvlValues()], [-4, -5, -2, -3, 0]);
tree = RBTree.from(values); assertEquals(tree.remove(-3), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-4), true); assertEquals([...tree.nlrValues()], [-3, -5, 0, -2, 2]); assertEquals([...tree.lvlValues()], [-3, -5, 0, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-5), true); assertEquals([...tree.nlrValues()], [0, -3, -4, -2, 2]); assertEquals([...tree.lvlValues()], [0, -3, 2, -4, -2]);
values = [-4, -5, 0, -2, 2, -1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, -1, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, -1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-4, -5, -1, -2, 2]); assertEquals([...tree.lvlValues()], [-4, -5, -1, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -1, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -1, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-4, -5, -1, -2, 0]); assertEquals([...tree.lvlValues()], [-4, -5, -1, -2, 0]);
tree = RBTree.from(values); assertEquals(tree.remove(-1), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-4), true); assertEquals([...tree.nlrValues()], [-2, -5, 0, -1, 2]); assertEquals([...tree.lvlValues()], [-2, -5, 0, -1, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-5), true); assertEquals([...tree.nlrValues()], [0, -2, -4, -1, 2]); assertEquals([...tree.lvlValues()], [0, -2, 2, -4, -1]);
values = [-4, -5, 0, -2, 2, 1]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2, 1]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, 1]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-4, -5, 1, -2, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 1, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [-4, -5, 1, 0, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 1, 0, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 1]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 1]);
tree = RBTree.from(values); assertEquals(tree.remove(1), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-4), true); assertEquals([...tree.nlrValues()], [-2, -5, 1, 0, 2]); assertEquals([...tree.lvlValues()], [-2, -5, 1, 0, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-5), true); assertEquals([...tree.nlrValues()], [0, -4, -2, 2, 1]); assertEquals([...tree.lvlValues()], [0, -4, 2, -2, 1]);
values = [-4, -5, 0, -2, 2, 3]; tree = RBTree.from(values); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2, 3]); assertEquals(tree.remove(0), true); assertEquals([...tree.nlrValues()], [-4, -5, 2, -2, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 2, -2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-2), true); assertEquals([...tree.nlrValues()], [-4, -5, 2, 0, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 2, 0, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(2), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 3]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(3), true); assertEquals([...tree.nlrValues()], [-4, -5, 0, -2, 2]); assertEquals([...tree.lvlValues()], [-4, -5, 0, -2, 2]);
tree = RBTree.from(values); assertEquals(tree.remove(-4), true); assertEquals([...tree.nlrValues()], [-2, -5, 2, 0, 3]); assertEquals([...tree.lvlValues()], [-2, -5, 2, 0, 3]);
tree = RBTree.from(values); assertEquals(tree.remove(-5), true); assertEquals([...tree.nlrValues()], [0, -4, -2, 2, 3]); assertEquals([...tree.lvlValues()], [0, -4, 2, -2, 3]);});
Deno.test("[collections/RBTree] README example", () => { const values = [3, 10, 13, 4, 6, 7, 1, 14]; const tree = new RBTree<number>(); values.forEach((value) => tree.insert(value)); assertEquals([...tree], [1, 3, 4, 6, 7, 10, 13, 14]); assertEquals(tree.min(), 1); assertEquals(tree.max(), 14); assertEquals(tree.find(42), null); assertEquals(tree.find(7), 7); assertEquals(tree.remove(42), false); assertEquals(tree.remove(7), true); assertEquals([...tree], [1, 3, 4, 6, 10, 13, 14]);
const invertedTree = new RBTree<number>(descend); values.forEach((value) => invertedTree.insert(value)); assertEquals([...invertedTree], [14, 13, 10, 7, 6, 4, 3, 1]); assertEquals(invertedTree.min(), 14); assertEquals(invertedTree.max(), 1); assertEquals(invertedTree.find(42), null); assertEquals(invertedTree.find(7), 7); assertEquals(invertedTree.remove(42), false); assertEquals(invertedTree.remove(7), true); assertEquals([...invertedTree], [14, 13, 10, 6, 4, 3, 1]);
const words = new RBTree<string>((a, b) => ascend(a.length, b.length) || ascend(a, b) ); ["truck", "car", "helicopter", "tank", "train", "suv", "semi", "van"] .forEach((value) => words.insert(value)); assertEquals([...words], [ "car", "suv", "van", "semi", "tank", "train", "truck", "helicopter", ]); assertEquals(words.min(), "car"); assertEquals(words.max(), "helicopter"); assertEquals(words.find("scooter"), null); assertEquals(words.find("tank"), "tank"); assertEquals(words.remove("scooter"), false); assertEquals(words.remove("tank"), true); assertEquals([...words], [ "car", "suv", "van", "semi", "train", "truck", "helicopter", ]);});