\documentclass[twocolumn]{jarticle}
\usepackage{taikai2001}

\title{$B<+8JD4@0FsJ,LZ$NJBNsA`:n(B\\
\large Concurrent Operations on Splay Trees}
\author{$B>eED(B $BOB5*(B\adag\\\normalsize Kazunori UEDA\\[6pt]
\adag $BAa0pEDBg3XM}9)3XIt>pJs3X2J(B\\%
Dept.\ of Information and Computer Science, Waseda University\\
\texttt{ueda@ueda.info.waseda.ac.jp}}
\abstract{%
Sleator$B$H(BTarjan$B$K$h$k<+8JD4@0FsJ,LZ!J(Bsplay tree$B!K$KBP$7$FJB(B
$BNsA`:n$r2DG=$K$9$kA`:n%"%k%4%j%:%`$rDs0F$9$k!%Ds0F$9$k%"%k(B
$B%4%j%:%`$O!$F10l$NLZ$KBP$9$kJ#?t$N99?7!&A^F~!&:o=|A`:n$N%Q%$%W%i%$%sE*JB(B
$BNs<B9T$r5v$7!$$+$DA`:n7ONs$N%9%k!<%W%C%H!JC10L;~4VFb$K=hM}2DG=$J(B
$BA`:n$N8D?t!K$H%l%9%]%s%9!J8D!9$NA`:n$N=~5Q7W;;NL(B
$B!J(Bamortized complexity$B!K!K$rN>N)$5$;$k$3$H$rL\E*$H$7$F$$$k!%(B
$B%9%k!<%W%C%H$N:GE,@-$HA^F~A`:n$NBP?tE*%l%9%]%s%9$K$D$$$F$O(B
$BM}O@E*7k2L$r<($9!%:o=|A`:n$O!$LZ$N7A>u$K4X$9$kNI$$@-<A$rJ]$D(B
$B$K$b$+$+$o$i$:!$(BSleator$B$i$NOHAH$_$G$O:GE,@-$,>ZL@$G$-$J$$!%(B
$B$3$N$3$H$K$D$$$F$bO@$8$k!%(B}

\begin{document}
\maketitle
\thispagestyle{myheadings}
%
\section{$B$O$8$a$K(B}\label{sec1}

$B<+8JD4@0FsJ,LZ!J%9%W%l!<LZ(B, splay tree$B!K(B\cite{ST85} $B$O!$%"%/%;%9$7$?@a(B
$BE@$KBP$7$FY(J?2=!J(Bsplaying$B!KA`:n!J(B\ref{subsection:splaying} $B@a!K(B
$B$r;\$9$3$H$K$h$j!$LZ$N7A>u$rF0E*$K:GE,2=$9(B
$B$kFsJ,C5:wLZ$NAm>N$G$"$j!$(B
$BB?$/$N6/NO$J@-<A$,@.$jN)$D$3$H$,$o$+$C$F$$$k!%K\O@J8$G$O!$(B
$BF10l$N%9%W%l!<LZ$KBP$9$kJ#?t$NA^F~:o=|Ey$NA`:n(B
$B$NJBNs<B9T$r2DG=$K$9$kJ}K!$r8!F$$9$k!%L\I8$O!$2<5-$NMW@A$rK~$?$9(B
$BA`:n%"%k%4%j%:%`$rF@$k$3$H$G$"$k!%(B
%
\begin{enumerate}
\item $B!J(B{\bf $B%l%9%]%s%9(B}$B!KDL>o$N%9%W%l!<LZ$NA`:n$HF1MM!$(B
$BBP?tE*$J=~5Q7W;;NL!J(Bamortized complexity$B!K$r$b$D!%(B

\item $B!J(B{\bf $B%9%k!<%W%C%H(B}$B!KA`:n8e$NLZ$N7A>u$,!$:,$K6a$$ItJ,$+(B
$B$iA2A}E*$K3NDj$9$k$h$&$K$9$k$3$H$G!$8D!9$NA`:n$,F1;~$K;\>{$7$J$1$l$P$J(B
$B$i$J$$@aE@$N?t$r9b!9(B${\rm O}(1)$$B8D$K$*$5$($k!%(B
\end{enumerate}
%
$B$b$7%9%k!<%W%C%H$@$1$,L\I8$J$i$P!$@~7A%j%9%H$rMQ$$$FMF(B
$B0W$KC#@.$G$-$k!%$7$?$,$C$F!$%l%9%]%s%9$H%9%k!<%W%C%H(B
$B$rF1;~$KC#@.$9$k$3$H$,K\<AE*$K=EMW$G$"$k!%(B
%
B$BLZ$d$=$NJQ<o$KBP$9$kJBNsA`:n$N8&5f$O>/$J$/$J$$(B\cite{LS86} $B$,!$%9%W(B
$B%l!<LZ$NJBNs@-$K4X$9$k8&5f$O>/$J$/!$Cx<T$NCN$k8B$j!$>e5-$NFs>r7o$rK~$?$9(B
$BJBNs%"%k%4%j%:%`$O$^$@Ds0F$5$l$F$$$J$$!%(B

$BK\O@J8$G$O!$FsJ,C5:wLZ$N3F@aE@$O%-!<$HCM$NBP$rJ];}$9$k$b$N$H$7!$@aE@$O(B
$B%-!<$NBP>N=g!J(Bsymmetric order$B!K$KJB$s$G$$$k$H$9$k!%4pK\A`:n$H$7$F!$(B
$B<!$NFs$D$r9M$($k!%C1$J$k@aE@CM$NFI=P$7$O(B${\it update\/}$$B$NC1=c$JJQ(B
$B<o$H9M$($k$3$H$,$G$-$k!%(B

\begin{description}
\item{${\it update}(i,v,v',t)$:} $B%-!<(B$i$$B$r$b$D@aE@$,LZ(B$t$$B$NCf$K$"$l$P!$$=(B
$B$N@aE@$N8=:_$NCM$r(B$v$$B$KBeF~$7$?$"$H!$@aE@$K?7$?$JCM(B$v'$$B$r3JG<$9$k!%(B
$B$J$1$l$P!$%-!<(B$i$$B$HCM(B$v'$$B$r$b$D@aE@$r(B$t$$B$KA^F~$7!$(B$v$$B$K$OFCJL$NCM$rBeF~$9$k!%(B

\item{${\it delete}(i,v,t)$:} $B%-!<(B$i$$B$r$b$D@aE@$,LZ(B$t$$B$K$"$l$P!$$=$N@a(B
$BE@$N8=:_$NCM$r(B$v$$B$KBeF~$7$?$"$H!$@aE@$r>C5n$9$k!%$J$1$l$P(B$v$$B$KFCJL$N(B
$BCM$rBeF~$9$k!%(B
\end{description}


\section{$B4XO"8&5f(B}

\subsection{$BY(J?2=$H%H%C%W%@%&%sY(J?2=(B}\label{subsection:splaying}

$B%9%W%l!<LZ$K$*$1$k(B
$BY(J?2=$H$O!$%"%/%;%9$7$?@aE@$K;j$k%Q%9$ND9$5$r$*$h$=H>J,$K$7$D$D!$$=$N(B
$B@aE@$rLZ$N:,$K0\F0$5$;$kA`:n$G$"$j!$?^(B\ref{figure:splaying} $B$K<($9(B
zig, zig-zig, zig-zag$BA`:n$r%\(B
$B%H%`%"%C%W$K7+$jJV$9!%0J2<K\O@J8$G$O!$:81&BP>N$JA`:n72$O$=$NJRJ}$N$_$r<((B
$B$9!%$^$??^Cf$N>.J8;z$O@aE@!$BgJ8;z$OItJ,LZ$r<($9!%(B
%
${\it update}$, ${\it delete}$$BEy$N8DJL$N(B
$BA`:n%"%k%4%j%:%`$K$D$$$F$OB?$/$NJQ<o$,$"$k!%Y(J?2=$NBg$-$JFCD'$O!$%"%/(B
$B%;%9$7$?%Q%9$N>e$K$J$$@aE@$r!$9b!9(B${\rm O}(1)$$BCJ$7$+?<$/$7$J$$$3$H(B
$B$G$"$k!%(B

\begin{figure*}
{\footnotesize\baselineskip=8pt
\begin{verbatim}
                                             z        x              z            _x_
                  y           x             / \      / \            / \          /   \
                 / \         / \           y   D    A   y          y   D        y     z
                x   C  ==>  A   y         / \    ==>   / \        / \     ==>  / \   / \
               / \             / \       x   C        B   z      A   x        A   B C   D
              A   B           B   C     / \              / \        / \
                                       A   B            C   D      B   C
                       (a)                       (b)                      (c)
\end{verbatim}
}
\caption{
$B%\%H%`%"%C%WY(J?2=A`:n$N(B1$B%9%F%C%W!%(B % \cite{ST85}
$x$ $B$,%"%/%;%9$7$?@aE@!%(B(a) zig: 1$B2s$N1&2sE>(B($y$$B$,:,$N>l9g(B
$B$N$_(B)$B!$(B
(b) zig-zig: $B;^(B$yz$$B$H;^(B$xy$$B$r$3$N=g$K1&2sE>!$(B(c) zig-zag: $B;^(B$xy$
$B$r:82sE>$7!$$G$-$?;^(B$xz$$B$r1&2sE>!%(B}
\label{figure:splaying}
\end{figure*}


$BY(J?2=$O%\%H%`%"%C%W$JJQ7AA`:n$G$"$k$?$a!$JBNsA`:n$K$OE,$5$J$$!%(B
$BJ88%(B\cite{ST85} $B$O%H%C%W%@%&%sY(J?2=$bDs0F$7$F$$$k$,!$$3$l$O<BAu$N(B
$BMF0W2=$,<g$JL\E*$G$"$j!$LZ$N:,$OA`:n=*N;$ND>A0$^$G3NDj$7$J$$!%(B


\subsection{$BJBNsA`:n$K4X$9$k2a5n$N8&5f(B}

$BOBED(B\cite{W90} $B$O!$JB9TO@M}7?8@8l(B\cite{S89} $B$NO@M}JQ?t$rMQ$$$?Y((B
$BJ?2=%"%k%4%j%:%`$rDs0F$7$F$$$k!%$3$l$O!$O@M}JQ?t$rMxMQ$7$F!$(B
$B%H%C%W%@%&%sY(J?2=$r(Bin-place$B$G9T$J$&$h$&$K$7$?$b$N$H8+$J$9$3$H$b$G$-$k(B
$B$,!$(B${\it update\/}$$B$N$h$&$K!$BP>]$H$J$k@aE@$,A`:n=*N;8e$NLZ$KB8:_$9$k$3(B
$B$H$,$o$+$C$F$$$k>l9g$O!$LZ$N:,$N%-!<$rA`:n$N:G=i$K7h$a$kE@$,Bg$-$JFCD'$G(B
$B$"$k!%(B
$B$7$+$7$3$N5;K!$O!$(B
${\it delete\/}$$B$N$h$&$K!$A`:n7k2L$NLZ$N:,$,;vA0$K$o$+$i(B
$B$J$$>l9g$K$OE,MQ$G$-$J$$!%(B


\subsection{$B%H%C%W%@%&%sY(J?2=$NLdBjE@(B}

$B%H%C%W%@%&%sY(J?2=$K$h$k(B${\it update\/}$$B$O!$:,$N%-!<$r:G=i$K3NDj$9$k$h(B
$B$&$K$7$F$b!$JBNs=hM}$N4QE@$+$i$OLdBj$,;D$k!%$?$H$($P!$@aE@(B
$x(<b)$($<$$B$O%-!<$K$h$k=g=x4X78(B)$B$N(B${\it update\/}$$B$K$h$C$F5/$-$k<!$N(B
zig-zig$BA`:n(B\cite{W90}  $B$r9M$($k!J(B$L$ ($R$)$B$O!$LZ(B$C$$B$r%H%C%W%@%&%sY(J?(B
$B2=$7$?7k2L$N:8(B($B1&(B)$BItJ,LZ$G!$$"$H$G3NDj!K!%(B

\medskip
{\footnotesize\baselineskip=8pt
\begin{verbatim}
                a             x        
               / \           / \
              b   A         L   b 
             / \     ==>       / \
            C   B             R   a
                                 / \
                                B   A
\end{verbatim}
}

$B$3$N(B${\it update\/}$$B$N8e!$(B$y(<x)$, $z(>b)$$B$X$N%"%/%;%9$,$3$N=g$KB3$/$H(B
$B$9$k!%(B$x$$B$X$N%"%/%;%9;~$K(B$x$$B$,ItJ,LZ(B$C$$B$NCf$K$"$C$?>l9g!$(B$L$$B$N:,$,3N(B
$BDj$9$k$N$OCY$/$J$k!%$7$+$7(B$L$$B$N:,$,3NDj$9$k$^$G$O!$<!$N(B$y$$B$X$N%"%/%;(B
$B%9$,(Bzig, zig-zig, zig-zag$B$N$I$l$r$^$:E,MQ$9$k$+7h$a$i$l$J$$!%(B
$B$=$3$G(B3$BHVL\$N(B
$z$$B$X$N%"%/%;%9!JA0$NA`:n$K$h$C$F1F6A$r<u$1$k$3$H$N$J$$(B$b$$B$N1&ItJ,LZ$K(B
$B8~$+$&!K$,D9;~4V%V%m%C%/$7$F$7$^$&!%(B

$B:o=|A`:n$O$5$i$KLdBj$G$"$k!%LZ$+$i@aE@(B$x$$B$r:o=|$9$k$K$O!$$=$N:8It(B
$BJ,LZ$N:GBg$N@aE@(B$y$$B$rC5$7$F$=$l$r(B$x$$B$N>l=j$K0\$9$3$H$,4pK\$H$J(B
$B$k!%$7$+$7!$Y(J?2=$NM-L5$K$+$+$o$i$:!$(B$y$$B$,8+$D$+$k$^$G$O(B$x$$B$N>l=j(B
$B$K$/$k?7$?$J%-!<$O3NDj$;$:!$8eB3$NA`:n$r%V%m%C%/$7$F$7$^$&!%0J2<$N$h$&(B
$B$J2r7hK!$b9M$($i$l$k$,!$$$$:$l$b$&$^$/F0:n$7$J$$!%(B

\begin{enumerate}
\item % {\bf $B0l;~E*$J%-!<(B}
$y$$B$,8+$D$+$k$^$G!$(B$x$$B$r0l;~E*$J%-!<$H$7$FMxMQ$9$k$H!$(B
$y\le z\le x$$B$G$"$k$h$&$J@aE@(B$z$$B$X$NA`:n$r8m$C$?J}8~$XF3$/!%(B

\item % {\bf $BAPJ}8~%j%9%H(B}
$x$$B$ND>A0$NMWAG(B$y$$B$K(B${\rm O}(1)$$B;~4V$G%"%/%;%9$9$k$?$a$K!$3F@aE@$,D>A0$H(B 
$BD>8e$N@aE@$X$N%]%$%s%?$rJ];}$9$k$3$H$,9M$($i$l$k!%$3$l$i$N%]%$%s%?$OLZ(B
$B$NY(J?2=;~$KJQ99$9$kI,MW$,$J$$$H$$$&FCD'$,$"$k!%(B
% 
$B$7$+$7$3$NJ}K!$OC`<!A`:n$N$H$-$7$+$&$^$/F0:n$7$J$$!%(B
%
$B$J$<$J$i$3$N:o=|A`:n$NA0$NA`:n$,(B$x$$B$H(B$y$$B$r7k(B
$B$V%Q%9$r2<9_Cf$G!$$$$:$l(B$y$$B$KE~C#$9$k$+$b$7$l$J$$$+$i$G$"$k!%(B
\end{enumerate}

$B$7$?$,$C$F$3$3$G$O!$9b!9(B${\rm O}(1)$$B8D$N@a$r;\>{$7$D$D!$87L)$K%H%C%W%@%&(B
$B%s$KLZ$rJQ7A$7$F$f$/%"%k%4%j%:%`$r9M$($k$3$H$H$9$k!%(B

\section{$BJBNs99?7%"%k%4%j%:%`(B}\label{section:update}

$BK\@a$G$O!$8eB3$NA`:n$r%V%m%C%/$7$J$$(B${\it update\/}$$BA`:n$rM?$($k!%4pK\E*$J(B
$B%"%$%G%"$O!$(Bzig-zig$B$H(Bzig-zag$B$NN>J}$K$D$$$F!$%"%/%;%9$7$?@aE@$r$=$N?<$5$N(B
$BH>J,$^$G$7$+Ib>e$5$;$J$$H>Y(J?2=!J(Bsemi-splaying$B!K$rMQ$$$k$3$H$G$"$k!JJ88%(B
\cite{ST85} $B$NH>Y(J?2=$O!$(Bzig-zig$B$N$_$,Y(J?2=$H0[$J$C$F$$$?!K!%(B$x$$B$r99?7BP(B
$B>]$N@aE@$H$9$k$H!$%"%k%4%j%:%`$O0J2<$N$h$&$K$J$k!%(B

% \begin{itemize}
\medskip\noindent (a)
% \item[(a)]
$B6u$NLZ$KBP$9$kA^F~$O2<?^:8$NA`:n!$!J6u$G$J$$!KLZ$N:,$KBP$9$k99?7$O(B
$B2<?^1&$NA`:n$r9T$J$&!%(B

\medskip
{\footnotesize\baselineskip=8pt
\begin{verbatim}
                             x          x
          ==>  x            / \   ==>  / \
                           A   B      A   B
\end{verbatim}
}

\medskip\noindent (b)
% \item[(b)]
zig: 
$x$$B$,:8ItJ,LZ$N:,$G$"$k>l9g$O2<?^:8$NA`:n!$(B$x$$B$,B8:_$9$Y$-:8ItJ,LZ$,6u$N(B
$B>l9g$O2<?^1&$NA`:n$r9T$J$&!%(B

\medskip
{\footnotesize\baselineskip=8pt
\begin{verbatim}
        a           x             a       x
       / \         / \             \       \
      x   C  ==>  A   a             C  ==>  a 
     / \             / \                     \
    A   B           B   C                     C
\end{verbatim}
}

\medskip\noindent (c)
% \item[(c)]
zig-zig: $B2<?^:8$NLZ$K$*$1$k(B$x (<b)$$B$NC5:w$G$O!$(B
1$B2s$N2sE>$r9T$J$$!$%"%/%;%9$7$?%Q%9$ND9$5$r(B1$BC;=L$7!$!JC;=LA0$ND9$5(B
$B$G!K(B2$B%l%Y%k2<9_$9$k!%<!$OItJ,LZ(B$A$$B$KBP$7$F:F5"E*$KC5:w$r9T$J$&!%(B

\medskip
{\footnotesize\baselineskip=8pt
\begin{verbatim}
                  a           b
                 / \         / \ 
                b   C  ==>  A   a
               / \             / \
              A   B           B   C
\end{verbatim}
}

\medskip\noindent (d)
% \item[(d)]
zig-zag: $B2<?^:8$NLZ$K$*$1$k@aE@(B$x$ ($b<x<a$) $B$NC5:w$G$O!$(B
2$B2s$N2sE>$r9T$J$$!$%"%/%;%9$7$?%Q%9$r(B1$BC;=L$7!$(B3$B%l%Y%k2<9_$9$k!%(B

\medskip
{\footnotesize\baselineskip=8pt
\begin{verbatim}
         a               a              _c_
        / \             / \            /   \ 
       b   D           c   D          b     a
      / \     ==>     / \     ==>    / \   / \
     A   c           b   C          A   B C   D
        / \         / \
       B   C       A   B
\end{verbatim}
}

\noindent
$x=c$$B$J$i$P$3$l$GC5:w=*N;$G$"$k!%(B$x<c$$B$J$i$P(B$B$$B$NCf$+$i(B$x$$B$r:F5"E*$K(B
$BC5:w$9$k!%(B$x>c$$B$J$i$P(B$C$$B$NCf$+$i:F5"E*$KC5:w$9$k!%(B$x\ge c$$B$N>l9g$K$O(B
$BFs$D$a$N2sE>A`:n$r>JN,$9$k$3$H$b9M$($i$l$k!%(B
%
$b$$B$N1&ItJ,LZ$,6u$N>l9g$O!$$=$3$K@aE@(B$x$$B$rA^F~(B
$B$7$?$"$H!$>e$K=R$Y$?2sE>A`:n$r9T$J$&!%(B

% \end{itemize}
\medskip
$B0J>e$NA`:n$G!$%"%/%;%9$7$?%Q%9$ND9$5$O:G0-$G$bLs(B$2/3$$B$K$J$k!%(B

\section{$BJBNs:o=|%"%k%4%j%:%`(B}\label{section:delete}

$BJBNs:o=|$N$?$a$N4pK\E*$JCeA[$O!$Y(J?2=A`:n$r!$:o=|$9$Y$-@aE@$r2<9_$5(B
$B$;$k$?$a$KMxMQ$9$k$3$H$G$"$k!%$3$l$^$G$O!$Y(J?2=A`:n$O$b$C$Q$i!$:FEY%"%/(B
$B%;%9$7$=$&(B
$B$J@aE@$rIb>e$5$;$k$?$a$KMQ$$$i$l$F$-$?!%$3$3$G=EMW$J$3$H$O!$:o=|BP>]$N(B
$B@aE@0J30$O9b!9(B${\rm O}(1)$$B%l%Y%k$7$+2<9_$5$;$J$$$h$&$K$9$k$3$H$G$"$k!%(B
$B0J2<$G$O!$(B$z$$B$r:o=|BP>]$N@aE@$H$9$k!%(B

$B$^$:!$:,@aE@$,(B$z$$B$G$"$k>l9g$r9M$($k!%$3$N>l9g!$(Bzipping$B$H8F$VA`:n$K$h$C$F(B
$B$=$l$r(B``$BMF0W$K(B''$B:o=|$G$-$k>l=j$^$G2<9_$5$;$k!%@aE@$,(B``$BMF0W$K(B''$B:o=|$G$-(B
$B$k$H$O!$$=$N:8ItJ,LZ!$1&ItJ,LZ!$:8ItJ,LZ$N1&ItJ,LZ!$1&ItJ,LZ$N:8ItJ,LZ$N(B
$B$$$:$l$+$,6u$G$"$k$3$H$G$"$k!%:,@aE@$N2<9_$K$h$C$F!$$=$N:8ItJ,LZ$H(B
$B1&ItJ,LZ$NK%$$9g$;$,5/$-$k!%(B

% \begin{enumerate}
\medskip\noindent (a)
% \item[(a)]
``$BMF0W$K(B''$B:o=|$G$-$k>l9g(B:

\medskip
{\footnotesize\baselineskip=8pt
\begin{verbatim}
        z           a             z          B
       / \         / \             \   ==>            
      a   B  ==>  A   B             B                 
     /                      
    A                       
\end{verbatim}
}

\medskip\noindent (b)
% \item[(b)]
``$BMF0W$K(B''$B:o=|$G$-$J$$>l9g(B: $z$$B$N:8ItJ,LZ$K(Bzig-zag$B$r;\$7!$$=(B
$B$N7k2L$G$-$k(B$z$$B$N1&ItJ,LZ$K!$!J0l$D$a$H$O:81&BP>N$J!K(Bzig-zag$B$r;\$9!%(B

\medskip
{\footnotesize\baselineskip=8pt
\begin{verbatim}
     ___z___            _b_            __b__
    /       \          /   \          /     \
   a         d        a     z        a     __e
  / \       / \  ==> / \   / \  ==> / \   /   \
 A   b     e   D    A   B C   d    A   B z     d
    / \   / \                / \        / \   / \
   B   C F   E              e   D      C   F E   D
                               / \
                              F   E
\end{verbatim}
}

\noindent
4$B2s$N2sE>$G(B$z$$B$O(B2$B%l%Y%k2<9_$9$k!%(B$z$$B$N?7$?$JItJ,LZ(B
$B$O!$F1$8%l%Y%k$K$H$I$^$k!%$=$l0J30$N@aE@$b9b!9(B1$B%l%Y%k$7$+2<9_(B
$B$7$J$$!%(B$z$$B$N?7$?$JItJ,LZ$KBP$7$F:F5"E*$K:o=|A`:n$r9T$J$&$,!$(B$z$$B$N2<(B
$B$K$J$$@aE@$,$=$l$K$h$C$F$5$i$K2<9_$9$k$3$H$O$J$$!%(B
% \end{enumerate}

\medskip
$B@aE@(B$z$$B$,:,$G$"$k$H$O8B$i$J$$>l9g$O!$$^$:Bh(B\ref{section:update} $B@a$N(B
$BJ}K!$G(B$z$$B$rC5:w$9$k!%$3$l$O:,$+$i(B$z$$B$K;j$k%Q%9$rC;=L$9$k8z2L$r$b$D!%$D$.(B
$B$K!$(B$z$$B$r(Bzipping$B$K$h$C$F2<9_$5$;$F:o=|$9$k!%(B

Zipping$BA`:n$O%Q%9$NC;=L$r9T$J$o$J$$$,!$%"%/%;%9$7$?@aE@$OIb>e$5$;(B
$B$k$H$$$&86B'$K$7$?$,$&$J$i$P!$(Bzipping$B$K@h$@$C$F!$:8ItJ,LZ$N:GBgMWAG$K;j(B
$B$k%Q%9$H1&ItJ,LZ$N:G>.MWAG$K;j$k%Q%9$r$=$l$>$l%H%C%W%@%&%s$NH>Y(J?2=(B
$B!JBh(B\ref{section:update} $B@a(B(c)$B!K$K$h$C(B
$B$FC;=L$9$l$P$h$$!%$3$NC;=L2=$O(Bzipping$B$HJB9T$7$F9T$J$&$3$H$,$G$-$k!%(B

Zipping$B$O99?7A`:n$H0[$J$j!$3F@aE@$N%-!<CM$rFI$`$3$H$J$/LZ$r2<9_$9$k!%(B
$B$^$?(Bzipping$B$O!$LZ(B$T_1$$B$HLZ(B$T_2$$B!J(B$T_1$$B$N$I(B
$B$N%-!<$b!$(B$T_2$$B$N$I$N%-!<$h$j$b>.$5$$$b$N$H$9$k!K$H$N%H%C%W%@%&%sJ;9gA`:n(B
$B$K$b1~MQ$G$-$k!%$9$J$o$A!$?7$?$J@aE@!J%-!<$OG$0U!K$rD4C#$7!$$=$N:8ItJ,LZ(B
$B$r(B$T_1$$B!$1&ItJ,LZ$r(B$T_2$$B$H$7$F0l$D$NLZ$r9=@.$7$?(B
$B$N$A!$:,$r>C5n$9$l$P$h$$!%(B


\section{$B7W;;NL$K4X$9$k7k2L$H9M;!(B}

$B8zN($NFs$D$N<\EY$N$&$A!$%9%k!<%W%C%H$K$D(B
$B$$$F$OMF0W$K5DO@$,$G$-$k!%$9$J$o$A!$Fs$D$NA`:n$O!$%l%Y%k(B$n$$B!J:,$r%l(B
$B%Y%k(B$0$$B$H$7$F!K$N@aE@$r(B${\rm O}(n)$$B2s(B --- ${\it update\/}$$B$O9b!9(B$(n+2)$$B2s!$(B
zipping$B$O9b!9(B$(2n+2)$$B2s(B ---
$B$N2sE>A`:n$N$N$A$K3NDj$5$;$k!%(B
$B$5$i$K$I$A$i$NA`:n$b!$O"B3$9$k9b!9(B$3$
$B%l%Y%k$N@aE@$rF1;~$K;\>{$9$k$@$1$G$h$$!%$3$l$i$N$3$H$+$i!$LZ$NBg$-$5$d?<(B
$B$5$K$h$i$J$$%9%k!<%W%C%H$G!$A`:n7ONs$r%Q%$%W%i%$%sE*$KJBNs=hM}$9$k$3(B
$B$H$,$G$-$k!%(B

$B%l%9%]%s%9$O!$(B${\it update\/}$$B$K$D$$$F$O!$DL>o$N%9%W%l!<(B
$BLZ$HF1Ey$N=~5Q7W;;NL$r$b$D$3$H$,>ZL@$G$-$k!%6qBNE*$K$O!$(B
$B@aE@(B$x$$B$N(B{\bf $BBg$-$5(B}$s(x)$$B$r(B$x$$B$r:,$H$9$kItJ,LZ$N@aE@?t$HDj5A$7!$(B
{\bf $B%i%s%/(B}$r(x)$$B$r(B$\log_2(s(x))$$B$H$9$k!%(B
$B$=$7$F(B
%
$BLZ$N%]%F%s%7%c%k$r!$$9$Y$F$N@aE@$N%i%s%/$NOB$HDj5A$9$k!%(B
$B$9$k$H!$(B${\it update\/}$$B$N=~5Q;~4V!$$D$^$j2sE>A`:n$N2s?t$GB,$C$?=j(B
$BMW;~4V$KA`:nA08e$N%]%F%s%7%c%k$NJQ2=$r2C$($?$b$N$O!$(B$n$$B$rLZ$N@aE@?t$H$7(B
$B$F!$(B${\rm O}(\log n)$$B$G$"$k$3$H$r<($9$3$H$,$G$-$k!J(B\cite{ST85} $B$N$h$&(B
$B$K!$@aE@$K0[$J$k=E$_$r$D$1$F(B$s$$B$d(B$r$$B$rDj5A$9$k$3$H$K$h$j!$$h$j6/$$@-<A(B
$B$r<($9$3$H$b$G$-$k$,!$$3$3$G$O>J$/!K!%(B

$B0lJ}!$(B${\it delete\/}$$B$K$D$$$F$O!$(B\cite{ST85} $B$N2r@OJ}K!$G$O!$BP?tE*=~5Q7W(B
$B;;NL$rF3$/$3$H$O$G$-$J$$!%$=$N$3$H$r<($9$?$a$K!$Bh(B\ref{section:delete}
$B@a(B(b)$B$N(B4$B2s$N2sE>$K$h$k%]%F%s%7%c%kJQ2=$r9M$($k!%(B

$BBh(B\ref{section:delete} $B@a(B(b)$B$N0lHV1&B&(B
$B$NLZ$N%i%s%/4X?t$r(B$r'$$B$H$9$k!%A`:nA08e$N%]%F%s%7%c%k$NJQ2=$r!$(B
$k$$B$r$"$k@5Dj?t$H$7$F(B$k(r'(b)-r'(z))$$B0JFb$K2!$5$($k$3$H$,$G$-$k$3$H$r<($9$N$,!$(B
\cite{ST85} $B$K$*$1$k=~5Q7W;;NL$N>ZL@5;K!$N4pK\$G$"$C$?!%$7$+$7!$$3$NLZ$K(B
$B$D$$$F(B$s(A)= s(B) = s(C) = h\gg t = s(D) = s(E) = s(F)$
$B$r2>Dj$9$k$H!$%]%F%s%7%c%kJQ2=$,(B$h/t$$B$K4X$7$F(B${\rm O}(\log
(h/t))$$B$H$J$k!%0lJ}(B$r'(b)-r'(z)$$B$O(B$h/t$$B$K4X$7$F(B${\rm O}(1)$$B$G$"$k$N$G!$$=(B
$B$N$h$&$J(B$k$$B$OB8:_$7$J$$$3$H$,$o$+$k!%(BZipping$B$K@hN)$C$F%Q%9C;=L2=$r9T$J$C(B
$B$?>l9g$K$D$$$F$b!$F1MM$N$3$H$,<($;$k!%(B

$B$7$+$7!$Bh(B\ref{section:delete} $B@a$N:o=|A`:n$O!$(B
%
$B%"%/%;%9$7$?@aE@$K;j$k%Q%9>e$N@aE@$N?<$5$,LsH>J,$K$J$j!J;vA0$K%Q%9(B
$BC;=L2=$r;\$7$?>l9g!K!$$=$l0J30$N@aE@$b9b!9Dj?t%l%Y%k$7$+D@$^$J$$(B
%
$B$H$$$&!$@aE@$NIb$-D@$_$K$D$$$F$N%9%W%l!<LZ0lHL$N@-<A$OK~$?$7$F$$$k!%(B
%
$B$G$O0lHL$K!$$3$NFs$D$N@-<A$rK~$?$9<+8JD4@0E*$JLZ%"%k%4%j%:%`$G!$J?6Q%l%9(B
$B%]%s%9$,BP?t;~4V$G2!$5$($i$l$J$$$h$&$J!$==J,D9$$A`:n7ONs$OB8:_$9(B
$B$k$N$@$m$&$+!)(B $B$3$l$OL$2r7h$G$"$k$,!$K\9F$GDs0F$7$?FsA`:n$K(B
$B$D$$$F$O!$J?6Q%l%9%]%s%9$O>/$J$/$H$b(B${\rm O}(\sqrt n)$$B!J99?7$N$_$J$i$P(B
${\rm O}(\log n)$$B!K$HM=A[$5$l$k!%(B

$B$=$N:,5r(B
% 
$B$H$7$F!$3F@aE@$N:o=|$7$d$9$5$NJQ2=$r9M$($k!%(B
$B@aE@(B$x$$B$N:o=|MF0W@-(B$d(x)$$B$r!$(B$x$$B$+$i$=$ND>A0$N%-!<(B$x_-$$B$r$b$D@a(B
$BE@$X;j$k%Q%9D9!J(B$x_-$$B$,B8:_$7$J$$>l9g$d!$(B$x_-$$B$,(B$x$$B$N;RB9$G(B
$B$J$$>l9g$O(B$0$$B$HDj$a$k!K$HD>8e$N%-!<(B$x_+$$B$r$b$D@a$K;j$k%Q%9D9$N:G>.CM(B
$B$HDj$a$k$H!$(B${\it delete\/}$$B$O!$(B$d$$B$NBg$-$J@aE@$N>C5n$K$O;~4V$,$+$+$k$b(B
$B$N$N!$;D$C$?3F@aE@$N(B$d$$B$r9b!9(B${\rm O}(1)$
$B$7$+Bg$-$/$7$J$$!%$^$?(B${\it update\/}$$B$G?7$?$KA^F~$7$?@aE@$N(B$d$
$B$O(B$1$$B$G$"$j!$$9$G$KB8:_$7$F$$$?3F@aE@$N(B$d$$B$b9b!9(B${\rm O}(1)$$B$7$+Bg$-(B
$B$/$J$i$J$$!%!J%\%H%`%"%C%WY(J?2=$O!$@aE@$N(B$d$$B$NA}2C$rDj?t$G(B
$B2!$5$($k$3$H$,$G$-$J$$!%!K3F@aE@$N(B$d$$B$NAmOB$O(B${\rm O}(n)$$B$G$"$k$+$i!$(B
$B?7$?$J@aE@$NDI2C$H!$(B$d$$B$NBg$-$J@aE@$N>C5n$,7+$jJV$5$l$k$H$$$&:G0-$NA`:n(B
$B7ONs$r9M$($F$b!$J?6Q$N<j4V$O(B${\rm O}(\sqrt n)$$B$G$"$j!$<BMQ>e$N8zN($O(B
$B99?7A`:n$N$_$N>l9g$H$[$H$s$IJQ$o$i$J$$$HM=A[$5$l$k!%(B

\section{$B$^$H$a$H:#8e$N2]Bj(B}

$B@aE@$NIb$-D@$_$K4X$9$kK>$^$7$$@-<A$rJ]$A!$$+$D!J7W;;NL$N0UL#$G!K:GE,$J%9%k!<(B
$B%W%C%H$r$b$D<+(B
$B8JD4@0FsJ,LZ$NJBNsA`:n%"%k%4%j%:%`$rDs0F$7$?!%@aE@$NFI=P$7$dDI2C$K4X$7$F(B
$B$OBP?tE*=~5Q7W;;NL$r;}$D$3$H$,>ZL@$G$-$F$*$j!$$5$i$K%"%/%;%9%Q%?!<%s$NJP(B
$B$j$dJQ2=$KBP$9$kDI=>@-$J$I!$%9%W%l!<LZ$N;}$D6/NO$+$D4h7r$J@-<A(B
$B$NB?$/$r0z$-7Q$$$G$$$k!%:o=|$N=~5Q7W;;NL$NNI$$M}O@E*8B3&$rF3$/$3$H$O:#(B
$B8e$N2]Bj$G$"$k!%$^$?!$%"%k%4%j%:%`$N<B:]E*8zN(!$JBNsJ,;64D6-$G$N<BAu!$1~(B
$BMQ$N8!F$$b:#8e$N2]Bj$G$"$k!%(B

\subsection*{$B<U<-(B}
$BK\O@J8$N=i4|$NHG$K$D$$$F5DO@$7$F$$$?$@$$$?(BRobert Tarjan$B;a!J(BPrinceton$BBg!K!$(B
$BLS<uE/;a!J(BNEC$B!KCfC+M42p;a!JAa0pEDBg!K$K46<U$9$k!%(B

\begin{thebibliography}{9}
\bibitem{LS86} V. Lanin and D. Shasha, A Symmetric Concurrent B-Tree Algorithm.
In {\it Proc.\ 1986 Fall Joint Computer Conference}, IEEE, 1986,
pp.~380--389.

\bibitem{ST85} D. D. Sleator and R. E. Tarjan, Self-Adjusting Binary Search
Trees.  {\it J. ACM}, Vol.~32, No.~3 (1985), pp.~652--686.

\bibitem{S89} E. Shapiro, The Family of Concurrent Logic Programming Languages.
{\it Computing Surveys}, Vol.~21, No.~3 (1989), pp.~413--510.

\bibitem{W90} $BOBED5WH~;R(B, $B%9%W%l%$LZ$NJBNs%G!<%?C5:w(B.  In {\it Proc.\ KL1
Programming Workshop '90}, ICOT, Tokyo, 1990, pp.~42--49.

\end{thebibliography}
\end{document}
