redblacktree.m

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

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

    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