A Flash Developer Resource Site

Results 1 to 10 of 10

Thread: Red-Black Tree Implementation in AS3

  1. #1
    Member
    Join Date
    Aug 2007
    Posts
    61

    Red-Black Tree Implementation in AS3

    Anybody have, or know of an implementation of this in AS3? Maybe not the right forum to ask in but on the other hand the people most likely to have needed might be here.

  2. #2
    Senior Member rachil0's Avatar
    Join Date
    Jul 2007
    Location
    Columbus, OH.
    Posts
    465
    Darn, I came in here hoping that you were posting your implementation, which I would then swipe with an audible "yoink".

    If you have Cormen et al I would just translate their pseudocode and run with it, I have never had a problem arise with code copied from them. (Actually, I would first ask myself if a heap would suffice instead of r/b tree, but if you know enough to ask this question to begin with, you've probably already thought that part through).

  3. #3
    Member
    Join Date
    Aug 2007
    Posts
    61
    You got a heap implementation in AS3 then?

    The balancing is important but I can live without it for now. Actually does anybody know what the built in Dictionary class uses?

  4. #4
    SaphuA SaphuA's Avatar
    Join Date
    Oct 2002
    Location
    The Netherlands
    Posts
    2,182
    Don't realy know which datastructures they/he/she have/has made, but is this of any help?
    http://lab.polygonal.de/category/data-structures/

  5. #5
    Senior Member
    Join Date
    Jan 2006
    Location
    USA
    Posts
    383
    I have an implementation in Java.

    I've thought about building one in AS3. If I do, I can let you know. Might tonight for the hell of it, actually.

  6. #6
    Junior Member
    Join Date
    Jun 2008
    Posts
    2
    I spent a couple of hours translating the code I found here: http://web.mit.edu/~emin/www/source_...ees/index.html

    Code:
    package RBTree {
      public class NodeInt {
        public var left:NodeInt;
        public var right:NodeInt;
        public var parent:NodeInt;
        public var red:int;
    
        // setting the key to type '*' is twice as slow
        public var key:int;   
        public var data:*;
    
        public function NodeInt( key:int=0, data:*=null ) {
          this.key = key;
          this.data = data;
        }
    
      }
    }
    Code:
    package RBTree {
      public class TreeInt {
        public var root:NodeInt;
        public var nil:NodeInt;
    
        public function TreeInt() {
          nil = new NodeInt();
          nil.left = nil;
          nil.right = nil;
          nil.parent = nil;
          nil.red = 0;
    
          root = new NodeInt();
          root.left = nil;
          root.right = nil;
          root.parent = nil;
          root.red = 0;
        }
    
        public function Delete( z:NodeInt ):void {
          var x:NodeInt;
          var y:NodeInt;
    
          y = ( (z.left == nil) || (z.right == nil) ) ? z : Next( z );
          x = (y.left == nil) ? y.right : y.left;
    
          if( root == (x.parent = y.parent) ) {
            root.left = x;
          } else {
            if( y == y.parent.left ) {
              y.parent.left = x;
            } else {
              y.parent.right = x;
            }
          }
    
          if( y != z ) {
            y.left = z.left;
            y.right = z.right;
            y.parent = z.parent;
            z.left.parent = z.right.parent = y;
            if( z == z.parent.left ) {
              z.parent.left = y;
            } else {
              z.parent.right = y;
            }
            if( y.red == 0 ) {
              y.red = z.red;
              DeleteFixUp( x );
            } else {
              y.red = z.red;
            }
          } else {
            if( y.red == 0 ) DeleteFixUp( x );
          }
        }
    
        public function Insert( z:NodeInt ) {
          var x:NodeInt;
          var y:NodeInt;
    
          z.left = z.right = nil;
    
          // ordinary binary tree insert
          y = root;
          x = root.left;
          while( x != nil ) {
            y = x;
            if( x.key > z.key ) {
              x = x.left;
            /* Not sure what to do about duplicate keys
            } else if( x.key < z.key ) {
              x = x.right;
            */
            } else {
              x = x.right;
            }
          }
          z.parent = y;
          if( ( y == root ) || ( y.key > z.key ) ) {
            y.left = z;
          } else {
            y.right = z;
          }
    
          x = z;
          x.red = 1;
          while( x.parent.red ) {
            if( x.parent == x.parent.parent.left ) {
              y = x.parent.parent.right;
              if( y.red ) {
                y.red = 0;
                x.parent.red = 0;
                x.parent.parent.red = 1;
                x = x.parent.parent;
              } else {
                if( x == x.parent.right ) {
                  x = x.parent;
                  LeftRotate( x );
                }
                x.parent.red = 0;
                x.parent.parent.red = 1;
                RightRotate( x.parent.parent );
              }
            } else {
              y = x.parent.parent.left;
              if( y.red ) {
                y.red = 0;
                x.parent.red = 0;
                x.parent.parent.red = 1;
                x = x.parent.parent;
              } else {
                if( x == x.parent.left ) {
                  x = x.parent;
                  RightRotate( x );
                }
                x.parent.red = 0;
                x.parent.parent.red = 1;
                LeftRotate( x.parent.parent );
              }
            }
          }
          root.left.red = 0;
          return( z );
        } // Insert()
    
        public function Next( x:NodeInt ):NodeInt {
          var y:NodeInt = x.right;
    
          if( y != nil ) {
            while( y.left != nil ) y = y.left;
            return( y );
          }
          // else
          y = x.parent;
          while( x == y.right ) {
            x = y;
            y = y.parent;
          }
          if( y == root ) return( nil );
          return( y );
        }
    
        public function Prev( x:NodeInt ):NodeInt {
          var y:NodeInt = x.left;
          
          if( y != nil ) {
            while( y.right != nil ) y = y.right;
            return( y );
          }
          // else
          y = x.parent;
          while( x == y.left ) {
            if( y == root ) return( nil );
            x = y;
            y = y.parent;
          }
          return( y );
        }
    
        public function Find( key:int ):NodeInt {
          var x:NodeInt = root.left;
    
          while( x != nil ) {
            if( key < x.key ) x = x.left;
            else if( key > x.key ) x = x.right;
            else return( x );
          }
          return( null );
        }
    
        public function FindRange( low:int, high:int ):Array {
          var ret:Array = new Array();
          var x:NodeInt = root.left;
          var lastBest:NodeInt = nil;
    
          while( x != nil ) {
            if( x.key > high ) {
              x = x.left;
            } else {
              lastBest = x;
              x = x.right;
            }
          }
          while( (lastBest != nil) && (low <= lastBest.key) ) {
            ret.push( lastBest );
            lastBest = Prev( lastBest );
          }
          return( ret );
        }
    
        private function LeftRotate( x:NodeInt ):void {
          var y:NodeInt;
    
          y = x.right;
          x.right = y.left;
    
          if( y.left != nil ) y.left.parent = x;
          y.parent = x.parent;
    
          if( x == x.parent.left ) {
            x.parent.left = y;
          } else {
            x.parent.right = y;
          }
          y.left = x;
          x.parent = y;
        }
    
        private function RightRotate( y:NodeInt ):void {
          var x:NodeInt;
    
          x = y.left;
          y.left = x.right;
    
          if( x.right != nil ) x.right.parent = y;
    
          x.parent = y.parent;
          if( y == y.parent.left ) {
            y.parent.left = x;
          } else {
            y.parent.right = x;
          }
    
          x.right = y;
          y.parent = x;
        }
    
        private function DeleteFixUp( x:NodeInt ):void {
          var w:NodeInt;
          var rootLeft:NodeInt = root.left;
    
          while( (x.red == 0) && (x != rootLeft) ) {
            if( x == x.parent.left ) {
              w = x.parent.right;
              if( w.red ) {
                w.red = 0;
                x.parent.red = 1;
                LeftRotate( x.parent );
                w = x.parent.right;
              }
              if( (w.right.red == 0) && (w.left.red == 0) ) {
                w.red = 1;
                x = x.parent;
              } else {
                if( w.right.red == 0 ) {
                  w.left.red = 0;
                  w.red = 1;
                  RightRotate( w );
                  w = x.parent.right;
                }
                w.red = x.parent.red;
                x.parent.red = 0;
                w.right.red = 0;
                LeftRotate( x.parent );
                x = rootLeft; // this is to exit while loop
              }
            } else {
              // same as above but with left and right switched
              w = x.parent.left;
              if( w.red ) {
                w.red = 0;
                x.parent.red = 1;
                RightRotate( x.parent );
                w = x.parent.left;
              }
              if( (w.right.red == 0) && (w.left.red == 0) ) {
                w.red = 1;
                x = x.parent;
              } else {
                if( w.left.red == 0 ) {
                  w.right.red = 0;
                  w.red = 1;
                  LeftRotate( w );
                  w = x.parent.left;
                }
                w.red = x.parent.red;
                x.parent.red = 0;
                w.left.red = 0;
                RightRotate( x.parent );
                x = rootLeft; // this is to exit while loop
              }
            }
          }
          x.red = 0;
        } // DeleteFixUp
      }
    }

  7. #7
    Member
    Join Date
    Aug 2007
    Posts
    61
    Great! I was just thinking of coming back to this...

    Now for some benchmarking....

  8. #8
    Knows where you live
    Join Date
    Oct 2004
    Posts
    944
    I find that in most cases its incredibly hard to beat flashes built in data structures because they are implemented natively. Your best bet is changing the way you access them, such as binary trees built on top of an array.
    The greatest pleasure in life is doing what people say you cannot do.
    - Walter Bagehot
    The height of cleverness is to be able to conceal it.
    - Francois de La Rochefoucauld

  9. #9
    Junior Member
    Join Date
    Jun 2008
    Posts
    10
    Quote Originally Posted by 691175002
    I find that in most cases its incredibly hard to beat flashes built in data structures because they are implemented natively.
    I think it depends entirely on your usage, but it really isn't hard to beat array performance:

    http://www.newgrounds.com/bbs/topic/906548

  10. #10
    Junior Member
    Join Date
    Jun 2008
    Posts
    2
    Performance very much depends on the usage. In my benchmarks I found that for storing strings, an object is very good up until 30,000 entries and then it becomes the same speed as using an RBTreeString. Perhaps it was using a hash table until it reached 2^15 entries?

    Inserted strings ""+i for i=0..N, then queried for same strings in same order:

    Code:
    Object:
          //      N : ms per query
          // 500000 : 0.002362
          // 100000 : 0.0032
          //  50000 : 0.00294
          //  40000 : 0.002975
          //  30000 : 0.00087
          //  20000 : 0.00092
          //  10000 : 0.00093
          //   1000 : 0.00072
    
    RBTreeString:
          // 500000 : 0.0039
          // 100000 : 0.0031
          //  10000 : 0.0024
    Somewhere between 30k and 40k strings, the object query time goes way up.

    Array indexes are lightning fast. Unfortunately that's all they're good for. Finding an item is slow unless the array is sorted, which is what balanced binary trees are for.

    Inserting ints 1..N and then querying (data = array[i]) for same ints in same order:

    Code:
    Array:
          // (generally too small to measure)
          // 100000 : 0.000017
          //  10000 : 0.00001
          //   1000 : 0.00002
    
    RBTreeInt:
          // 100000 : 0.000362
          //  10000 : 0.0003
    In both cases, inserting into an RBTree is slower than querying, obviously.
    Code:
    RB insert int:
          // 100000 : 0.00156
    RB insert string:
          // 100000 : 0.00495
    Which illustrates the time penalty for constructing and comparing strings vs ints. All these benchmarks were obtained by running variants of this example function:

    Code:
        private var testTreeString:TreeString;
        private var keyCount:int = 500000;
    
        function runTree4():Number {
          // 500000 : 0.0039
          // 100000 : 0.0031
          //  10000 : 0.0024
          var loopCount:int = keyCount;
          var iterCount:int = 1;
          var time:Number = getTimer();
          var node:NodeString;
          for( var iter:int = 0; iter < iterCount; iter++ ) {
            for( var i:int = 0; i < loopCount; i++ ) {
              node = testTreeString.Find( ""+i );
              if( node == null || node.data != (1000000 + i) ) {
                trace( "Error finding "+i );
                i = loopCount;
                iter = iterCount;
              }
            }
          }
          return( (getTimer() - time) / loopCount / iterCount );
        }
    
        function runTree3():Number {
          // 100000 : 0.00495
          testTreeString = new TreeString();
          var loopCount:int = keyCount;
          var iterCount:int = 1;
          var time:Number = getTimer();
          for( var iter:int = 0; iter < iterCount; iter++ ) {
            for( var i:int = 0; i < loopCount; i++ ) {
              testTreeString.Insert( new NodeString( ""+i, 1000000 + i ) );
            }
          }
          return( (getTimer() - time) / loopCount / iterCount );
        }
    I run runTree3() once, then runTree4() twenty times and record the minimum. That's probably the most important thing in benchmarking: run multiple times and report the minimum, not the average. This is the best way to prune out the overhead in a shared-time operating system. The more runs the better, but twenty is pushing the 15s executing limit. Then I execute the whole program a few times and record that minimum. Chasing the minimum has busted some myths I've seen regarding the speed of "x++" vs "x = x + 1" for example (there is no speed difference between those two by the way).
    Last edited by Smack9; 06-26-2008 at 02:08 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center