MATLABCombined

      1:classdef RedBlackTree < handle
      2:    %     NOTE: Inheriting from handle class provides reference behavior
      3:    %     Red/Black tree implementation based on Algorithms in C++,
      4:    %     Sedgewick Introduction To Algorithms Cormen, Thomas H. Leiserson,
ML    5:    %     Charles E. Rivest, Ronald L . The MIT Press 07/1990
      6:    %     Copyright 2008-2009 The MathWorks, Inc. 
      7:
      8:    properties (Constant=true)
      9:        red=0;
ML   10:        black=1;
     11:    end
     12:    properties (GetAccess='private',SetAccess='private')
     13:        left
     14:        right
ML   15:    end
     16:    properties % Leave public, as get methods in other langauges are public
     17:        color
     18:        val
     19:    end
ML   20:
     21:    methods (Access='private')
     22:
     23:        function copy(self,x)
     24:            self.val     = x.val;
ML   25:            self.left    = x.left;
     26:            self.right   = x.right;
     27:            self.color   = x.color;
     28:        end
     29:        function RBinsertLeft(self,k,sw)
ML   30:            if isempty(self.left)
     31:                self.left = RedBlackTree(k);
     32:            else
     33:                self.left.RBinsert(k,sw);
     34:            end
ML   35:        end
     36:        function RBinsertRight(self,k,sw)
     37:            if isempty(self.right)
     38:                self.right = RedBlackTree(k);
     39:            else
ML   40:                self.right.RBinsert(k,sw);
     41:            end
     42:        end
     43:        function  x=rotLeft(self)
     44:            if isempty(self.right)
ML   45:                x=[];
     46:            else
     47:
     48:                % make the changes in a copy of current node self
     49:                % on return, the caller will copy in 'me' to current node
ML   50:                me          = RedBlackTree();
     51:                me.copy(self);
     52:                x           = me.right;
     53:                me.right = x.left;
     54:                x.left   = me;
ML   55:            end
     56:        end
     57:        function x=rotRight(self)
     58:            if isempty(self.left)
     59:                x=[];
ML   60:            else
     61:
     62:                % make the changes in a copy of current node self
     63:                % on return, the caller will copy in 'me' to current node
     64:                me          = RedBlackTree();
ML   65:                me.copy(self);
     66:                x           = me.left;
     67:                me.left  = x.right;
     68:                x.right  = me;
     69:            end
ML   70:        end
     71:        function RBinsert(self,k,sw)
     72:            % if current node is a 4 node, split it by flipping its colors
     73:            % if both children of this node are red, change this one to red
     74:            % and the children to black
ML   75:            left=self.left;
     76:            right=self.right;
     77:            if (~isempty(left)&&(left.color==RedBlackTree.red)&&~isempty(right)&&(right.color==RedBlackTree.red))
     78:                self.color = RedBlackTree.red;
     79:                left.color = RedBlackTree.black;
ML   80:                right.color = RedBlackTree.black;
     81:            end
     82:
     83:            % go left or right depending on key relationship
     84:            if k<self.val
ML   85:                % recursively insert
     86:                self.RBinsertLeft(k,0);
     87:
     88:                % on the way back up check if a rotation is needed
     89:                % if search path has two red links with same orientation
ML   90:                % do a single rotation and flip the color bits
     91:                left=self.left;
     92:                if ((self.color == RedBlackTree.red)&&~isempty(left)&&(left.color == RedBlackTree.red)&&(sw == 1))
     93:                    x = self.rotRight();
     94:                    if ~isempty(x)
ML   95:                        % copy returned node to 'self'
     96:                        self.copy(x);
     97:                    end
     98:                end
     99:
ML  100:                % flip the color bits
    101:                left=self.left;
    102:                if ~isempty(left)
    103:                    ll = left.left;
    104:                    if ~isempty(ll)
ML  105:                        if ((left.color == RedBlackTree.red)&&(ll.color == RedBlackTree.red))
    106:                            x = self.rotRight();
    107:                            if ~isempty(x)
    108:                                self.copy(x);
    109:                            end
