.gitignore

*.rbc
*.pyc

bm_red_black_tree.py

import sys
import time
import random
from red_black_tree import RedBlackTree
import sys
#import cProfile

minor = sys.version_info[0]
if minor >= 3:
  xrange = range

def rbt_bm():
  n = 100000
  a1 = [random.randint(0, 999999) for x in xrange(0, n)]
  a2 = [random.randint(0, 999999) for x in xrange(0, n)]

  start = time.time()

  tree = RedBlackTree()

  for i in xrange(0, n):
    tree.add(i)
  for i in xrange(0, n):
    tree.delete(tree.root)

  tree = RedBlackTree()
  for x in a1:
    tree.add(x)
  for x in a2:
    tree.search(x)
  for key in tree.inorder_walk():
    key + 1
  for key in tree.reverse_inorder_walk():
    key + 1
  for i in xrange(0, n):
    tree.maximum()
  for i in xrange(0, n):
    tree.minimum()

  return time.time() - start

if len(sys.argv) > 1:
  n = int(sys.argv[1])
else:
  n = 5

for i in xrange(0, n):
  print("%02f" % rbt_bm())

rbt_bm()

bm_red_black_tree.rb

$:.unshift(File.expand_path(File.dirname(__FILE__) + "/../../lib"))

require 'red_black_tree'

def rbt_bm
  n = 100000
  a1 = []; n.times { a1 << rand(999_999) }
  a2 = []; n.times { a2 << rand(999_999) }
  start = Time.now

  n = 100_000

  tree = RedBlackTree.new

  n.times { tree.insert(RedBlackTree::Node.new(n)) }
  n.times { tree.delete(tree.root) }

  tree = RedBlackTree.new
  a1.each {|e| tree.add(e) }
  a2.each {|e| tree.search(e) }
  tree.inorder_walk {|key| key + 1 }
  tree.reverse_inorder_walk {|key| key + 1 }
  n.times { tree.minimum }
  n.times { tree.maximum }

  return Time.now - start
end

N = (ARGV[0] || 5).to_i

N.times do
  puts rbt_bm
end

red_black_tree.py

RED = 1
BLACK = 2
COLORS = [RED, BLACK]

class Node:

  def __init__(self, key, color = RED):
    if not color in COLORS:
      raise TypeError("Bad value for color parameter (%s)" % color)
    self.color = color
    self.key = key
    self.left = self.right = self.parent = NilNode.instance()

  def __str__(self, level = 0, indent = "   "):
    s = level * indent + str(self.key)
    if self.left:
      s = s + "\n" + self.left.__str__(level + 1, indent)
    if self.right:
      s = s + "\n" + self.right.__str__(level + 1, indent)
    return s
    #return "<Node @key=%s, @color=%s, @left=%s, @right=%s>" % (self.key, self.color, self.left, self.right)

  def is_red(self):
    return self.color == RED

  def is_black(self):
    return self.color == BLACK

  def is_nil(self):
    return False


class NilNode(Node):
  __instance__ = None

  @classmethod
  def instance(self):
    if self.__instance__ is None:
      self.__instance__ = NilNode()
    return self.__instance__

  def __init__(self):
    self.color = BLACK
    self.key = None
    self.left = self.right = self.parent = None
  
  def is_nil(self):
    return True

class RedBlackTree:
  def __init__(self):
    self.root = NilNode.instance()
    self.size = 0
    
  def __str__(self):
    return ("(root.size = %d)\n" % self.size)  + str(self.root)

  def add(self, key):
    self.insert(Node(key))

  #def del(key):


  def insert(self, x):
    self.__insert_helper(x)

    x.color = RED
    while x != self.root and x.parent.color == RED:
      if x.parent == x.parent.parent.left:
        y = x.parent.parent.right
        if not y.is_nil() and y.color == RED:
          x.parent.color = BLACK
          y.color = BLACK
          x.parent.parent.color = RED
          x = x.parent.parent
        else:
          if x == x.parent.right:
            x = x.parent
            self.__left_rotate(x)
          x.parent.color = BLACK
          x.parent.parent.color = RED
          self.__right_rotate(x.parent.parent)
      else:
        y = x.parent.parent.left
        if not y.is_nil() and y.color == RED:
          x.parent.color = BLACK
          y.color = BLACK
          x.parent.parent.color = RED
          x = x.parent.parent
        else:
          if x == x.parent.left:
            x = x.parent
            self.__right_rotate(x)
          x.parent.color = BLACK
          x.parent.parent.color = RED
          self.__left_rotate(x.parent.parent)
    self.root.color = BLACK

  def delete(self, z):
    if z.left.is_nil() or z.right.is_nil():
      y = z
    else:
      y = self.successor(z)
    if y.left.is_nil():
      x = y.right
    else:
      x = y.left
    x.parent = y.parent

    if y.parent.is_nil():
      self.root = x
    else:
      if y == y.parent.left:
        y.parent.left = x
      else:
        y.parent.right = x

    if y != z: z.key = y.key

    if y.color == BLACK:
      self.__delete_fixup(x)

    self.size -= 1
    return y

  def minimum(self, x = None):
    if x is None: x = self.root
    while not x.left.is_nil():
      x = x.left
    return x

  def maximum(self, x = None):
    if x is None: x = self.root
    while not x.right.is_nil():
      x = x.right
    return x

  def successor(self, x):
    if not x.right.is_nil():
      return self.minimum(x.right)
    y = x.parent
    while not y.is_nil() and x == y.right:
      x = y
      y = y.parent
    return y

  def predecessor(self, x):
    if not x.left.is_nil():
      return self.maximum(x.left)
    y = x.parent
    while not y.is_nil() and x == y.left:
      x = y
      y = y.parent
    return y

  def inorder_walk(self, x = None):
    if x is None: x = self.root
    x = self.minimum()
    while not x.is_nil():
      yield x.key
      x = self.successor(x)

  def reverse_inorder_walk(self, x = None):
    if x is None: x = self.root
    x = self.maximum()
    while not x.is_nil():
      yield x.key
      x = self.predecessor(x)

  def search(self, key, x = None):
    if x is None: x = self.root
    while not x.is_nil() and x.key != key:
      if key < x.key:
        x = x.left
      else:
        x = x.right
    return x

  def is_empty(self):
    return self.root.is_nil()

  def black_height(self, x = None):
    if x is None: x = self.root
    height = 0
    while not x.is_nil():
      x = x.left
      if x.is_nil() or x.is_black():
        height += 1
    return height

  def __left_rotate(self, x):
    if x.right.is_nil():
      raise "x.right is nil!"
    y = x.right
    x.right = y.left
    if not y.left.is_nil(): y.left.parent = x
    y.parent = x.parent
    if x.parent.is_nil():
      self.root = y
    else:
      if x == x.parent.left:
        x.parent.left = y
      else:
        x.parent.right = y
    y.left = x
    x.parent = y

  def __right_rotate(self, x):
    if x.left.is_nil():
      raise "x.left is nil!"
    y = x.left
    x.left = y.right
    if not y.right.is_nil(): y.right.parent = x
    y.parent = x.parent
    if x.parent.is_nil():
      self.root = y
    else:
      if x == x.parent.left:
        x.parent.left = y
      else:
        x.parent.right = y
    y.right = x
    x.parent = y

  def __insert_helper(self, z):
    y = NilNode.instance()
    x = self.root
    while not x.is_nil():
      y = x
      if z.key < x.key:
        x = x.left
      else:
        x = x.right
    
    z.parent = y
    if y.is_nil():
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      else:
        y.right = z
    
    self.size += 1

  def __delete_fixup(self, x):
    while x != self.root and x.color == BLACK:
      if x == x.parent.left:
        w = x.parent.right
        if w.color == RED:
          w.color = BLACK
          x.parent.color = RED
          self.__left_rotate(x.parent)
          w = x.parent.right
        if w.left.color == BLACK and w.right.color == BLACK:
          w.color = RED
          x = x.parent
        else:
          if w.right.color == BLACK:
            w.left.color = BLACK
            w.color = RED
            self.__right_rotate(w)
            w = x.parent.right
          w.color = x.parent.color
          x.parent.color = BLACK
          w.right.color = BLACK
          self.__left_rotate(x.parent)
          x = self.root
      else:
        w = x.parent.left
        if w.color == RED:
          w.color = BLACK
          x.parent.color = RED
          self.__right_rotate(x.parent)
          w = x.parent.left
        if w.right.color == BLACK and w.left.color == BLACK:
          w.color = RED
          x = x.parent
        else:
          if w.left.color == BLACK:
            w.right.color = BLACK
            w.color = RED
            self.__left_rotate(w)
            w = x.parent.left
          w.color = x.parent.color
          x.parent.color = BLACK
          w.left.color = BLACK
          self.__right_rotate(x.parent)
          x = root
    x.color = BLACK
    
  

if __name__ == "__main__":
  tree = RedBlackTree()
  tree.add(10)
  tree.add(3)
  tree.add(7)
  tree.add(4)
  tree.add(20)
  tree.add(15)

  print(tree)

  for key in tree.inorder_walk():
    print("key = %s" % key)

red_black_tree.rb

# Algorithm based on "Introduction to Algorithms" by Cormen and others
class RedBlackTree
  class Node
    attr_accessor :color
    attr_accessor :key
    attr_accessor :left
    attr_accessor :right
    attr_accessor :parent

    RED = :red
    BLACK = :black
    COLORS = [RED, BLACK].freeze

    def initialize(key, color = RED)
      raise ArgumentError, "Bad value for color parameter" unless COLORS.include?(color)
      @color = color
      @key = key
      @left = @right = @parent = NilNode.instance
    end

    def black?
      return color == BLACK
    end

    def red?
      return color == RED
    end
  end

  class NilNode < Node
    class << self
      private :new
      @instance = nil

      # it's not thread safe
      def instance
        if @instance.nil?
          @instance = new

          def instance
            return @instance
          end
        end

        return @instance
      end
    end

    def initialize
      self.color = BLACK
      self.key = 0
      self.left = nil
      self.right = nil
      self.parent = nil
    end

    def nil?
      return true
    end
  end

  include Enumerable

  attr_accessor :root
  attr_accessor :size

  def initialize
    self.root = NilNode.instance
    self.size = 0
  end

  def add(key)
    insert(Node.new(key))
  end

  def insert(x)
    insert_helper(x)

    x.color = Node::RED
    while x != root && x.parent.color == Node::RED
      if x.parent == x.parent.parent.left
        y = x.parent.parent.right
        if !y.nil? && y.color == Node::RED
          x.parent.color = Node::BLACK
          y.color = Node::BLACK
          x.parent.parent.color = Node::RED
          x = x.parent.parent
        else
          if x == x.parent.right
            x = x.parent
            left_rotate(x)
          end
          x.parent.color = Node::BLACK
          x.parent.parent.color = Node::RED
          right_rotate(x.parent.parent)
        end
      else
        y = x.parent.parent.left
        if !y.nil? && y.color == Node::RED
          x.parent.color = Node::BLACK
          y.color = Node::BLACK
          x.parent.parent.color = Node::RED
          x = x.parent.parent
        else
          if x == x.parent.left
            x = x.parent
            right_rotate(x)
          end
          x.parent.color = Node::BLACK
          x.parent.parent.color = Node::RED
          left_rotate(x.parent.parent)
        end
      end
    end
    root.color = Node::BLACK
  end

  alias << insert

  def delete(z)
    y = (z.left.nil? || z.right.nil?) ? z : successor(z)
    x = y.left.nil? ? y.right : y.left
    x.parent = y.parent

    if y.parent.nil?
      self.root = x
    else
      if y == y.parent.left
        y.parent.left = x
      else
        y.parent.right = x
      end
    end

    z.key = y.key if y != z

    if y.color == Node::BLACK
      delete_fixup(x)
    end

    self.size -= 1
    return y
  end

  def minimum(x = root)
    while !x.left.nil?
      x = x.left
    end
    return x
  end

  def maximum(x = root)
    while !x.right.nil?
      x = x.right
    end
    return x
  end

  def successor(x)
    if !x.right.nil?
      return minimum(x.right)
    end
    y = x.parent
    while !y.nil? && x == y.right
      x = y
      y = y.parent
    end
    return y
  end

  def predecessor(x)
    if !x.left.nil?
      return maximum(x.left)
    end
    y = x.parent
    while !y.nil? && x == y.left
      x = y
      y = y.parent
    end
    return y
  end

  def inorder_walk(x = root)
    x = self.minimum
    while !x.nil?
      yield x.key
      x = successor(x)
    end
  end

  alias each inorder_walk

  def reverse_inorder_walk(x = root)
    x = self.maximum
    while !x.nil?
      yield x.key
      x = predecessor(x)
    end
  end

  alias reverse_each reverse_inorder_walk

  def search(key, x = root)
    while !x.nil? && x.key != key
      key < x.key ? x = x.left : x = x.right
    end
    return x
  end

  def empty?
    return self.root.nil?
  end

  def black_height(x = root)
    height = 0
    while !x.nil?
      x = x.left
      height +=1 if x.nil? || x.black?
    end
    return height
  end

private

  def left_rotate(x)
    raise "x.right is nil!" if x.right.nil?
    y = x.right
    x.right = y.left
    y.left.parent = x if !y.left.nil?
    y.parent = x.parent
    if x.parent.nil?
      self.root = y
    else
      if x == x.parent.left
        x.parent.left = y
      else
        x.parent.right = y
      end
    end
    y.left = x
    x.parent = y
  end

  def right_rotate(x)
    raise "x.left is nil!" if x.left.nil?
    y = x.left
    x.left = y.right
    y.right.parent = x if !y.right.nil?
    y.parent = x.parent
    if x.parent.nil?
      self.root = y
    else
      if x == x.parent.left
        x.parent.left = y
      else
        x.parent.right = y
      end
    end
    y.right = x
    x.parent = y
  end

  def insert_helper(z)
    y = NilNode.instance
    x = root
    while !x.nil?
      y = x
      z.key < x.key ? x = x.left : x = x.right
    end
    z.parent = y
    if y.nil?
      self.root = z
    else
      z.key < y.key ? y.left = z : y.right = z
    end
    self.size += 1
  end

  def delete_fixup(x)
    while x != root && x.color == Node::BLACK
      if x == x.parent.left
        w = x.parent.right
        if w.color == Node::RED
          w.color = Node::BLACK
          x.parent.color = Node::RED
          left_rotate(x.parent)
          w = x.parent.right
        end
        if w.left.color == Node::BLACK && w.right.color == Node::BLACK
          w.color = Node::RED
          x = x.parent
        else
          if w.right.color == Node::BLACK
            w.left.color = Node::BLACK
            w.color = Node::RED
            right_rotate(w)
            w = x.parent.right
          end
          w.color = x.parent.color
          x.parent.color = Node::BLACK
          w.right.color = Node::BLACK
          left_rotate(x.parent)
          x = root
        end
      else
        w = x.parent.left
        if w.color == Node::RED
          w.color = Node::BLACK
          x.parent.color = Node::RED
          right_rotate(x.parent)
          w = x.parent.left
        end
        if w.right.color == Node::BLACK && w.left.color == Node::BLACK
          w.color = Node::RED
          x = x.parent
        else
          if w.left.color == Node::BLACK
            w.right.color = Node::BLACK
            w.color = Node::RED
            left_rotate(w)
            w = x.parent.left
          end
          w.color = x.parent.color
          x.parent.color = Node::BLACK
          w.left.color = Node::BLACK
          right_rotate(x.parent)
          x = root
        end
      end
    end
    x.color = Node::BLACK
  end
end

results.txt

# all interpreters built from source

$ ruby1.9.1 bm_red_black_tree.rb
4.949379389
4.85002854
4.872958709
4.75958293
4.824939178

$ ruby1.8.6 bm_red_black_tree.rb
13.245832
13.335391
13.974618
14.115719
13.896763

$ ~/opt/src/jruby/bin/jruby --server bm_red_black_tree.rb 20
6.863479
3.409712
3.545647
3.574088
3.547512
3.498346
3.446358
3.483826
3.313169
3.431394
3.461995
3.326763
3.440695
3.286011
3.390503
3.524378
3.322712
3.435351
3.459602
3.326452

$ ~/opt/src/jruby/bin/jruby --server --fast bm_red_black_tree.rb 20
7.088924
2.298887
2.488584
3.616405
3.743274
2.295828
2.360864
2.294946
2.381404
2.23098
2.389819
2.305196
2.255837
2.354832
2.271856
2.647422
2.436133
2.262261
2.286042
2.461298

$ ~/opt/bin/python bm_red_black_tree.py 
16.874310
16.919597
16.818060
16.984473
17.225864

$ ~/opt/bin/python2.6 bm_red_black_tree.py 
16.934663
17.016423
16.703839
17.076022
16.968335

$ ~/opt/bin/python3.0 bm_red_black_tree.py 
11.534306
11.542991
11.569866
11.713882
11.637492

results_pietia.txt

model name      : Intel(R) Core(TM)2 Duo CPU     T8300  @ 2.40GHz
########################
jruby --version
jruby 1.1.6 (ruby 1.8.6 patchlevel 114) (2008-12-17 rev 8388) [i386-java]

ruby --version
ruby 1.8.6 (2008-08-11 patchlevel 287) [i686-linux]

python --version
Python 2.5.2

jython --version
Jython 2.5b1 (trunk:5903:5905, Jan 9 2009, 16:01:29)
[Java HotSpot(TM) Server VM (Sun Microsystems Inc.)] on java1.6.0_11
########################
python  bm_red_black_tree.py
23.203221
26.215589
25.151917
25.242468
24.118340
jython bm_red_black_tree.py
18.650000
16.735000
15.966000
15.878000
15.195000
jythonserver bm_red_black_tree.py
19.630000
17.668000
15.408000
14.670000
14.703000
ruby bm_red_black_tree.rb
10.651496
12.019062
13.499802
13.5671
13.726589
 jruby bm_red_black_tree.rb
7.42838
7.035626
6.913339
7.105795
7.035911
 jruby --server bm_red_black_tree.rb
6.531473
4.11704
4.149193
3.979266
4.047518