數(shù)據(jù)結(jié)構(gòu)(data structure)是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，并確保經(jīng)過這些運(yùn)算以后所得到的新結(jié)構(gòu)仍保持原來的結(jié)構(gòu)類型。基本的數(shù)據(jù)結(jié)構(gòu)我們都接觸過，總體而言還是比較簡單的，本文我們就來聊一聊相對而言比較難的高級數(shù)據(jù)結(jié)構(gòu)。

下面為大家介紹3種高級數(shù)據(jù)結(jié)構(gòu)分別為：跳躍表，紅黑樹和B樹，接下來詳細(xì)看一下這3種數(shù)據(jù)結(jié)構(gòu)。

1.跳躍表

跳躍列表是對有序的鏈表增加上附加的前進(jìn)鏈接，增加是以隨機(jī)化的方式進(jìn)行的，所以在列表中的查找可以快速的跳過部分列表。是一種隨機(jī)化數(shù)據(jù)結(jié)構(gòu)，基于并聯(lián)的鏈表，其效率可比擬于紅黑樹和AVL樹(對于大多數(shù)操作需要O(logn)平均時(shí)間)，但是實(shí)現(xiàn)起來更容易且對并發(fā)算法友好。redis 的 sorted SET 就是用了跳躍表。

2.紅黑樹

我們對平衡二叉樹的定義往往是模棱兩可的，在這里大概說一下，左右子樹高度差用 HB(k) 來表示，當(dāng) k=0 為完全平衡二叉樹，當(dāng) k<=1 為AVL樹，當(dāng)k>=1 但是接近平衡的是紅黑樹，其它平衡的還有如Treap、替罪羊樹等，總之就是高度能保持在O(logn)級別的二叉樹。紅黑樹是一種自平衡二叉查找樹，也被稱為"對稱二叉B樹"，保證樹的高度在[logN,logN+1]（理論上，極端的情況下可以出現(xiàn)RBTree的高度達(dá)到2*logN，但實(shí)際上很難遇到）。它是復(fù)雜的，但它的操作有著良好的最壞運(yùn)行時(shí)間：它可以在O(logn)時(shí)間內(nèi)做查找，插入和刪除。

紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。在二叉查找樹強(qiáng)制一般要求以外，有如下額外要求：

1）節(jié)點(diǎn)是紅色或黑色。

2）根是黑色。

3）所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)，亦即空節(jié)點(diǎn)）。

4）每個(gè)紅色節(jié)點(diǎn)的子節(jié)點(diǎn)必須是黑色的。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）

5）從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

3.B樹

B樹有一種說法是二叉查找樹，每個(gè)結(jié)點(diǎn)只存儲一個(gè)關(guān)鍵字，等于則命中，小于走左結(jié)點(diǎn)，大于走右結(jié)點(diǎn)。但是實(shí)際上這樣翻譯是一種錯(cuò)誤，B樹就是 B-tree 亦即B-樹。

B-樹（B-tree）是一種自平衡的樹，能夠保持?jǐn)?shù)據(jù)有序。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)、順序訪問、插入數(shù)據(jù)及刪除的動(dòng)作，都在對數(shù)時(shí)間內(nèi)完成。B-樹，概括來說是一個(gè)一般化的二叉查找樹，可以擁有多于2個(gè)子節(jié)點(diǎn)（多路查找樹）。與自平衡二叉查找樹不同，B-樹為系統(tǒng)大塊數(shù)據(jù)的讀寫操作做了優(yōu)化。B-樹減少定位記錄時(shí)所經(jīng)歷的中間過程，從而加快存取速度。B-樹這種數(shù)據(jù)結(jié)構(gòu)可以用來描述外部存儲。這種數(shù)據(jù)結(jié)構(gòu)常被應(yīng)用在數(shù)據(jù)庫和文件系統(tǒng)的實(shí)現(xiàn)上，比如MySQL索引就用了B+樹。

其實(shí)，這些所謂的高級數(shù)據(jù)結(jié)構(gòu)往往是一些簡單的數(shù)據(jù)結(jié)構(gòu)衍生出來的，我們想要學(xué)習(xí)高級的數(shù)據(jù)結(jié)構(gòu)，就必須打好基本的數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中有對各種基本數(shù)據(jù)結(jié)構(gòu)的詳細(xì)講解，我們可以以此為根基，深入鉆研數(shù)據(jù)結(jié)構(gòu)這門學(xué)科。