Binary Search Tree in AS3

In this article we implement a binary search tree in ActionScript 3. We will create a class and add some basic methods. At the end we create an algorithm to draw it.

fullscreen version

What is Binary Search Tree?

BST is a dynamic data structure, whicht contains a set of comparable items (numbers, words) and if it is well-balanced, it allows us to operate with these words or numbers very fast (aproximately $O(log(n))$). You can find more information in article on Wikipedia.

Node class

What do I want from my tree

I want to be able to create the tree easily (var tree = new ...), be able to add new numbers (tree.Add(24);). I want to be able to detect, whether my tree contains some exact number ( if(tree.Contains(24)) ... ). I want to have some text output of tree data (trace(tree.toString());).

Node data

Every number is located in some node, on the left are smaller numbers, bigger numbers on the right. Each node defines the tree, which is under it.

Node Class in ActionScript 3

package
{
   public class Node
   {
      public var left:Node;      // left child
      public var right:Node;    // right child
      public var value:int = int.MAX_VALUE;   // value in node
   }
}

Constructor

The parameter of constructor is number, which we save into node.

public function Node(c:int):void
{
   value = c;
}

Adding the number into a tree

If the value is already in the node, we don't add anything. If it is smaller, we add it to the left node, if bigger - to the right one.

public function Add(c:int)
{
   if(c == value){return; }
   if(c > value)
   {
      if (right != null) right.Add(c);
      else right = new Node(c);
   }
   else
   {
      if (left != null) left.Add(c);
      else left = new Node(c);
   }
}

Detect a number in a structure

At first we check, whether the value is in current node. If not, we check in left (smaller) or in right (bigger) node.

public function Contains(c:int):Boolean
{
   if(c == value) return true;
   if(c < value) 
   {
      if(left != null) return left.Contains(c);
      else return false;
   }
   else 
   {
      if(right != null) return right.Contains(c);
      else return false;
   }
}

Text output of a tree

When we want to make a text output of the current node, we make a text output of the left node, add a number in the current node, and then add the output of the right node.

public function toString():String
{
   var out:String = "";
   
   if(left != null) out += left.toString();
   out += value + ", ";
   if(right != null) out += right.toString();
   
   return out;
}

Other methods

We often need a remove method in BST (you can write it up). Functions for balancing a tree are also very useful (we don't have long branches - we don't have to go to deep when searching numbers). There are many sets of rules to balance a BST, for example AVL tree or Red-black tree.

Using the class

Let's add some numbers into tree and write it out. We start with creating the first node, which will be the root, with some number in it, and then we add some other numbers to it.

function vav(e:MouseEvent):void
{
   var tree:Node = new Node(2);
   txt.text="Adding:\n";
   for(var i:int=0; i<15; i++) 
   {
      var num:int = Math.round(Math.random()*100)-50;
      tree.Add(num);
      txt.appendText(num + ", ");
   }
   txt.appendText("\nSorted:\n" + tree.toString());
   txt.appendText("\nContains -5: " + tree.Contains(-5));
   txt.appendText("\nContains 10: " + tree.Contains(10));
}

Drawing a tree

Let's write a recursive function for drawing a tree.

// u:node to draw; x, y: position; w:width of the tree; place: a sprite to draw in
function draw(u:Node, x:int, y:int, w:int, place:Sprite)
{
   // when there is a left child
   if(u.left != null)
   {
      // draw a line to it
      with(place.graphics)
      {
         lineStyle(6,0x00E1FF);
         moveTo(x, y);
         lineTo(x-w/4, y+60);
      }
      // draw a child
      draw(u.left, x-w/4, y+60, w/2, place); 
   }
   // when there is a right child ...
   if(u.right != null)
   {
      with(place.graphics)
      {
         lineStyle(6,0x91FF00);
         moveTo(x, y);
         lineTo(x+w/4, y+60);
      }
      draw(u.right, x+w/4, y+60, w/2, place); 
   }
   // draw a round for this node
   with(place.graphics)
   {
      lineStyle(4, 0x6D00D9);
      beginFill(0xff005E);
      drawEllipse(x-20, y-20, 40, 40);
      endFill();
   }
   // add a text field with the number
   var tf:TextField = new TextField();
   tf.text = u.value.toString();
   tf.x = x-tf.textWidth;
   tf.y = y-14;
   place.addChild(tf);
}

Old comments (closed because of spam)

24 Comments

  1. kim said:

    How to start step1.I do not understand.Please describe for the first step.thank you.

    January 31st, 2011
  2. Ivan Kuckir said:

    If you have a class, then in the first step you create a root of a tree.

    var root:Node = new Node(4);
    

    Then you can add some numbers

    root.Add(67); root.Add(-15); root.Add(41); //...
    
    January 31st, 2011
  3. kim said:

    5000: The class ‘Node’ must subclass ‘flash.display.MovieClip’ since it is linked to a library symbol of that type.?

    January 31st, 2011
  4. Ivan Kuckir said:

    No, Node is not subclass of anything, it is subclass of “Object”. It is not linked to any symbol. It is just small class that contains integer value and two pointers.

    January 31st, 2011
  5. kim said:

    thank you so

    January 31st, 2011
  6. kim said:

    I’m not good on the language.I just started to study for the project. It is very difficult for me. Must learn from books and web site link. I have no knowledge of this matter at all. Everything to a new study out. So I really understand what you are trying to say too much. And thank you a lot of help.Could you give me examples. If you please, it really hard for me because everything I’ve studied from the beginning.

    January 31st, 2011
  7. kim said:

    Sorry to disturb you time.

    January 31st, 2011
  8. kim said:

    I would like to buy a Binary Search Tree in AS3, please give me your tired my answers.

    February 2nd, 2011
  9. Ivan Kuckir said:

    Hi Kim, I am not sure if I fully understand what you want. The main code is written above, if you want something more, please give me your e-mail address, so we can talk over it.

    February 2nd, 2011
  10. kim said:

    Thanks Ivan is my e-mail.Qafter_chin@hotmail.com. If you are comfortable in the field wherever you can tell me.

    February 2nd, 2011
  11. kim said:

    Hi, Ivan
    I’ll buy you a price of 15 $ for binary tree, but it is my brother’s account. You will also know how it is paid by me. It is not over today, I would buy your work. Please answer too.

    March 18th, 2011
  12. sovik said:

    Hello!
    How to make remove Node of valued?
    Thank you!

    May 4th, 2011
  13. Ivan Kuckir said:

    to sovik:
    There is an algorithm for removing a child.

    If it’s a leaf, just remove it.
    If it has one child, replace it by this child (child can be a subtree).
    If not, replace it with the minimum of the right subtree, or the maximum of left subtree.
    Minimums and maximums are always leaves or have only one child, guess why? :)
    article on Wikipedia

    August 14th, 2011
  14. Fernando Zucula said:

    Thanks and congratulations guy.
    I loved you lesson, easy and simply.

    June 12th, 2012
  15. Arjey said:

    Hello, Ivan! Can you provide a download link? I’ll be using it in our project as an interactive exercise in Binary Trees. Don’t worry. I’ll make sure that you’ll get all the credit because I’ll put this page as our reference. :D

    September 20th, 2012
  16. Ivan Kuckir said:

    Hi Arjey, I added a link to fullscreen version. You can show it right from the browser, or press File -> Save in your browser to save the SWF file.

    September 20th, 2012
  17. Arjey said:

    Thank you very much for the immediate reply, Ivan. Highly appreciated. Can you also provide the .fla file for this? If it’s okay with you.

    September 21st, 2012
  18. Ivan Kuckir said:

    Hello, I am providing all the code you can see on the webpage. If you want any additional code, I can send it to you when you make a Donation. Please read the column on the right side of this webpage.

    September 21st, 2012
  19. mak said:

    Hello, Thank you for this great tutorial which is very helpful. can you please make a tutorial in deletion and searching as well ?

    February 13th, 2013
  20. mfdjf said:

    can u creta a binary search tree and binary tree for the foloowin numbers 18,25,9,15,23,8,24,17,3

    March 31st, 2013
  21. alex said:

    Hi Ivan, where are you “activating” de Draw Function? I try implementing it into my code for a simple binary tree but it doesn’t show graphically. Thank You!

    May 8th, 2013
  22. Ivan Kuckir said:

    You should call “draw” function with tree root. E.g. draw(root, 200, 0, 400, mySprite); . If you made a donation (15$ or more), I can send you my complete code. Just write me an email.

    May 8th, 2013
  23. đức said:

    you can give yourself the full code. thank you

    November 6th, 2013
  24. Andy said:

    If anyone is interested in a Javascript dynamic (balanced) binary tree, you can get the source code here: http://www.aplweb.co.uk/experiments/js/AATree.js

    There is also a pointer-less version (allows you to store huge amounts of data at the compromise of a little speed). Get it here: http://www.aplweb.co.uk/experiments/js/LinklessAATree.js

    Enjoy.

    December 30th, 2013