《數(shù)據(jù)結(jié)構(gòu)與算法之美》，王爭(zhēng) 著

標(biāo)簽：數(shù)據(jù)結(jié)構(gòu)、算法

第7章 跳表、并查集、線段樹和樹狀數(shù)組

一、跳表

這一部分介紹了

• 跳表的由來(lái)

• 用跳表查詢到底有多快

• 跳表是不是浪費(fèi)內(nèi)存

• 高效插入和刪除

• 跳表索引動(dòng)態(tài)更新

• 跳表的應(yīng)用：為什么Redis的有序集合用跳表而非紅黑樹來(lái)實(shí)現(xiàn)

筆記：跳表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，各種基本操作的性能是不錯(cuò)的，但是，這個(gè)數(shù)據(jù)結(jié)構(gòu)比較新，很多編程語(yǔ)言沒有封裝，開發(fā)者要使用跳表要自己從零開始實(shí)現(xiàn)。

二、并查集

這一部分介紹了

• 并查集的由來(lái)

• 基于鏈表的思路實(shí)現(xiàn)并查集

• 基于樹的思路實(shí)現(xiàn)并查集

筆記：作者通過(guò)用不同的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)并查集，這種組織方式對(duì)學(xué)習(xí)者有效

三、線段樹

這一部分介紹了

• 區(qū)間統(tǒng)計(jì)問(wèn)題（統(tǒng)計(jì)某個(gè)區(qū)間的數(shù)據(jù)個(gè)數(shù)）：使用線段樹求解

• 線段樹的其他應(yīng)用：統(tǒng)計(jì)某個(gè)區(qū)間的數(shù)據(jù)之和、最大值和最小值、以及某個(gè)區(qū)間的第K大值

筆記：區(qū)間統(tǒng)計(jì)問(wèn)題，是很多編程比賽經(jīng)常出現(xiàn)的問(wèn)題，實(shí)際工程中也有很多應(yīng)用。當(dāng)然，實(shí)現(xiàn)線段樹還是需要一定的編程能力的。

四、樹狀數(shù)組

這一部分介紹了

前綴和問(wèn)題

樹狀數(shù)組和線段樹的對(duì)比

如何用樹狀數(shù)組實(shí)現(xiàn)一個(gè)高性能】低延遲的實(shí)時(shí)排行榜

筆記：所有可以用樹狀數(shù)組來(lái)解決的問(wèn)題都可以用線段樹來(lái)解決。但是如果能用樹狀數(shù)組來(lái)解決，代碼會(huì)更加簡(jiǎn)單，空間消耗更少。

這一章介紹的跳表、并查集、線段樹和樹狀數(shù)組屬于比較高級(jí)的數(shù)據(jù)結(jié)構(gòu)，所謂高級(jí)，其實(shí)就是一般數(shù)據(jù)結(jié)構(gòu)教材和課程是沒有、不講也不考的。而且，這類數(shù)據(jù)結(jié)構(gòu)一般不常用，只是在某些特定問(wèn)題和特殊需求時(shí)有奇效。

跳表是基于有序鏈表、添加多級(jí)索引構(gòu)建而成，支持快速的查找、插入、刪除數(shù)據(jù)操作。除此之外，跳表還支持快速地查找落在某個(gè)區(qū)間的數(shù)據(jù)。

并查集主要用來(lái)根據(jù)兩兩對(duì)象之間的直接關(guān)系，快速查詢?nèi)我鈨蓚€(gè)對(duì)象之間是否存在直接或間接的關(guān)系。

線段樹主要用來(lái)做區(qū)間統(tǒng)計(jì)，比如統(tǒng)計(jì)落在某個(gè)數(shù)值區(qū)間的數(shù)據(jù)個(gè)數(shù)。

樹狀數(shù)組主要用于求動(dòng)態(tài)數(shù)據(jù)集合的前綴和。