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 versionWhat 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); }
How to start step1.I do not understand.Please describe for the first step.thank you.
January 31st, 2011If you have a class, then in the first step you create a root of a tree.
Then you can add some numbers
January 31st, 20115000: The class ‘Node’ must subclass ‘flash.display.MovieClip’ since it is linked to a library symbol of that type.?
January 31st, 2011No, 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, 2011thank you so
January 31st, 2011I’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, 2011Sorry to disturb you time.
January 31st, 2011I would like to buy a Binary Search Tree in AS3, please give me your tired my answers.
February 2nd, 2011Hi 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, 2011Thanks Ivan is my e-mail.Qafter_chin@hotmail.com. If you are comfortable in the field wherever you can tell me.
February 2nd, 2011Hi, Ivan
March 18th, 2011I’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.
Hello!
May 4th, 2011How to make remove Node of valued?
Thank you!
to sovik:
There is an algorithm for removing a child.
If it’s a leaf, just remove it.
August 14th, 2011If 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
Thanks and congratulations guy.
June 12th, 2012I loved you lesson, easy and simply.
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.
September 20th, 2012Hi 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, 2012Thank 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, 2012Hello, 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, 2012Hello, Thank you for this great tutorial which is very helpful. can you please make a tutorial in deletion and searching as well ?
February 13th, 2013can u creta a binary search tree and binary tree for the foloowin numbers 18,25,9,15,23,8,24,17,3
March 31st, 2013Hi 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, 2013You 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, 2013you can give yourself the full code. thank you
November 6th, 2013If 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