rbmatlab.html

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

        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

classdef NodeVisitor < handle % Separate file
    methods
        function visit(self,node,depth)
            if ~isempty(node.val)
                fprintf('(%d:%d:%d), ', node.val, node.color, depth);
            end
        end
    end
end

% // ==================================
% // test program
% // ==================================

function test_RedBlackTree % Separate file
nodelist= [11,4,8,14,17,6,9,7,16,15,13,5,19,18,12,10,3,20,1];
root = RedBlackTree(2);
for n=nodelist
    root.insert(n)
end

% class implementing the NodeVisitor interface
v=NodeVisitor;
fprintf('M      = ');
root.inorder(v,0);
fprintf('\n');

% find the specified element and print its value
x=root.find(16);
fprintf([x.s '\n']);
##### SOURCE END #####
-->
   </body>
</html>