rbmatlab.html

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

<span class="gutter">    109:</span>                            <span class="keyword">end</span>
<span class="gutterH">ML  110:</span>                            self.color = RedBlackTree.black;
<span class="gutter">    111:</span>                            right = self.right;
<span class="gutter">    112:</span>                            <span class="keyword">if</span> ~isempty(right)
<span class="gutter">    113:</span>                                right.color = RedBlackTree.red;
<span class="gutter">    114:</span>                            <span class="keyword">end</span>
<span class="gutterH">ML  115:</span>                        <span class="keyword">end</span>
<span class="gutter">    116:</span>                    <span class="keyword">end</span>
<span class="gutter">    117:</span>                <span class="keyword">end</span>
<span class="gutter">    118:</span>
<span class="gutter">    119:</span>            <span class="keyword">else</span>
<span class="gutterH">ML  120:</span>                self.RBinsertRight(k,1);
<span class="gutter">    121:</span>
<span class="gutter">    122:</span>                <span class="comment">% on the way back up check if a rotation is needed</span>
<span class="gutter">    123:</span>                <span class="comment">% if search path has two red links with same orientation</span>
<span class="gutter">    124:</span>                <span class="comment">% do a single rotation and flip the color bits</span>
<span class="gutterH">ML  125:</span>                right = self.right;
<span class="gutter">    126:</span>                <span class="keyword">if</span> ((self.color == RedBlackTree.red)&amp;&amp;~isempty(right)&amp;&amp;(right.color == RedBlackTree.red)&amp;&amp;(sw == 0))
<span class="gutter">    127:</span>                    x = self.rotLeft();
<span class="gutter">    128:</span>                    <span class="keyword">if</span> ~isempty(x)
<span class="gutter">    129:</span>                        self.copy(x);
<span class="gutterH">ML  130:</span>                    <span class="keyword">end</span>
<span class="gutter">    131:</span>                <span class="keyword">end</span>
<span class="gutter">    132:</span>
<span class="gutter">    133:</span>                <span class="comment">% flip the color bits</span>
<span class="gutter">    134:</span>                right = self.right;
<span class="gutterH">ML  135:</span>                <span class="keyword">if</span> ~isempty(right)
<span class="gutter">    136:</span>                    rr = right.right;
<span class="gutter">    137:</span>                    <span class="keyword">if</span> ~isempty(rr)
<span class="gutter">    138:</span>                        <span class="keyword">if</span> ((right.color == RedBlackTree.red)&amp;&amp;(rr.color == RedBlackTree.red))
<span class="gutter">    139:</span>                            x = self.rotLeft();
<span class="gutterH">ML  140:</span>                            <span class="keyword">if</span> ~isempty(x)
<span class="gutter">    141:</span>                                self.copy(x);
<span class="gutter">    142:</span>                            <span class="keyword">end</span>
<span class="gutter">    143:</span>                            self.color = RedBlackTree.black;
<span class="gutter">    144:</span>                            left = self.left;
<span class="gutterH">ML  145:</span>                            <span class="keyword">if</span> ~isempty(left)
<span class="gutter">    146:</span>                                left.color = RedBlackTree.red;
<span class="gutter">    147:</span>                            <span class="keyword">end</span>
<span class="gutter">    148:</span>                        <span class="keyword">end</span>
<span class="gutter">    149:</span>                    <span class="keyword">end</span>
<span class="gutterH">ML  150:</span>                <span class="keyword">end</span>
<span class="gutter">    151:</span>            <span class="keyword">end</span>
<span class="gutter">    152:</span>        <span class="keyword">end</span>
<span class="gutter">    153:</span>    <span class="keyword">end</span>
<span class="gutter">    154:</span>
<span class="gutterH">ML  155:</span>    <span class="comment">% ==================================================</span>
<span class="gutter">    156:</span>    <span class="comment">% PUBLIC METHODS</span>
<span class="gutter">    157:</span>    <span class="comment">% ==================================================</span>
<span class="gutter">    158:</span>    <span class="keyword">methods</span>
<span class="gutter">    159:</span>        <span class="comment">% constructor</span>
<span class="gutterH">ML  160:</span>        <span class="keyword">function</span> self=RedBlackTree(varargin)
<span class="gutter">    161:</span>            self.left     = [];
<span class="gutter">    162:</span>            self.right    = [];
<span class="gutter">    163:</span>            <span class="keyword">if</span> nargin==1 <span class="comment">% Get param value</span>
<span class="gutter">    164:</span>                self.val =varargin{1};
<span class="gutterH">ML  165:</span>            <span class="keyword">end</span>
<span class="gutter">    166:</span>            self.color    = RedBlackTree.red;
<span class="gutter">    167:</span>        <span class="keyword">end</span>
<span class="gutter">    168:</span>
<span class="gutter">    169:</span>        <span class="comment">% to string</span>
<span class="gutterH">ML  170:</span>        <span class="keyword">function</span> str=s(self)
<span class="gutter">    171:</span>            str=[<span class="string">'['</span> num2str(self.val) <span class="string">','</span> num2str(self.color) <span class="string">']'</span>];
<span class="gutter">    172:</span>        <span class="keyword">end</span>
<span class="gutter">    173:</span>
<span class="gutter">    174:</span>        <span class="comment">% recursive 'find'</span>
<span class="gutterH">ML  175:</span>        <span class="keyword">function</span>  result=find(self,key)
<span class="gutter">    176:</span>            result=[];
<span class="gutter">    177:</span>            <span class="keyword">if</span> key == self.val
<span class="gutter">    178:</span>                result = self;
<span class="gutter">    179:</span>            <span class="keyword">elseif</span> key &lt; self.val
<span class="gutterH">ML  180:</span>                <span class="keyword">if</span> ~isempty(self.left)
<span class="gutter">    181:</span>                    result = self.left.find(key);
<span class="gutter">    182:</span>                <span class="keyword">end</span>
<span class="gutter">    183:</span>            <span class="keyword">else</span>
<span class="gutter">    184:</span>                <span class="keyword">if</span> ~isempty(self.right)
<span class="gutterH">ML  185:</span>                    result = self.right.find(key);
<span class="gutter">    186:</span>                <span class="keyword">end</span>
<span class="gutter">    187:</span>            <span class="keyword">end</span>
<span class="gutter">    188:</span>        <span class="keyword">end</span>
<span class="gutter">    189:</span>
<span class="gutterH">ML  190:</span>        <span class="comment">% inorder traversal using a class as the visitor</span>
<span class="gutter">    191:</span>        <span class="keyword">function</span> inorder(self,visitor,depth)
<span class="gutter">    192:</span>            <span class="keyword">if</span> ~isempty(self.left)
<span class="gutter">    193:</span>                self.left.inorder(visitor,depth+1);
<span class="gutter">    194:</span>            <span class="keyword">end</span>
<span class="gutterH">ML  195:</span>            visitor.visit(self,depth);
<span class="gutter">    196:</span>            <span class="keyword">if</span> ~isempty(self.right)
<span class="gutter">    197:</span>                self.right.inorder(visitor,depth+1);
<span class="gutter">    198:</span>            <span class="keyword">end</span>
<span class="gutter">    199:</span>        <span class="keyword">end</span>
<span class="gutterH">ML  200:</span>
<span class="gutter">    201:</span>        <span class="keyword">function</span> insert(self,k)
<span class="gutter">    202:</span>            self.RBinsert(k,0);
<span class="gutter">    203:</span>            self.color = RedBlackTree.black;
<span class="gutter">    204:</span>        <span class="keyword">end</span>
<span class="gutterH">ML  205:</span>    <span class="keyword">end</span>
<span class="gutter">    206:</span><span class="keyword">end</span>
<span class="gutter">    207:</span>
<span class="gutter">    208:</span><span class="keyword">classdef</span> NodeVisitor &lt; handle <span class="comment">% Separate file</span>
<span class="gutter">    209:</span>    <span class="keyword">methods</span>
<span class="gutterH">ML  210:</span>        <span class="keyword">function</span> visit(self,node,depth)
<span class="gutter">    211:</span>            <span class="keyword">if</span> ~isempty(node.val)
<span class="gutter">    212:</span>                fprintf(<span class="string">'(%d:%d:%d), '</span>, node.val, node.color, depth);
<span class="gutter">    213:</span>            <span class="keyword">end</span>
<span class="gutter">    214:</span>        <span class="keyword">end</span>
<span class="gutterH">ML  215:</span>    <span class="keyword">end</span>
<span class="gutter">    216:</span><span class="keyword">end</span>
<span class="gutter">    217:</span>
<span class="gutter">    218:</span><span class="comment">% // ==================================</span>
<span class="gutter">    219:</span><span class="comment">% // test program</span>
<span class="gutterH">ML  220:</span><span class="comment">% // ==================================</span>
<span class="gutter">    221:</span>
<span class="gutter">    222:</span><span class="keyword">function</span> test_RedBlackTree <span class="comment">% Separate file</span>
<span class="gutter">    223:</span>nodelist= [11,4,8,14,17,6,9,7,16,15,13,5,19,18,12,10,3,20,1];
<span class="gutter">    224:</span>root = RedBlackTree(2);
<span class="gutterH">ML  225:</span><span class="keyword">for</span> n=nodelist
<span class="gutter">    226:</span>    root.insert(n)
<span class="gutter">    227:</span><span class="keyword">end</span>
<span class="gutter">    228:</span>
<span class="gutter">    229:</span><span class="comment">% class implementing the NodeVisitor interface</span>
<span class="gutterH">ML  230:</span>v=NodeVisitor;
<span class="gutter">    231:</span>fprintf(<span class="string">'M      = '</span>);
<span class="gutter">    232:</span>root.inorder(v,0);
<span class="gutter">    233:</span>fprintf(<span class="string">'\n'</span>);
<span class="gutter">    234:</span>
<span class="gutterH">ML  235:</span><span class="comment">% find the specified element and print its value</span>
<span class="gutter">    236:</span>x=root.find(16);
<span class="gutter">    237:</span>fprintf([x.s <span class="string">'\n'</span>]);
</pre><p class="footer"><br>
            Published with MATLAB&reg; 7.6<br></p>
      </div>
      <!--
##### SOURCE BEGIN #####
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