📄 rbmatlab.html
字号:
<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN">
<html xmlns:mwsh="http://www.mathworks.com/namespace/mcode/v1/syntaxhighlight.dtd">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<!--
This HTML is auto-generated from an M-file.
To make changes, update the M-file and republish this document.
-->
<title>MATLABCombined</title>
<meta name="generator" content="MATLAB 7.6">
<meta name="date" content="2008-02-22">
<meta name="m-file" content="MATLABCombined"><style>
body {
background-color: white;
margin:10px;
}
h1 {
color: #990000;
font-size: x-large;
}
h2 {
color: #990000;
font-size: medium;
}
/* Make the text shrink to fit narrow windows, but not stretch too far in
wide windows. */
p,h1,h2,div.content div {
max-width: 600px;
/* Hack for IE6 */
width: auto !important; width: 600px;
}
pre.codeinput {
background: white
padding: 10px;
}
@media print {
pre.codeinput {word-wrap:break-word; width:100%;}
}
span.keyword {color: #0000FF}
span.comment {color: #228B22}
span.string {color: #A020F0}
span.untermstring {color: #B20000}
span.syscmd {color: #B28C00}
pre.codeoutput {
color: #666666;
padding: 10px;
}
pre.error {
color: red;
}
p.footer {
text-align: right;
font-size: xx-small;
font-weight: lighter;
font-style: italic;
color: gray;
}
.gutter {
background: #dbdbdb;
color: #000000;
}
.gutterH {
background: #dbdbdb;
color: #990066;
</style></head>
<body>
<div class="content"><pre class="codeinput">
<span class="gutter"> 1:</span><span class="keyword">classdef</span> RedBlackTree < handle
<span class="gutter"> 2:</span> <span class="comment">% NOTE: Inheriting from handle class provides reference behavior</span>
<span class="gutter"> 3:</span> <span class="comment">%</span>
<span class="gutter"> 4:</span> <span class="comment">% Red/Black tree implementation based on Algorithms in C++,</span>
<span class="gutterH">ML 5:</span> <span class="comment">% Sedgewick Introduction To Algorithms Cormen, Thomas H. Leiserson,</span>
<span class="gutter"> 6:</span> <span class="comment">% Charles E. Rivest, Ronald L . The MIT Press 07/1990</span>
<span class="gutter"> 7:</span>
<span class="gutter"> 8:</span> <span class="keyword">properties</span> (Constant=true)
<span class="gutter"> 9:</span> red=0;
<span class="gutterH">ML 10:</span> black=1;
<span class="gutter"> 11:</span> <span class="keyword">end</span>
<span class="gutter"> 12:</span> <span class="keyword">properties</span> (GetAccess=<span class="string">'private'</span>,SetAccess=<span class="string">'private'</span>)
<span class="gutter"> 13:</span> left
<span class="gutter"> 14:</span> right
<span class="gutterH">ML 15:</span> <span class="keyword">end</span>
<span class="gutter"> 16:</span> <span class="keyword">properties</span> <span class="comment">% Leave public, as get methods in other langauges are public</span>
<span class="gutter"> 17:</span> color
<span class="gutter"> 18:</span> val
<span class="gutter"> 19:</span> <span class="keyword">end</span>
<span class="gutterH">ML 20:</span>
<span class="gutter"> 21:</span> <span class="keyword">methods</span> (Access=<span class="string">'private'</span>)
<span class="gutter"> 22:</span>
<span class="gutter"> 23:</span> <span class="keyword">function</span> copy(self,x)
<span class="gutter"> 24:</span> self.val = x.val;
<span class="gutterH">ML 25:</span> self.left = x.left;
<span class="gutter"> 26:</span> self.right = x.right;
<span class="gutter"> 27:</span> self.color = x.color;
<span class="gutter"> 28:</span> <span class="keyword">end</span>
<span class="gutter"> 29:</span> <span class="keyword">function</span> RBinsertLeft(self,k,sw)
<span class="gutterH">ML 30:</span> <span class="keyword">if</span> isempty(self.left)
<span class="gutter"> 31:</span> self.left = RedBlackTree(k);
<span class="gutter"> 32:</span> <span class="keyword">else</span>
<span class="gutter"> 33:</span> self.left.RBinsert(k,sw);
<span class="gutter"> 34:</span> <span class="keyword">end</span>
<span class="gutterH">ML 35:</span> <span class="keyword">end</span>
<span class="gutter"> 36:</span> <span class="keyword">function</span> RBinsertRight(self,k,sw)
<span class="gutter"> 37:</span> <span class="keyword">if</span> isempty(self.right)
<span class="gutter"> 38:</span> self.right = RedBlackTree(k);
<span class="gutter"> 39:</span> <span class="keyword">else</span>
<span class="gutterH">ML 40:</span> self.right.RBinsert(k,sw);
<span class="gutter"> 41:</span> <span class="keyword">end</span>
<span class="gutter"> 42:</span> <span class="keyword">end</span>
<span class="gutter"> 43:</span> <span class="keyword">function</span> x=rotLeft(self)
<span class="gutter"> 44:</span> <span class="keyword">if</span> isempty(self.right)
<span class="gutterH">ML 45:</span> x=[];
<span class="gutter"> 46:</span> <span class="keyword">else</span>
<span class="gutter"> 47:</span>
<span class="gutter"> 48:</span> <span class="comment">% make the changes in a copy of current node self</span>
<span class="gutter"> 49:</span> <span class="comment">% on return, the caller will copy in 'me' to current node</span>
<span class="gutterH">ML 50:</span> me = RedBlackTree();
<span class="gutter"> 51:</span> me.copy(self);
<span class="gutter"> 52:</span> x = me.right;
<span class="gutter"> 53:</span> me.right = x.left;
<span class="gutter"> 54:</span> x.left = me;
<span class="gutterH">ML 55:</span> <span class="keyword">end</span>
<span class="gutter"> 56:</span> <span class="keyword">end</span>
<span class="gutter"> 57:</span> <span class="keyword">function</span> x=rotRight(self)
<span class="gutter"> 58:</span> <span class="keyword">if</span> isempty(self.left)
<span class="gutter"> 59:</span> x=[];
<span class="gutterH">ML 60:</span> <span class="keyword">else</span>
<span class="gutter"> 61:</span>
<span class="gutter"> 62:</span> <span class="comment">% make the changes in a copy of current node self</span>
<span class="gutter"> 63:</span> <span class="comment">% on return, the caller will copy in 'me' to current node</span>
<span class="gutter"> 64:</span> me = RedBlackTree();
<span class="gutterH">ML 65:</span> me.copy(self);
<span class="gutter"> 66:</span> x = me.left;
<span class="gutter"> 67:</span> me.left = x.right;
<span class="gutter"> 68:</span> x.right = me;
<span class="gutter"> 69:</span> <span class="keyword">end</span>
<span class="gutterH">ML 70:</span> <span class="keyword">end</span>
<span class="gutter"> 71:</span> <span class="keyword">function</span> RBinsert(self,k,sw)
<span class="gutter"> 72:</span> <span class="comment">% if current node is a 4 node, split it by flipping its colors</span>
<span class="gutter"> 73:</span> <span class="comment">% if both children of this node are red, change this one to red</span>
<span class="gutter"> 74:</span> <span class="comment">% and the children to black</span>
<span class="gutterH">ML 75:</span> left=self.left;
<span class="gutter"> 76:</span> right=self.right;
<span class="gutter"> 77:</span> <span class="keyword">if</span> (~isempty(left)&&(left.color==RedBlackTree.red)&&~isempty(right)&&(right.color==RedBlackTree.red))
<span class="gutter"> 78:</span> self.color = RedBlackTree.red;
<span class="gutter"> 79:</span> left.color = RedBlackTree.black;
<span class="gutterH">ML 80:</span> right.color = RedBlackTree.black;
<span class="gutter"> 81:</span> <span class="keyword">end</span>
<span class="gutter"> 82:</span>
<span class="gutter"> 83:</span> <span class="comment">% go left or right depending on key relationship</span>
<span class="gutter"> 84:</span> <span class="keyword">if</span> k<self.val
<span class="gutterH">ML 85:</span> <span class="comment">% recursively insert</span>
<span class="gutter"> 86:</span> self.RBinsertLeft(k,0);
<span class="gutter"> 87:</span>
<span class="gutter"> 88:</span> <span class="comment">% on the way back up check if a rotation is needed</span>
<span class="gutter"> 89:</span> <span class="comment">% if search path has two red links with same orientation</span>
<span class="gutterH">ML 90:</span> <span class="comment">% do a single rotation and flip the color bits</span>
<span class="gutter"> 91:</span> left=self.left;
<span class="gutter"> 92:</span> <span class="keyword">if</span> ((self.color == RedBlackTree.red)&&~isempty(left)&&(left.color == RedBlackTree.red)&&(sw == 1))
<span class="gutter"> 93:</span> x = self.rotRight();
<span class="gutter"> 94:</span> <span class="keyword">if</span> ~isempty(x)
<span class="gutterH">ML 95:</span> <span class="comment">% copy returned node to 'self'</span>
<span class="gutter"> 96:</span> self.copy(x);
<span class="gutter"> 97:</span> <span class="keyword">end</span>
<span class="gutter"> 98:</span> <span class="keyword">end</span>
<span class="gutter"> 99:</span>
<span class="gutterH">ML 100:</span> <span class="comment">% flip the color bits</span>
<span class="gutter"> 101:</span> left=self.left;
<span class="gutter"> 102:</span> <span class="keyword">if</span> ~isempty(left)
<span class="gutter"> 103:</span> ll = left.left;
<span class="gutter"> 104:</span> <span class="keyword">if</span> ~isempty(ll)
<span class="gutterH">ML 105:</span> <span class="keyword">if</span> ((left.color == RedBlackTree.red)&&(ll.color == RedBlackTree.red))
<span class="gutter"> 106:</span> x = self.rotRight();
<span class="gutter"> 107:</span> <span class="keyword">if</span> ~isempty(x)
<span class="gutter"> 108:</span> self.copy(x);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -