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);
}

1 komentářů:

  1. Anonymní ... (7. listopadu 2010 v 12:58)

    Skvele. Vyborna ukazka dovednosti AS.

Okomentovat