ML  110:                            self.color = RedBlackTree.black;
    111:                            right = self.right;
    112:                            if ~isempty(right)
    113:                                right.color = RedBlackTree.red;
    114:                            end
ML  115:                        end
    116:                    end
    117:                end
    118:
    119:            else
ML  120:                self.RBinsertRight(k,1);
    121:
    122:                % on the way back up check if a rotation is needed
    123:                % if search path has two red links with same orientation
    124:                % do a single rotation and flip the color bits
ML  125:                right = self.right;
    126:                if ((self.color == RedBlackTree.red)&&~isempty(right)&&(right.color == RedBlackTree.red)&&(sw == 0))
    127:                    x = self.rotLeft();
    128:                    if ~isempty(x)
    129:                        self.copy(x);
ML  130:                    end
    131:                end
    132:
    133:                % flip the color bits
    134:                right = self.right;
ML  135:                if ~isempty(right)
    136:                    rr = right.right;
    137:                    if ~isempty(rr)
    138:                        if ((right.color == RedBlackTree.red)&&(rr.color == RedBlackTree.red))
    139:                            x = self.rotLeft();
ML  140:                            if ~isempty(x)
    141:                                self.copy(x);
    142:                            end
    143:                            self.color = RedBlackTree.black;
    144:                            left = self.left;
ML  145:                            if ~isempty(left)
    146:                                left.color = RedBlackTree.red;
    147:                            end
    148:                        end
    149:                    end
ML  150:                end
    151:            end
    152:        end
    153:    end
    154:
ML  155:    % ==================================================
    156:    % PUBLIC METHODS
    157:    % ==================================================
    158:    methods
    159:        % constructor
ML  160:        function self=RedBlackTree(varargin)
    161:            self.left     = [];
    162:            self.right    = [];
    163:            if nargin==1 % Get param value
    164:                self.val =varargin{1};
ML  165:            end
    166:            self.color    = RedBlackTree.red;
    167:        end
    168:
    169:        % to string
ML  170:        function str=s(self)
    171:            str=['[' num2str(self.val) ',' num2str(self.color) ']'];
    172:        end
    173:
    174:        % recursive 'find'
ML  175:        function  result=find(self,key)
    176:            result=[];
    177:            if key == self.val
    178:                result = self;
    179:            elseif key < self.val
ML  180:                if ~isempty(self.left)
    181:                    result = self.left.find(key);
    182:                end
    183:            else
    184:                if ~isempty(self.right)
ML  185:                    result = self.right.find(key);
    186:                end
    187:            end
    188:        end
    189:
ML  190:        % inorder traversal using a class as the visitor
    191:        function inorder(self,visitor,depth)
    192:            if ~isempty(self.left)
    193:                self.left.inorder(visitor,depth+1);
    194:            end
ML  195:            visitor.visit(self,depth);
    196:            if ~isempty(self.right)
    197:                self.right.inorder(visitor,depth+1);
    198:            end
    199:        end
ML  200:
    201:        function insert(self,k)
    202:            self.RBinsert(k,0);
    203:            self.color = RedBlackTree.black;
    204:        end
ML  205:    end
    206:end
    207:
    208:classdef NodeVisitor < handle % Separate file
    209:    methods
ML  210:        function visit(self,node,depth)
    211:            if ~isempty(node.val)
    212:                fprintf('(%d:%d:%d), ', node.val, node.color, depth);
    213:            end
    214:        end
ML  215:    end
    216:end
    217:
    218:% // ==================================
    219:% // test program
ML  220:% // ==================================
    221:
    222:function test_RedBlackTree % Separate file
    223:nodelist= [11,4,8,14,17,6,9,7,16,15,13,5,19,18,12,10,3,20,1];
    224:root = RedBlackTree(2);
ML  225:for n=nodelist
    226:    root.insert(n)
    227:end
    228:
    229:% class implementing the NodeVisitor interface
ML  230:v=NodeVisitor;
    231:fprintf('M      = ');
    232:root.inorder(v,0);
    233:fprintf('\n');
    234:
ML  235:% find the specified element and print its value
    236:x=root.find(16);
    237:fprintf([x.s '\n']);