Binární vyhledávací strom v AS3
V tomto článku si ukážeme konkrétní příklad použití OOP ve flashi. Implementujeme si binární vyhledávací strom v AS3 a jeho základní metody. Nakonec ho zkusíme ještě vykreslit.
Co je to Binární vyhledávací strom?
BVS (binární vyhledávací strom), anglicky BST (binary search tree) je dynamická datová struktura, která obsahuje množinu porovnatelných prvků (čísla, slova) a pokud je dobře vyvážený, umožňuje rychlé operace s nimi (v logaritmickém čase - $O(log(n))$. Podrobný popis v článku na Wikipedii.Třída Uzel
Co od stromu chci
Chci, abych si strom mohl snadno vytvořit (var strom = new ...), mohl do něj snadno přidávat další čísla (strom.Přidej(24);). Chci mít možnost zjišťovat, zda nějaké číslo je ve stromě (if(strom.Obsahuje(24)) ...). Také chci snadno vypisovat jeho obsah (trace(strom.toString());)Data v uzlu
Každé číslo bude ležet v uzlu, vlevo budou čísla menší, vpravo větší. Každý uzel zároveň definuje strom, který je pod ním.Základní třída
package { public class Uzel { public var levý:Uzel; // uzel vlevo public var pravý:Uzel; // uzel vpravo public var hodnota:int = int.MAX_VALUE; // hodnota v uzlu } }
Konstruktor
Jeho parametr je číslo, které sem ukládáme. Pokud nebude uveden, hodnota v uzlu je int.MAX_VALUE.public function Uzel(c:int = int.MAX_VALUE):void { if(c == int.MAX_VALUE) return; // bez parametru -> vrátíme se hodnota = c; // jinak přiřadíme parametr do hodnoty }
Přidání čísla do struktury
je velmi snadné. Pokud daná hodnota už je v uzlu, neděláme nic. Pokud přidáváme menší číslo než hodnota v uzlu, přidáme ho do levého podstromu, jinak do pravého.public function Přidej(c:int) { if(hodnota == int.MAX_VALUE) { hodnota = c; return;} // konstruktor byl bez parametru if(c == hodnota){return; } // c už tu je if(c > hodnota) { if (pravý != null) pravý.Přidej(c); else pravý = new Uzel(c); } else { if (levý != null) levý.Přidej(c); else levý = new Uzel(c); } }
Zjištění, zda číslo už je ve struktuře
je také snadné. Podíváme se, zda je v daném uzlu, pokud je menší než hodnota v uzlu, hledáme ho v levém podstromu, jinak v pravém.public function Obsahuje(i:int):Boolean { if(i == hodnota) return true; if(i < hodnota) { if(levý != null) return levý.Obsahuje(i); else return false; } else { if(pravý != null) return pravý.Obsahuje(i); else return false; } }
Vypsání čísel ve struktuře - seřazeně
Obsah stromu vypíšeme velmi snadno. Nejdříve vypíšeme levý podstrom, pak vypíšeme hodnotu v tomto uzlu tolikrát, kolikrát tu je, potom pravý podstrom.public function toString():String { var out:String = ""; if(levý != null) out += levý.toString(); out += hodnota + ", "; if(pravý != null) out += pravý.toString(); return out; }
Další funkce
Další funkce, které by měl BVS umět, je odebrání prvku (můžete doprogramovat). Velmi užitečné jsou funkce pro vyvažování (aby strom byl symetrický a neměl dlouhé větve, kdy musíme chodit příliš hluboko). To často obnáší úpravu funkcí pro přidávání a odebírání prvku. Pravidla pro toto vyvažování jsou např. AVL strom nebo Červeno-černý strom.Použití třídy
Zkusme si do stromu naházet nějaké hodnoty a pak ho vypsat.btn.addEventListener(MouseEvent.MOUSE_DOWN, vav); function vav(e:MouseEvent):void { var strom:Uzel = new Uzel(); txt.text = "Přídáváme:\n"; for(var i:int = 0; i < 15; i++) { var číslo:int = Math.round(Math.random()*100)-50; strom.Přidej(číslo); txt.appendText(číslo + ", "); } txt.appendText("\nSeřazené:\n" + strom.toString()); txt.appendText("\nObsahuje -5: " + strom.Obsahuje(-5)); txt.appendText("\nObsahuje 10: " + strom.Obsahuje(10)); }
Vykreslení stromu
Napišme si funkci pro rekurzivní vykreslení stromu.function vykresli(u:Uzel, x:int, y:int, šířka:int, místo:Sprite) { //--- když uzel má levého syna if(u.levý != null) { //--- nakreslíme k němu čáru with(místo.graphics) { lineStyle(6,0x00E1FF); moveTo(x, y); lineTo(x - šířka/4, y + 70); } //--- a vykreslíme syna vykresli(u.levý, x - šířka/4, y + 70, šířka/2, místo); } //--- když má pravého, to samé if(u.pravý != null) { with(místo.graphics) { lineStyle(6,0x91FF00); moveTo(x, y); lineTo(x + šířka/4, y + 70); } vykresli(u.pravý, x + šířka/4, y + 70, šířka/2, místo); } //--- nakreslíme kroužek pro tento uzel with(místo.graphics) { lineStyle(4, 0x6D00D9); beginFill(0xff005E); drawEllipse(x - 23 - i*4, y - 23 - i*4, 46, 46); endFill(); } //--- přidáme textové pole s číslem var tf:TextField = new TextField(); tf.text = u.hodnota.toString(); tf.x = x-tf.textWidth-2; tf.y = y-16; tf.setTextFormat(tfo); místo.addChild(tf); }
Skvele. Vyborna ukazka dovednosti AS.