Red-Black Tree Implementation in AS3

[rje]

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.

[rachil0]

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).

[rje]

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?

[SaphuA]

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/

[AfternoonDelite]

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.

[Smack9]

I spent a couple of hours translating the code I found here: http://web.mit.edu/~emin/www/source_...ees/index.html

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

  }
}

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

[rje]

Great! I was just thinking of coming back to this...

Now for some benchmarking....

[691175002]

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.

[amirpc]

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

[Smack9]

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:

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:

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.

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:

    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).