?? 6_2_1 哈希avl樹的基本概念 - 《多任務(wù)下的數(shù)據(jù)結(jié)構(gòu)與算法》 - 免費試讀 - book_csdn_net.htm
字號:
urchinTracker();
</SCRIPT>
<!-- /公共頁頭 --><LINK
href="C:\Documents and Settings\K&G\桌面\6_2_1 哈希AVL樹的基本概念 - 《多任務(wù)下的數(shù)據(jù)結(jié)構(gòu)與算法》 - 免費試讀 - book_csdn_net.files\style(1).css"
type=text/css rel=stylesheet>
<DIV id=booknav2>
<DIV id=booknavtop>
<UL>
<LI><A href="http://book.csdn.net/">首頁</A> </LI>
<LI><A href="http://book.csdn.net/book/morelz.aspx">精品連載</A> </LI>
<LI><A href="http://club.book.csdn.net/people/myclub.aspx">我的書友會</A> </LI>
<LI><A href="http://club.book.csdn.net/people/putblog.aspx">圖書秀</A> </LI>
<LI><A href="http://club.book.csdn.net/people/alllist.aspx">書架</A> </LI>
<LI><A href="http://blog.csdn.net/group/bookread/" target=_blank>圈子</A> </LI>
<LI><A href="http://down.csdn.net/app/list.php?tid=502" target=_blank>資源下載</A>
</LI>
<LI><A href="http://bank.csdn.net/" target=_blank><FONT
style="FONT-WEIGHT: bold">銀行</FONT></A> </LI></UL></DIV>
<SCRIPT type=text/javascript>
function IsBlank(obj) //查看對象的值是否為空
{
if(obj.replace(/^\s+|\s+$/,"")=="")
{
return true;
}
else
{
return false;
}
}
function SearchBook_Top()
{
if( !IsBlank(document.getElementById("txtTopKey").value))
{
var loc;
var szType;
if(document.getElementById("listSearchType").value==null)
{
szType= document.getElementById("listSearchType").options(document.getElementById("listSearchType").selectedIndex).value;
}
else
{
szType= document.getElementById("listSearchType").value;
}
if(szType==1)
loc="http://book.csdn.net/book/morelz.aspx?key="+escape(document.getElementById("txtTopKey").value);
else
loc="http://club.book.csdn.net/book/s.aspx?key="+escape(document.getElementById("txtTopKey").value);
self.location=loc;
}
}
</SCRIPT>
<DIV id=booknavbottom2>
<DIV class=hotleft><A href="http://book.csdn.net/subject/allbook.htm"
target=_blank>全部圖書</A> <FONT color=red>推薦</FONT>:<A
href="http://club.book.csdn.net/book/s.aspx?key=asp.net">ASP.NET</A> <A
href="http://club.book.csdn.net/book/s.aspx?key=ajax">Ajax</A> <A
href="http://club.book.csdn.net/book/s.aspx?key=spring">Spring</A> <A
href="http://club.book.csdn.net/book/s.aspx?key=Hibernate">Hibernate</A> <A
href="http://club.book.csdn.net/book/s.aspx?key=Java">Java</A></DIV>
<DIV class=hotright><SELECT id=listSearchType name=aa> <OPTION value=2
selected>書友會</OPTION> <OPTION value=1>連載</OPTION></SELECT><INPUT
onkeypress=if(event.keyCode==13){SearchBook_Top();} id=txtTopKey maxLength=25><INPUT onclick=SearchBook_Top(); type=button value=搜索 name=提交></DIV></DIV></DIV>
<DIV class=area>
<SCRIPT
src="6_2_1 哈希AVL樹的基本概念 - 《多任務(wù)下的數(shù)據(jù)結(jié)構(gòu)與算法》 - 免費試讀 - book_csdn_net.files/BookDetailAd.js"
type=text/javascript></SCRIPT>
<DIV class=col1>
<DIV class=lineBlue></DIV><!-- title -->
<DIV class=arcTitle>
<H1><A href="http://book.csdn.net/bookfiles/65">多任務(wù)下的數(shù)據(jù)結(jié)構(gòu)與算法 </A></H1>
<DIV style="FONT-SIZE: 15px; TEXT-ALIGN: center"><A
href="http://book.csdn.net/bookfiles/65/100652558.shtml">6.2.1 哈希AVL樹的基本概念
</A></DIV>
<DIV style="FONT-SIZE: 15px; TEXT-ALIGN: center"><A class=url
href="http://book.csdn.net/">http://book.csdn.net/</A> 2006-8-14 14:19:00 </DIV>
<DIV class=clear></DIV>
<DIV
style="BORDER-RIGHT: #0b5f98 1px solid; BORDER-TOP: #0b5f98 1px solid; MARGIN: 0px auto; BORDER-LEFT: #0b5f98 1px solid; WIDTH: 700px; BORDER-BOTTOM: #0b5f98 1px solid">
<DIV
style="PADDING-RIGHT: 1px; PADDING-LEFT: 1px; FLOAT: left; PADDING-BOTTOM: 1px; WIDTH: 16px; COLOR: white; PADDING-TOP: 1px; BACKGROUND-COLOR: #0b5f98">圖書導(dǎo)讀
</DIV>
<DIV
style="PADDING-LEFT: 2px; FLOAT: right; WIDTH: 670px; LINE-HEIGHT: 16pt; TEXT-ALIGN: left"><!--導(dǎo)讀-->
<H1 id=divCurrentNode
style="PADDING-LEFT: 2px; FONT-SIZE: 12px; WIDTH: 100%; COLOR: #b83507; TEXT-ALIGN: left">當(dāng)前章節(jié):<A
href="http://book.csdn.net/bookfiles/65/100652558.shtml"><FONT color=red>6.2.1
哈希AVL樹的基本概念</FONT></A></H1>
<DIV id=divRelateNode style="PADDING-LEFT: 2px">
<DIV style="FLOAT: left; WIDTH: 49%">·<A
href="http://book.csdn.net/bookfiles/65/100652555.shtml">5.1.3 樹的遍歷算法</A></DIV>
<DIV style="FLOAT: right; WIDTH: 49%">·<A
href="http://book.csdn.net/bookfiles/65/100652556.shtml">5.1.4 樹的編碼實現(xiàn)</A></DIV>
<DIV style="FLOAT: left; WIDTH: 49%">·<A
href="http://book.csdn.net/bookfiles/65/100652557.shtml">5.1.5
使用樹的遍歷算法來實現(xiàn)Xcopy功能</A></DIV>
<DIV style="FLOAT: right; WIDTH: 49%">·<A
href="http://book.csdn.net/bookfiles/65/100652559.shtml">6.2.2
哈希AVL樹的查找</A></DIV>
<DIV style="FLOAT: left; WIDTH: 49%">·<A
href="http://book.csdn.net/bookfiles/65/100652560.shtml">6.2.3
哈希AVL樹的插入</A></DIV>
<DIV style="FLOAT: right; WIDTH: 49%">·<A
href="http://book.csdn.net/bookfiles/65/100652561.shtml">6.2.4
哈希AVL樹的刪除</A></DIV></DIV></DIV></DIV>
<DIV class=clear></DIV></DIV><!-- main -->
<DIV id=main>
<DIV id=text>
<DIV id=csdn_zhaig_ad_yahoo_2></DIV>
<H3 style="MARGIN-LEFT: 0cm; TEXT-INDENT: 0cm; LINE-HEIGHT: 16.4pt"><A
name=_Toc122884816></A><SPAN lang=EN-US>6.2.1</SPAN><SPAN lang=EN-US>
</SPAN><SPAN style="FONT-FAMILY: 方正準(zhǔn)圓簡體">哈希</SPAN><SPAN
lang=EN-US>AVL</SPAN><SPAN style="FONT-FAMILY: 方正準(zhǔn)圓簡體">樹的基本概念</SPAN></H3>
<P class=MsoNormal style="LINE-HEIGHT: 16.4pt"><SPAN
style="FONT-FAMILY: 華康簡宋">前面介紹了復(fù)合數(shù)據(jù)結(jié)構(gòu)哈希紅黑樹，它避免了哈希表里數(shù)據(jù)無序及紅黑樹查找速度不足的缺點。在軟件設(shè)計中，經(jīng)常會追求設(shè)計更快的查找算法。像哈希表查找，一次就可以定位到數(shù)據(jù)，已經(jīng)夠快的了，但是哈希表對哈希函數(shù)的設(shè)計有很高要求，若哈希函數(shù)設(shè)計不好，理論上查找的最壞復(fù)雜度為</SPAN><SPAN
lang=EN-US>O(n)</SPAN><SPAN style="FONT-FAMILY: 宋體">；</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">在二叉樹中，查找速度較快的為</SPAN><SPAN lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹，能不能將哈希表和</SPAN><SPAN lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹結(jié)合起來，使得查找更快呢？</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.4pt"><SPAN
style="FONT-FAMILY: 華康簡宋">本節(jié)就討論另外一個復(fù)合數(shù)據(jù)結(jié)構(gòu)</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋; LETTER-SPACING: -0.1pt">—</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">—哈希</SPAN><SPAN lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹。顧名思義，哈希</SPAN><SPAN lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹是哈希表和</SPAN><SPAN lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹的復(fù)合數(shù)據(jù)結(jié)構(gòu)，那么哈希</SPAN><SPAN lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹是不是也采用和哈希紅黑樹同樣的復(fù)合方法呢？哈希</SPAN><SPAN
lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹的每個節(jié)點是不是既有哈希表的特性，又有</SPAN><SPAN
lang=EN-US>AVL</SPAN><SPAN style="FONT-FAMILY: 華康簡宋">樹的特性呢？</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 華康簡宋">如果將哈希</SPAN><SPAN lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹設(shè)計成類似哈希紅黑樹，通常</SPAN><SPAN lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹比紅黑樹查找要快，但插入刪除效率較低，哈希</SPAN><SPAN
lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹可以采用哈希表的查找方法進行查找，</SPAN><SPAN
lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹的查找方法在這里不起作用，因此，查找速度也就和哈希表一樣，還不如直接使用哈希紅黑樹。要想查找更快，有必要換個思路來設(shè)計哈希</SPAN><SPAN
lang=EN-US>AVL</SPAN><SPAN style="FONT-FAMILY: 華康簡宋">樹。</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 華康簡宋">設(shè)計哈希</SPAN><SPAN lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹的目的首先是要解決哈希表的缺點。哈希表的使用對哈希函數(shù)有很高要求，如果哈希函數(shù)設(shè)計不好可能有很多個數(shù)據(jù)具有相同的哈希值，而對這些相同哈希值的數(shù)據(jù)查找是采用順序查找方式，效率非常低。如果對哈希表具有相同哈希值的數(shù)據(jù)不使用鏈?zhǔn)椒椒ń鉀Q沖突，而采用</SPAN><SPAN
lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹來解決沖突，那么對具有相同哈希值的數(shù)據(jù)的查找將變成</SPAN><SPAN
lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹的查找，比鏈?zhǔn)降捻樞虿檎倚蕦⑻岣吆芏唷?lt;/SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 華康簡宋">哈希</SPAN><SPAN lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹與哈希表的區(qū)別就是</SPAN><SPAN lang=EN-US>bucket</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">中的指針是</SPAN><SPAN lang=EN-US>AVLTREE</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">的節(jié)點類型，因此用</SPAN><SPAN lang=EN-US>C</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">語言結(jié)構(gòu)體來描述哈希</SPAN><SPAN lang=EN-US>AVL</SPAN><SPAN
style="FONT-FAMILY: 華康簡宋">樹如下。</SPAN></P>
<P class=4><SPAN lang=EN-US>typedef BINTREEBASENODE AVLTREENODE</SPAN><SPAN
style="FONT-FAMILY: 宋體">；</SPAN></P>
<P class=4><SPAN lang=EN-US>typedef struct HASHAVLTREE_st {</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> AVLTREENODE
**ppBucket</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋體">；</SPAN><SPAN
lang=EN-US style="FONT-SIZE: 9pt"> /* </SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 華康簡宋">索引表指針</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> */</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> UINT
uBucketCount</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋體">；</SPAN><SPAN
lang=EN-US
style="FONT-SIZE: 9pt">
/* </SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 華康簡宋">索引表的大小</SPAN><SPAN
lang=EN-US style="FONT-SIZE: 9pt"> */</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> UINT
uNodeCount</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋體">；</SPAN><SPAN
lang=EN-US
style="FONT-SIZE: 9pt">
/* </SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 華康簡宋">表中實際節(jié)點的個數(shù)</SPAN><SPAN
lang=EN-US style="FONT-SIZE: 9pt"> */</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> UINT
uCurBucketNo</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋體">；</SPAN><SPAN
lang=EN-US
style="FONT-SIZE: 9pt">
/* </SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 華康簡宋">當(dāng)前要執(zhí)行的</SPAN><SPAN
lang=EN-US style="FONT-SIZE: 9pt">bucket</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 華康簡宋">序號</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> */</SPAN></P>
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -