Code covered by the BSD License

# Comparison of C++, Java, Python, Ruby and MATLAB Using Object Oriented Example

### Stuart McGarrity (view profile)

28 Feb 2008 (Updated )

RedBlack Tree Binary Search Example Used to Compare of C++, Java™, Python, Ruby and MATLAB® Code

### Editor's Notes:

This file was selected as MATLAB Central Pick of the Week

RedBlackTree
```classdef RedBlackTree < handle
%     NOTE: Inheriting from handle class provides reference behavior
%
%     Red/Black tree implementation based on Algorithms in C++,
%     Sedgewick Introduction To Algorithms Cormen, Thomas H. Leiserson,
%     Charles E. Rivest, Ronald L . The MIT Press 07/1990
%
%     Copyright 2008-2009 The MathWorks, Inc

properties (Constant=true)
red=0;
black=1;
end
properties (GetAccess='private',SetAccess='private')
left
right
end
properties % Leave public, as get methods in other langauges are public
color
val
end

methods (Access='private')

function copy(self,x)
self.val     = x.val;
self.left    = x.left;
self.right   = x.right;
self.color   = x.color;
end
function RBinsertLeft(self,k,sw)
if isempty(self.left)
self.left = RedBlackTree(k);
else
self.left.RBinsert(k,sw);
end
end
function RBinsertRight(self,k,sw)
if isempty(self.right)
self.right = RedBlackTree(k);
else
self.right.RBinsert(k,sw);
end
end
function  x=rotLeft(self)
if isempty(self.right)
x=[];
else

% make the changes in a copy of current node self
% on return, the caller will copy in 'me' to current node
me          = RedBlackTree();
me.copy(self);
x           = me.right;
me.right = x.left;
x.left   = me;
end
end
function x=rotRight(self)
if isempty(self.left)
x=[];
else

% make the changes in a copy of current node self
% on return, the caller will copy in 'me' to current node
me          = RedBlackTree();
me.copy(self);
x           = me.left;
me.left  = x.right;
x.right  = me;
end
end
function RBinsert(self,k,sw)
% if current node is a 4 node, split it by flipping its colors
% if both children of this node are red, change this one to red
% and the children to black
left=self.left;
right=self.right;
if (~isempty(left)&&(left.color==RedBlackTree.red)&&~isempty(right)&&(right.color==RedBlackTree.red))
self.color = RedBlackTree.red;
left.color = RedBlackTree.black;
right.color = RedBlackTree.black;
end

% go left or right depending on key relationship
if k<self.val
% recursively insert
self.RBinsertLeft(k,0);

% on the way back up check if a rotation is needed
% if search path has two red links with same orientation
% do a single rotation and flip the color bits
left=self.left;
if ((self.color == RedBlackTree.red)&&~isempty(left)&&(left.color == RedBlackTree.red)&&(sw == 1))
x = self.rotRight();
if ~isempty(x)
% copy returned node to 'self'
self.copy(x);
end
end

% flip the color bits
left=self.left;
if ~isempty(left)
ll = left.left;
if ~isempty(ll)
if ((left.color == RedBlackTree.red)&&(ll.color == RedBlackTree.red))
x = self.rotRight();
if ~isempty(x)
self.copy(x);
end
self.color = RedBlackTree.black;
right = self.right;
if ~isempty(right)
right.color = RedBlackTree.red;
end
end
end
end

else
self.RBinsertRight(k,1);

% on the way back up check if a rotation is needed
% if search path has two red links with same orientation
% do a single rotation and flip the color bits
right = self.right;
if ((self.color == RedBlackTree.red)&&~isempty(right)&&(right.color == RedBlackTree.red)&&(sw == 0))
x = self.rotLeft();
if ~isempty(x)
self.copy(x);
end
end

% flip the color bits
right = self.right;
if ~isempty(right)
rr = right.right;
if ~isempty(rr)
if ((right.color == RedBlackTree.red)&&(rr.color == RedBlackTree.red))
x = self.rotLeft();
if ~isempty(x)
self.copy(x);
end
self.color = RedBlackTree.black;
left = self.left;
if ~isempty(left)
left.color = RedBlackTree.red;
end
end
end
end
end
end
end

% ==================================================
% PUBLIC METHODS
% ==================================================
methods
% constructor
function self=RedBlackTree(varargin)
self.left     = [];
self.right    = [];
if nargin==1 % Get param value
self.val =varargin{1};
end
self.color    = RedBlackTree.red;
end

% to string
function str=s(self)
str=['[' num2str(self.val) ',' num2str(self.color) ']'];
end

% recursive 'find'
function  result=find(self,key)
result=[];
if key == self.val
result = self;
elseif key < self.val
if ~isempty(self.left)
result = self.left.find(key);
end
else
if ~isempty(self.right)
result = self.right.find(key);
end
end
end

% inorder traversal using a class as the visitor
function inorder(self,visitor,depth)
if ~isempty(self.left)
self.left.inorder(visitor,depth+1);
end
visitor.visit(self,depth);
if ~isempty(self.right)
self.right.inorder(visitor,depth+1);
end
end

function insert(self,k)
self.RBinsert(k,0);
self.color = RedBlackTree.black;
end
end
end```