數(shù)據(jù)結(jié)構(gòu)是什么？

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

是的，上面這句話是非常經(jīng)典的，程序由數(shù)據(jù)結(jié)構(gòu)以及算法組成，當(dāng)然數(shù)據(jù)結(jié)構(gòu)和算法也是相輔相成的，不能完全獨(dú)立來看待，但是本文會(huì)相對(duì)重點(diǎn)聊聊那些常用的數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)是什么呢？

首先得知道數(shù)據(jù)是什么？數(shù)據(jù)是對(duì)客觀事務(wù)的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)總稱。那為何加上“結(jié)構(gòu)”兩字？

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，而任何問題中，數(shù)據(jù)元素都不是獨(dú)立存在的，它們之間總是存在著某種關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系我們稱之為結(jié)構(gòu)。

因此，我們有了以下定義：

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

簡(jiǎn)單講，數(shù)據(jù)結(jié)構(gòu)就是組織，管理以及存儲(chǔ)數(shù)據(jù)的方式。雖然理論上所有的數(shù)據(jù)都可以混雜，或者混合，或者饑不擇食，隨便存儲(chǔ)，但是計(jì)算機(jī)是追求高效的，如果我們能了解數(shù)據(jù)結(jié)構(gòu)，找到較為適合當(dāng)前問題場(chǎng)景的數(shù)據(jù)結(jié)構(gòu)，將數(shù)據(jù)之間的關(guān)系表現(xiàn)在存儲(chǔ)上，計(jì)算的時(shí)候可以較為高效的利用適配的算法，那么程序的運(yùn)行效率肯定也會(huì)有所提高。

常用的4種數(shù)據(jù)結(jié)構(gòu)有：

• 集合：只有同屬于一個(gè)集合的關(guān)系，沒有其他關(guān)系
• 線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系
• 樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系
• 圖狀結(jié)構(gòu)或者網(wǎng)狀結(jié)構(gòu)：圖狀結(jié)構(gòu)或者網(wǎng)狀結(jié)構(gòu)

何為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)？

數(shù)據(jù)元素之間的邏輯關(guān)系，稱之為邏輯結(jié)構(gòu)，也就是我們定義了對(duì)操作對(duì)象的一種數(shù)學(xué)描述。但是我們還必須知道在計(jì)算機(jī)中如何表示它。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱為映像），稱之為數(shù)據(jù)的物理結(jié)構(gòu)，又稱存儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)元素之前的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序映像和非順序映像，并且由此得到兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，比如順序存儲(chǔ)結(jié)構(gòu)，我們要表示復(fù)數(shù)z1 =3.0 - 2.3i ,可以直接借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系：

而鏈?zhǔn)浇Y(jié)構(gòu)，則是以指針表示數(shù)據(jù)元素之間的邏輯關(guān)系，同樣是z1 =3.0 - 2.3i ，先找到下一個(gè)是 100，是一個(gè)地址，根據(jù)地址找到真實(shí)的數(shù)據(jù)-2.3i:

位（bit）

在計(jì)算機(jī)中表示信息的最小的單位是二進(jìn)制數(shù)中的一位，叫做位。也就是我們常見的類似01010101010這種數(shù)據(jù)，計(jì)算機(jī)的底層就是各種晶體管，電路板，所以不管是什么數(shù)據(jù)，即使是圖片，聲音，在最底層也是0和1,如果有八條電路，那么每條電路有自己的閉合狀態(tài)，有8個(gè)2相乘，28，也就是256種不同的信號(hào)。

但是一般我們需要表示負(fù)數(shù)，也就是最高的一位表示符號(hào)位，0表示正數(shù)，1表示負(fù)數(shù)，也就是8位的最大值是01111111，也就是127。

值得我們注意的是，計(jì)算機(jī)的世界里，多了原碼，反碼，補(bǔ)碼的概念：

• 源碼：用第一位表示符號(hào)，其余位表示值
• 反碼：正數(shù)的補(bǔ)碼反碼是其本身，負(fù)數(shù)的反碼是符號(hào)位保持不變，其余位取反。
• 補(bǔ)碼：正數(shù)的補(bǔ)碼是其本身，負(fù)數(shù)的補(bǔ)碼是在其反碼的基礎(chǔ)上 + 1

為什么有了原碼還要反碼和補(bǔ)碼？

我們知道加減法是高頻的運(yùn)算，人可以很直觀地看出加號(hào)減號(hào)，馬上就可以算出來，但是計(jì)算機(jī)如果區(qū)分不同的符號(hào)，那么加減就會(huì)比較復(fù)雜，比如正數(shù)+正數(shù)，正數(shù)-正數(shù)，正數(shù)-負(fù)數(shù)，負(fù)數(shù)+負(fù)數(shù)...等等。于是，有人就想用同一個(gè)運(yùn)算器（加號(hào)運(yùn)算器），解決所有的加減法計(jì)算，可以減少很多復(fù)雜的電路，以及各種符號(hào)轉(zhuǎn)換的開銷，計(jì)算也更加高效。

我們可以看到，下面負(fù)數(shù)參加運(yùn)算的結(jié)果也是符合補(bǔ)碼的規(guī)則的：

        00100011		35
 +      11011101	   -35
-------------------------
        00000000       0

        00100011		35
 + 	    11011011	   -37
-------------------------
        11111110       -2

當(dāng)然，如果計(jì)算結(jié)果超出了位數(shù)所能表示的范圍，那就是溢出，就說明需要更多的位數(shù)才能正確表示。

一般能用位運(yùn)算的，都盡量使用位運(yùn)算，因?yàn)樗容^高效, 常見地位置運(yùn)算：

• ~：按位取反
• &：按為與運(yùn)算
• |：按位或運(yùn)算
• ^：按位異或
• <<: 帶符號(hào)左移，比如35(00100011),左移一位為 70(01000110),-35(11011101)左移一位為-70(10111010)
• >>：帶符號(hào)右移，比如35(00100011),右移一位為 17(00010001),-35(11011101)左移一位為-18(11101110)
• <<<:無(wú)符號(hào)左移，比如35(00100011),左移一位為70(01000110)
• >>>:無(wú)符號(hào)右移，比如-35(11011101),右移一位為110(01101110)
• x ^= y; y ^= x; x ^= y;:交換
• s &= ~(1 << k):第k位置0

要說哪里使用位運(yùn)算比較經(jīng)典，那么要數(shù)布隆過濾器，需要了解詳情的可以參考：http://aphysia.cn/archives/cachebloomfilter

布隆過濾器是什么呢？

布隆過濾器（Bloom Filter）是由布?。?span>Burton Howard Bloom）在1970年提出的，它實(shí)際上是由一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)hash映射函數(shù)組成（說白了，就是用二進(jìn)制數(shù)組存儲(chǔ)數(shù)據(jù)的特征）?？梢允褂盟鼇砼袛嘁粋€(gè)元素是否存在于集合中，它的優(yōu)點(diǎn)在于查詢效率高，空間小，缺點(diǎn)是存在一定的誤差，以及我們想要剔除元素的時(shí)候，可能會(huì)相互影響。

也就是當(dāng)一個(gè)元素被加入集合的時(shí)候，通過多個(gè)hash函數(shù)，將元素映射到位數(shù)組中的k個(gè)點(diǎn)，置為1。

重點(diǎn)是多個(gè)hash函數(shù)，可以將數(shù)據(jù)hash到不同地位上，也只有這些位全部為1的時(shí)候，我們才能判斷該數(shù)據(jù)已經(jīng)存在

假設(shè)有三個(gè)hash函數(shù)，那么不同的元素，都會(huì)使用三個(gè)hash函數(shù)，hash到三個(gè)位置上。

假設(shè)后面又來了一個(gè)張三，那么在hash的時(shí)候，同樣會(huì)hash到以下位置，所有位都是1，我們就可以說張三已經(jīng)存在在里面了。

那么有沒有可能出現(xiàn)誤判的情況呢？這是有可能的，比如現(xiàn)在只有張三，李四，王五，蔡八，hash映射值如下：

后面來了陳六，但是不湊巧的是，它hash的三個(gè)函數(shù)hash出來的位，剛剛好就是被別的元素hash之后，改成1了，判斷它已經(jīng)存在了，但是實(shí)際上，陳六之前是不存在的。

上面的情況，就是誤判，布隆過濾器都會(huì)不可避免地出現(xiàn)誤判。但是它有一個(gè)好處是，布隆過濾器，判斷存在的元素，可能不存在，但是判斷不存在的元素，一定不存在。，因?yàn)榕袛嗖淮嬖谡f明至少有一位hash出來是對(duì)不上的。

也是由于會(huì)出現(xiàn)多個(gè)元素可能hash到一起，但有一個(gè)數(shù)據(jù)被踢出了集合，我們想把它映射地位，置為0，相當(dāng)于刪除該數(shù)據(jù)。這個(gè)時(shí)候，就會(huì)影響到其他的元素，可能會(huì)把別的元素映射地位置，置為了0。這也就是為什么布隆過濾器不能刪除的原因。

數(shù)組

線性表示最常用而且最為簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，一個(gè)線性表示 n 數(shù)據(jù)元素的有限序列，有以下特點(diǎn)：

• 存在唯一的第一個(gè)數(shù)據(jù)元素
• 存在唯一被稱為最后一個(gè)的數(shù)據(jù)元素
• 除了第一個(gè)以外，集合中每一個(gè)元素均有一個(gè)前驅(qū)
• 除了最后一個(gè)元素之外，集合中的每一個(gè)數(shù)據(jù)元素都有一個(gè)后繼元素

線性表包括下面幾種：

• 數(shù)組：查詢 / 更新快，查找/刪除慢
• 鏈表
• 隊(duì)列
• 棧

數(shù)組是線性表的一種，線性表的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素：

在Java中表示為：

int[] nums = new int[100];
int[] nums = {1,2,3,4,5};

Object[] Objects = new Object[100];

在C++ 中表示為：

int nums[100];

數(shù)組是一種線性的結(jié)構(gòu)，一般在底層是連續(xù)的空間，存儲(chǔ)相同類型的數(shù)據(jù)，由于連續(xù)緊湊結(jié)構(gòu)以及天然索引支持，查詢數(shù)據(jù)效率高:

假設(shè)我們知道數(shù)組a的第 1 個(gè)值是 地址是 296,里面的數(shù)據(jù)類型占 2 個(gè) 單位，那么我們?nèi)绻谕玫降?5 個(gè)： 296+（5-1）*2 = 304,O(1)的時(shí)間復(fù)雜度就可以獲取到。

更新的本質(zhì)也是查找，先查找到該元素，就可以動(dòng)手更新了：

但是如果期望插入數(shù)據(jù)的話，需要移動(dòng)后面的數(shù)據(jù)，比如下面的數(shù)組，插入元素6，最差的是移動(dòng)所有的元素，時(shí)間復(fù)雜度為O(n)

而刪除元素則需要把后面的數(shù)據(jù)移動(dòng)到前面，最差的時(shí)間復(fù)雜度同樣為O(n):

Java代碼實(shí)現(xiàn)數(shù)組的增刪改查：

package datastruction;

import java.util.Arrays;

public class MyArray {
    private int[] data;

    private int elementCount;

    private int length;

    public MyArray(int max) {
        length = max;
        data = new int[max];
        elementCount = 0;
    }

    public void add(int value) {
        if (elementCount == length) {
            length = 2 * length;
            data = Arrays.copyOf(data, length);
        }
        data[elementCount] = value;
        elementCount++;
    }

    public int find(int searchKey) {
        int i;
        for (i = 0; i < elementCount; i++) {
            if (data[i] == searchKey)
                break;
        }
        if (i == elementCount) {
            return -1;
        }
        return i;
    }

    public boolean delete(int value) {
        int i = find(value);
        if (i == -1) {
            return false;
        }
        for (int j = i; j < elementCount - 1; j++) {
            data[j] = data[j + 1];
        }
        elementCount--;
        return true;
    }

    public boolean update(int oldValue, int newValue) {
        int i = find(oldValue);
        if (i == -1) {
            return false;
        }
        data[i] = newValue;
        return true;
    }
}

// 測(cè)試類
public class Test {
    public static void main(String[] args) {
        MyArray myArray = new MyArray(2);
        myArray.add(1);
        myArray.add(2);
        myArray.add(3);
        myArray.delete(2);
        System.out.println(myArray);
    }
}

鏈表

上面的例子中，我們可以看到數(shù)組是需要連續(xù)的空間，這里面如果空間大小只有 2，放到第 3 個(gè)元素的時(shí)候，就不得不擴(kuò)容，不僅如此，還得拷貝元素。一些刪除，插入操作會(huì)引起較多的數(shù)據(jù)移動(dòng)的操作。

鏈表，也就是鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，由于它不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰，所以它沒有順序存儲(chǔ)結(jié)構(gòu)所具有的缺點(diǎn)，但是同時(shí)也失去了通過索引下標(biāo)直接查找元素的優(yōu)點(diǎn)。

重點(diǎn)：鏈表在計(jì)算機(jī)的存儲(chǔ)中不是連續(xù)的，而是前一個(gè)節(jié)點(diǎn)存儲(chǔ)了后一個(gè)節(jié)點(diǎn)的指針（地址），通過地址找到后一個(gè)節(jié)點(diǎn)。

下面是單鏈表的結(jié)構(gòu)：

一般我們會(huì)手動(dòng)在單鏈表的前面設(shè)置一個(gè)前置結(jié)點(diǎn)，也可以稱為頭結(jié)點(diǎn)，但是這并非絕對(duì)：

一般鏈表結(jié)構(gòu)分為以下幾種：

• 單向鏈表：鏈表中的每一個(gè)結(jié)點(diǎn)，都有且只有一個(gè)指針指向下一個(gè)結(jié)點(diǎn)，并且最后一個(gè)節(jié)點(diǎn)指向空。
• 雙向鏈表：每個(gè)節(jié)點(diǎn)都有兩個(gè)指針（為方便，我們稱之為前指針，后指針），分別指向上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)，第一個(gè)節(jié)點(diǎn)的前指針指向NULL，最后一個(gè)節(jié)點(diǎn)的后指針指向NULL
• 循環(huán)鏈表：每一個(gè)節(jié)點(diǎn)的指針指向下一個(gè)節(jié)點(diǎn)，并且最后一個(gè)節(jié)點(diǎn)的指針指向第一個(gè)節(jié)點(diǎn)（雖然是循環(huán)鏈表，但是必要的時(shí)候還需要標(biāo)識(shí)頭結(jié)點(diǎn)或者尾節(jié)點(diǎn)，避免死循環(huán)）
• 復(fù)雜鏈表：每一個(gè)鏈表有一個(gè)后指針，指向下一個(gè)節(jié)點(diǎn)，同時(shí)有一個(gè)隨機(jī)指針，指向任意一個(gè)結(jié)點(diǎn)。

鏈表操作的時(shí)間復(fù)雜度：

• 查詢：O(n),需要遍歷鏈表
• 插入：O(1)，修改前后指針即可
• 刪除：O(1)，同樣是修改前后指針即可
• 修改：不需要查詢則為O(1)，需要查詢則為O(n)

鏈表的結(jié)構(gòu)代碼怎么表示呢？

下面只表示單鏈表結(jié)構(gòu)，C++表示：

// 結(jié)點(diǎn)
typedef struct LNode{
  // 數(shù)據(jù)
  ElemType data;
  // 下一個(gè)節(jié)點(diǎn)的指針
  struct LNode *next;
}*Link,*Position;

// 鏈表
typedef struct{
  // 頭結(jié)點(diǎn)，尾節(jié)點(diǎn)
  Link head,tail;
  // 長(zhǎng)度
  int len;
}LinkList;

Java 代碼表示：

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

自己實(shí)現(xiàn)簡(jiǎn)單鏈表，實(shí)現(xiàn)增刪改查功能：

class ListNode<T> {
    T val;
    ListNode next = null;

    ListNode(T val) {
        this.val = val;
    }
}

public class MyList<T> {
    private ListNode<T> head;
    private ListNode<T> tail;
    private int size;

    public MyList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void add(T element) {
        add(size, element);
    }

    public void add(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出鏈表長(zhǎng)度范圍");
        }
        ListNode current = new ListNode(element);
        if (index == 0) {
            if (head == null) {
                head = current;
                tail = current;
            } else {
                current.next = head;
                head = current;
            }
        } else if (index == size) {
            tail.next = current;
            tail = current;
        } else {
            ListNode preNode = get(index - 1);
            current.next = preNode.next;
            preNode.next = current;
        }
        size++;
    }

    public ListNode get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出鏈表長(zhǎng)度");
        }
        ListNode temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    public ListNode delete(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出鏈表節(jié)點(diǎn)范圍");
        }
        ListNode node = null;
        if (index == 0) {
            node = head;
            head = head.next;
        } else if (index == size - 1) {
            ListNode preNode = get(index - 1);
            node = tail;
            preNode.next = null;
            tail = preNode;
        } else {
            ListNode pre = get(index - 1);
            pre.next = pre.next.next;
            node = pre.next;
        }
        size--;
        return node;
    }

    public void update(int index, T element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出鏈表節(jié)點(diǎn)范圍");
        }
        ListNode node = get(index);
        node.val = element;
    }

    public void display() {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " -> ");
            temp = temp.next;
        }
        System.out.println("");
    }
}

測(cè)試代碼如下：

public class Test {
    public static void main(String[] args) {
        MyList myList = new MyList();
        myList.add(1);
        myList.add(2);
        // 1->2
        myList.display();

        // 1
        System.out.println(myList.get(0).val);

        myList.update(1,3);
        // 1->3
        myList.display();

        myList.add(4);
        // 1->3->4
        myList.display();

        myList.delete(1);
        // 1->4
        myList.display();
    }
}

輸出結(jié)果：

1 -> 2 -> 
1
1 -> 3 -> 
1 -> 3 -> 4 -> 
1 -> 4 ->

單向鏈表的查找更新比較簡(jiǎn)單，我們看看插入新節(jié)點(diǎn)的具體過程（這里只展示中間位置的插入，頭尾插入比較簡(jiǎn)單）：

那如何刪除一個(gè)中間的節(jié)點(diǎn)呢？下面是具體的過程：

或許你會(huì)好奇，a5節(jié)點(diǎn)只是指針沒有了，那它去哪里了？

如果是Java程序，垃圾回收器會(huì)收集這種沒有被引用的節(jié)點(diǎn)，幫我們回收掉了這部分內(nèi)存，但是為了加快垃圾回收的速度，一般不需要的節(jié)點(diǎn)我們需要置空，比如 node = null, 如果在C++ 程序中，那么就需要手動(dòng)回收了，否則容易造成內(nèi)存泄漏等問題。

復(fù)雜鏈表的操作暫時(shí)講到這里，后面我會(huì)單獨(dú)把鏈表這一塊的數(shù)據(jù)結(jié)構(gòu)以及常用算法單獨(dú)分享一下，本文章主要講數(shù)據(jù)結(jié)構(gòu)全貌。

跳表

上面我們可以觀察到，鏈表如果搜索，是很麻煩的，如果這個(gè)節(jié)點(diǎn)在最后，需要遍歷所有的節(jié)點(diǎn)，才能找到，查找效率實(shí)在太低，有沒有什么好的辦法呢？

辦法總比問題多，但是想要絕對(duì)的”多快好省“是不存在的，有舍有得，計(jì)算機(jī)的世界里，充滿哲學(xué)的味道。既然搜索效率有問題，那么我們不如給鏈表排個(gè)序。排序后的鏈表，還是只能知道頭尾節(jié)點(diǎn)，知道中間的范圍，但是要找到中間的節(jié)點(diǎn)，還是得走遍歷的老路。如果我們把中間節(jié)點(diǎn)存儲(chǔ)起來呢？存起來，確實(shí)我們就知道數(shù)據(jù)在前一半，還是在后一半。比如找7，肯定就從中間節(jié)點(diǎn)開始找。如果查找4,就得從頭開始找，最差到中間節(jié)點(diǎn)，就停止查找。

但是如此，還是沒有徹底解決問題，因?yàn)殒湵砗荛L(zhǎng)的情況，只能通過前后兩部分查找。不如回到原則：空間和時(shí)間，我們選擇時(shí)間，那就要舍棄一部分空間,我們每個(gè)節(jié)點(diǎn)再加一個(gè)指針，現(xiàn)在有 2 層指針（注意：節(jié)點(diǎn)只有一份，都是同一個(gè)節(jié)點(diǎn)，只是為了好看，弄了兩份，實(shí)際上是同一個(gè)節(jié)點(diǎn)，有兩個(gè)指針，比如 1 ，既指向2，也指向5）：

兩層指針，問題依然存在，那就不斷加層，比如每?jī)蓚€(gè)節(jié)點(diǎn)，就加一層：

這就是跳表了，跳表的定義如下：

跳表(SkipList，全稱跳躍表)是用于有序元素序列快速搜索查找的一個(gè)數(shù)據(jù)結(jié)構(gòu)，跳表是一個(gè)隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，實(shí)質(zhì)就是一種可以進(jìn)行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級(jí)索引，通過索引來實(shí)現(xiàn)快速查找。跳表不僅能提高搜索性能，同時(shí)也可以提高插入和刪除操作的性能。它在性能上和紅黑樹，AVL樹不相上下，但是跳表的原理非常簡(jiǎn)單，實(shí)現(xiàn)也比紅黑樹簡(jiǎn)單很多。

主要的原理是用空間換時(shí)間，可以實(shí)現(xiàn)近乎二分查找的效率，實(shí)際上消耗的空間，假設(shè)每?jī)蓚€(gè)加一層， 1 + 2 + 4 + ... + n = 2n-1,多出了差不多一倍的空間。你看它像不像書的目錄，一級(jí)目錄，二級(jí)，三級(jí) ...

如果我們不斷往跳表中插入數(shù)據(jù)，可能出現(xiàn)某一段節(jié)點(diǎn)會(huì)特別多的情況，這個(gè)時(shí)候就需要?jiǎng)討B(tài)更新索引，除了插入數(shù)據(jù)，還要插入到上一層的鏈表中，保證查詢效率。

redis 中使用了跳表來實(shí)現(xiàn)zset,redis中使用一個(gè)隨機(jī)算法來計(jì)算層級(jí)，計(jì)算出每個(gè)節(jié)點(diǎn)到底多少層索引，雖然不能絕對(duì)保證比較平衡，但是基本保證了效率，實(shí)現(xiàn)起來比那些平衡樹，紅黑樹的算法簡(jiǎn)單一點(diǎn)。

棧

棧是一種數(shù)據(jù)結(jié)構(gòu)，在Java里面體現(xiàn)是Stack類。它的本質(zhì)是先進(jìn)后出，就像是一個(gè)桶，只能不斷的放在上面，取出來的時(shí)候，也只能不斷的取出最上面的數(shù)據(jù)。要想取出底層的數(shù)據(jù)，只有等到上面的數(shù)據(jù)都取出來，才能做到。當(dāng)然，如果有這種需求，我們一般會(huì)使用雙向隊(duì)列。

以下是棧的特性演示：

棧的底層用什么實(shí)現(xiàn)的？其實(shí)可以用鏈表，也可以用數(shù)組，但是JDK底層的棧，是用數(shù)組實(shí)現(xiàn)的，封裝之后，通過API操作的永遠(yuǎn)都只能是最后一個(gè)元素，棧經(jīng)常用來實(shí)現(xiàn)遞歸的功能。如果想要了解Java里面的?；蛘咂渌蠈?shí)現(xiàn)分析，可以看看這系列文章：http://aphysia.cn/categories/collection

元素加入稱之為入棧（壓棧），取出元素，稱之為出棧，棧頂元素則是最后一次放進(jìn)去的元素。

使用數(shù)組實(shí)現(xiàn)簡(jiǎn)單的棧(注意僅供參考測(cè)試，實(shí)際會(huì)有線程安全等問題)：

import java.util.Arrays;

public class MyStack<T> {
    private T[] data;
    private int length = 2;
    private int maxIndex;

    public MyStack() {
        data = (T[]) new Object[length];
        maxIndex = -1;
    }

    public void push(T element) {
        if (isFull()) {
            length = 2 * length;
            data = Arrays.copyOf(data, length);
        }
        data[maxIndex + 1] = element;
        maxIndex++;
    }

    public T pop() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException("棧內(nèi)沒有數(shù)據(jù)");
        } else {
            T[] newdata = (T[]) new Object[data.length - 1];
            for (int i = 0; i < data.length - 1; i++) {
                newdata[i] = data[i];
            }
            T element = data[maxIndex];
            maxIndex--;
            data = newdata;
            return element;
        }
    }

    private boolean isFull() {
        return data.length - 1 == maxIndex;
    }

    public boolean isEmpty() {
        return maxIndex == -1;
    }

    public void display() {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+" ");
        }
        System.out.println("");
    }
}

測(cè)試代碼：

public class MyStackTest {
    public static void main(String[] args) {
        MyStack<Integer> myStack = new MyStack<>();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.display();

        System.out.println(myStack.pop());

        myStack.display();

    }
}

輸出結(jié)果如下，符合預(yù)期：

1 2 3 4 
4
1 2 3 

棧的特點(diǎn)就是先進(jìn)先出，但是如果需要隨機(jī)取出前面的數(shù)據(jù)，效率會(huì)比較低，需要倒騰出來，但是如果底層使用數(shù)組，理論上是可以通過索引下標(biāo)取出的，Java里面正是這樣實(shí)現(xiàn)。

隊(duì)列

既然前面有先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，那我們必定也有先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，疫情的時(shí)候，排隊(duì)估計(jì)大家都有測(cè)過核酸，那排隊(duì)老長(zhǎng)了，排在前面先測(cè)，排在后面后測(cè)，這道理大家都懂。

隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。

隊(duì)列的特點(diǎn)是先進(jìn)先出，以下是例子：

一般只要說到先進(jìn)先出（FIFO）,全稱First In First Out,就會(huì)想到隊(duì)列，但是如果你想擁有隊(duì)列即可以從隊(duì)頭取出元素，又可以從隊(duì)尾取出元素，那就需要用到特殊的隊(duì)列（雙向隊(duì)列），雙向隊(duì)列一般使用雙向鏈表實(shí)現(xiàn)會(huì)簡(jiǎn)單一點(diǎn)。

下面我們用Java實(shí)現(xiàn)簡(jiǎn)單的單向隊(duì)列：

class Node<T> {
    public T data;
    public Node next;

    public Node(T data) {
        this.data = data;
    }
}

public class MyQueue<T> {
    private Node<T>  head;
    private Node<T>  rear;
    private int size;

    public MyQueue() {
        size = 0;
    }

    public void pushBack(T element) {
        Node newNode = new Node(element);
        if (isEmpty()) {
            head = newNode;
        } else {
            rear.next = newNode;
        }
        rear = newNode;
        size++;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public T popFront() {
        if (isEmpty()) {
            throw new NullPointerException("隊(duì)列沒有數(shù)據(jù)");
        } else {
            Node<T> node = head;
            head = head.next;
            size--;
            return node.data;
        }
    }

    public void dispaly() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data +" -> ");
            temp = temp.next;
        }
        System.out.println("");
    }
}

測(cè)試代碼如下：

public class MyStackTest {
    public static void main(String[] args) {
        MyStack<Integer> myStack = new MyStack<>();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.display();

        System.out.println(myStack.pop());

        myStack.display();

    }
}

運(yùn)行結(jié)果：

1 -> 2 -> 3 -> 
1
2 -> 3 -> 
2
3 -> 

常用的隊(duì)列類型如下：

• 單向隊(duì)列：也就是我們說的普通隊(duì)列，先進(jìn)先出。
• 雙向隊(duì)列：可以從不同方向進(jìn)出隊(duì)列
• 優(yōu)先隊(duì)列：內(nèi)部是自動(dòng)排序的，按照一定順序出隊(duì)列
• 阻塞隊(duì)列：從隊(duì)列取出元素的時(shí)候，隊(duì)列沒有元素則會(huì)阻塞，同樣如果隊(duì)列滿了，往隊(duì)列里面放入元素也會(huì)被阻塞。
• 循環(huán)隊(duì)列：可以理解為一個(gè)循環(huán)鏈表，但是一般需要標(biāo)識(shí)出頭尾節(jié)點(diǎn)，防止死循環(huán)，尾節(jié)點(diǎn)的next指向頭結(jié)點(diǎn)。

隊(duì)列一般可以用來保存需要順序的數(shù)據(jù)，或者保存任務(wù)，在樹的層次遍歷中可以使用隊(duì)列解決，一般廣度優(yōu)先搜索都可以使用隊(duì)列解決。

哈希表

前面的數(shù)據(jù)結(jié)構(gòu)，查找的時(shí)候，一般都是使用=或者!=,在折半查找或者其他范圍查詢的時(shí)候，可能會(huì)使用<和>,理想的時(shí)候，我們肯定希望不經(jīng)過任何的比較，直接能定位到某個(gè)位置（存儲(chǔ)位置），這種在數(shù)組中，可以通過索引取得元素。那么，如果我們將需要存儲(chǔ)的數(shù)據(jù)和數(shù)組的索引對(duì)應(yīng)起來，并且是一對(duì)一的關(guān)系，那不就可以很快定位到元素的位置了么？

只要通過函數(shù)f(k)就能找到k對(duì)應(yīng)的位置，這個(gè)函數(shù)f(k)就是hash函數(shù)。它表示的是一種映射關(guān)系，但是對(duì)不同的值，可能會(huì)映射到同一個(gè)值（同一個(gè)hash地址），也就是f(k1) = f(k2)，這種現(xiàn)象我們稱之為沖突或者碰撞。

hash表定義如下：

散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存儲(chǔ)存位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來訪問記錄，這加快了查找速度。這個(gè)映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

一般常用的hash 函數(shù)有：

• 直接定址法：取出關(guān)鍵字或者關(guān)鍵字的某個(gè)線性函數(shù)的值為哈希函數(shù)，比如H(key) = key或者H(key) = a * key + b
• 數(shù)字分析法：對(duì)于可能出現(xiàn)的數(shù)值全部了解，取關(guān)鍵字的若干數(shù)位組成哈希地址
• 平方取中法：取關(guān)鍵字平方后的中間幾位作為哈希地址
• 折疊法：將關(guān)鍵字分割成為位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），取這幾部分的疊加和（舍去進(jìn)位），作為哈希地址。
• 除留余數(shù)法：取關(guān)鍵字被某個(gè)不大于散列表表長(zhǎng)m的數(shù)p除后所得的余數(shù)為散列地址。即hash(k)=k mod p，p< =m。不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊法、平方取中法等運(yùn)算之后取模。對(duì)p的選擇很重要，一般取素?cái)?shù)或m，若p選擇不好，容易產(chǎn)生沖突。
• 隨機(jī)數(shù)法：取關(guān)鍵字的隨機(jī)函數(shù)值作為它的哈希地址。

但是這些方法，都無(wú)法避免哈希沖突，只能有意識(shí)的減少。那處理hash沖突，一般有哪些方法呢？

• 開放地址法：hash計(jì)算后，如果該位置已經(jīng)有數(shù)據(jù)，那么對(duì)該地址+1，也就是往后找，知道找到一個(gè)空的位置。
• 重新hash法：發(fā)生哈希沖突后，可以使用另外的hash函數(shù)重新極計(jì)算，找到空的hash地址,如果有，還可以再疊加hash函數(shù)。
• 鏈地址法：所有hash值一樣的,鏈接成為一個(gè)鏈表，掛在數(shù)組后面。
• 建立公共溢出區(qū)：不常見，意思是所有元素，如果和表中的元素hash沖突，都弄到另外一個(gè)表，也叫溢出表。

Java里面，用的就是鏈地址法：

但是如果hash沖突比較嚴(yán)重，鏈表會(huì)比較長(zhǎng)，查詢的時(shí)候，需要遍歷后面的鏈表，因此JDK優(yōu)化了一版，鏈表的長(zhǎng)度超過閾值的時(shí)候，會(huì)變成紅黑樹，紅黑樹有一定的規(guī)則去平衡子樹，避免退化成為鏈表，影響查詢效率。

但是你肯定會(huì)想到，如果數(shù)組太小了，放了比較多數(shù)據(jù)了，怎么辦？再放沖突的概率會(huì)越來越高，其實(shí)這個(gè)時(shí)候會(huì)觸發(fā)一個(gè)擴(kuò)容機(jī)制，將數(shù)組擴(kuò)容成為 2倍大小，重新hash以前的數(shù)據(jù)，哈希到不同的數(shù)組中。

hash表的優(yōu)點(diǎn)是查找速度快，但是如果不斷觸發(fā)重新 hash, 響應(yīng)速度也會(huì)變慢。同時(shí)，如果希望范圍查詢，hash表不是好的選擇。

樹

數(shù)組和鏈表都是線性結(jié)構(gòu)，而這里要介紹的樹，則是非線性結(jié)構(gòu)?，F(xiàn)實(shí)中樹是金字塔結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)中的樹，最上面稱之為根節(jié)點(diǎn)。

我們?cè)撊绾味x樹結(jié)構(gòu)呢？

樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n(n≥1)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：

每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹。(百度百科)

下面是樹的基本術(shù)語(yǔ)（來自于清華大學(xué)數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版）：

• 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度
• 樹的度：一棵樹中，最大的節(jié)點(diǎn)度稱為樹的度；
• 葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為零的節(jié)點(diǎn)；
• 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為零的節(jié)點(diǎn)；
• 父親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；
• 孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；
• 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；
• 節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
• 深度：對(duì)于任意節(jié)點(diǎn)n,n的深度為從根到n的唯一路徑長(zhǎng)，根的深度為0；
• 高度：對(duì)于任意節(jié)點(diǎn)n,n的高度為從n到一片樹葉的最長(zhǎng)路徑長(zhǎng)，所有樹葉的高度為0；
• 堂兄弟節(jié)點(diǎn)：父節(jié)點(diǎn)在同一層的節(jié)點(diǎn)互為堂兄弟；
• 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；
• 子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。
• 有序樹：將樹種的節(jié)點(diǎn)的各個(gè)子樹看成從左至右是有次序的（不能互換），則應(yīng)該稱該樹為有序樹，否則為無(wú)序樹
• 第一個(gè)孩子：在有序樹中最左邊的子樹的根稱為第一個(gè)孩子
• 最后一個(gè)孩子：在有序樹種最右邊的子樹的根稱為最后一個(gè)孩子
• 森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

樹，其實(shí)我們最常用的是二叉樹：

二叉樹的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子樹，并且子樹有左右之分，左右子節(jié)點(diǎn)的次序不能任意顛倒。

二叉樹在Java中表示：

public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}

滿二叉樹：一棵深度為 k 且有 2k-1 個(gè)節(jié)點(diǎn)的二叉樹，稱之為滿二叉樹

完全二叉樹：深度為 k 的，有 n 個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為 k 的滿二叉樹中編號(hào)從 1 到 n 的節(jié)點(diǎn)一一對(duì)應(yīng)是，稱之為完全二叉樹。

一般二叉樹的遍歷有幾種：

• 前序遍歷：遍歷順序 根節(jié)點(diǎn) --> 左子節(jié)點(diǎn) --> 右子節(jié)點(diǎn)
• 中序遍歷：遍歷順序 左子節(jié)點(diǎn) --> 根節(jié)點(diǎn) --> 右子節(jié)點(diǎn)
• 后序遍歷：遍歷順序 左子節(jié)點(diǎn) --> 右子節(jié)點(diǎn) --> 根節(jié)點(diǎn)
• 廣度 / 層次遍歷： 從上往下，一層一層的遍歷

如果是一棵混亂的二叉樹，那查找或者搜索的效率也會(huì)比較低，和一條混亂的鏈表沒有什么區(qū)別，何必弄更加復(fù)雜的結(jié)構(gòu)呢？

其實(shí)，二叉樹是可以用在排序或者搜索中的，因?yàn)槎鏄溆袊?yán)格的左右子樹之分，我們可以定義根節(jié)點(diǎn)，左子節(jié)點(diǎn)，右子節(jié)點(diǎn)的大小之分。于是有了二叉搜索樹：

二叉查找樹（Binary Search Tree），（又：二叉搜索樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹也分別為二叉排序樹。二叉搜索樹作為一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它既有鏈表的快速插入與刪除操作的特點(diǎn)，又有數(shù)組快速查找的優(yōu)勢(shì)；所以應(yīng)用十分廣泛，例如在文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)一般會(huì)采用這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行高效率的排序與檢索操作。

二叉查找樹樣例如下：

比如上面的樹，如果我們需要查找到 4， 從 5開始，4比5小，往左子樹走，查找到3，4比3大，往右子樹走，找到了4，也就是一個(gè) 7個(gè)節(jié)點(diǎn)的樹，我們只查找了3次，也就是層數(shù)，假設(shè)n個(gè)節(jié)點(diǎn)，那就是log(n+1)。

樹維護(hù)好了，查詢效率固然高，但是如果樹沒維護(hù)好，容易退化成為鏈表，查詢效率也會(huì)下降，比如：

一棵對(duì)查詢友好的二叉樹，應(yīng)該是一個(gè)平衡或者接近平衡的二叉樹，何為平衡二叉樹：

平衡二叉搜索樹的任何結(jié)點(diǎn)的左子樹和右子樹高度最多相差1。平衡二叉樹也稱為 AVL 樹。

為了保證插入或者刪除數(shù)據(jù)等之后，二叉樹還是平衡二叉樹，那么就需要調(diào)整節(jié)點(diǎn)，這個(gè)也稱為平衡過程，里面會(huì)涉及各種旋轉(zhuǎn)調(diào)整，這里暫時(shí)不展開。

但是如果涉及大量的更新，刪除操作，平衡樹種的各種調(diào)整需要犧牲不小的性能，為了解決這個(gè)問題，有大佬提出了紅黑樹.

紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。 [1]

紅黑樹是在1972年由[Rudolf Bayer](https://baike.baidu.com/item/Rudolf Bayer/3014716)發(fā)明的，當(dāng)時(shí)被稱為平衡二叉B樹（symmetric binary B-trees）。后來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的“紅黑樹”。 [2]

紅黑樹是一種特化的AVL樹（平衡二叉樹），都是在進(jìn)行插入和刪除操作時(shí)通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。

紅黑樹有以下的特點(diǎn)：

• 性質(zhì)1. 結(jié)點(diǎn)是紅色或黑色。
• 性質(zhì)2. 根結(jié)點(diǎn)是黑色。
• 性質(zhì)3. 所有葉子都是黑色。（葉子是NIL結(jié)點(diǎn)）
• 性質(zhì)4. 每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)都是黑色。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色結(jié)點(diǎn)）
• 性質(zhì)5. 從任一節(jié)結(jié)點(diǎn)其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點(diǎn)。

正是這些特性，讓紅黑樹在調(diào)整的時(shí)候，不像普通的平衡二叉樹調(diào)整那般困難，頻繁。也就是加上了條條框框，讓它符合一定的標(biāo)準(zhǔn)，減少平衡過程的混亂以及頻次。

前面說的哈希表，Java 中的實(shí)現(xiàn)，正是應(yīng)用了紅黑樹，在hash沖突較多的時(shí)候，會(huì)將鏈表轉(zhuǎn)換成為紅黑樹。

上面說的都是二叉樹，但是我們不得不扯一下多叉樹，為什么呢？雖然二叉樹中的各種搜索樹，紅黑樹已經(jīng)很優(yōu)秀了，但是在與磁盤交互的時(shí)候，大多數(shù)是數(shù)據(jù)存儲(chǔ)中，我們不得不考慮 IO 的因素，因?yàn)榇疟PIO比內(nèi)存慢太多了。如果索引樹的層高有幾千上萬(wàn)，那么磁盤讀取的時(shí)候，需要次數(shù)太多了。B樹更加適合磁盤存儲(chǔ)。

970年，R.Bayer和E.mccreight提出了一種適用于外查找的樹，它是一種平衡的多叉樹，稱為B樹（或B-樹、B_樹）。

一棵m階B樹(balanced tree of order m)是一棵平衡的m路搜索樹。它或者是空樹，或者是滿足下列性質(zhì)的樹：

1、根結(jié)點(diǎn)至少有兩個(gè)子女；

2、每個(gè)非根節(jié)點(diǎn)所包含的關(guān)鍵字個(gè)數(shù) j 滿足：m/2 - 1 <= j <= m - 1；

3、除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn)（不包括葉子結(jié)點(diǎn)）的度數(shù)正好是關(guān)鍵字總數(shù)加1，故內(nèi)部子樹個(gè)數(shù) k 滿足：m/2 <= k <= m ；

4、所有的葉子結(jié)點(diǎn)都位于同一層。

每個(gè)節(jié)點(diǎn)放多一點(diǎn)數(shù)據(jù)，查找的時(shí)候，內(nèi)存中的操作比磁盤快很多，b樹可以減少磁盤IO的次數(shù)。B 樹：

而每個(gè)節(jié)點(diǎn)的data可能很大,這樣會(huì)導(dǎo)致每一頁(yè)查出來的數(shù)據(jù)很少，IO查詢次數(shù)自然就增加了，那我們不如只在葉子節(jié)點(diǎn)中存儲(chǔ)數(shù)據(jù)：

B+樹是B樹的一種變形形式，B+樹上的葉子結(jié)點(diǎn)存儲(chǔ)關(guān)鍵字以及相應(yīng)記錄的地址，葉子結(jié)點(diǎn)以上各層作為索引使用。一棵m階的B+樹定義如下:

(1)每個(gè)結(jié)點(diǎn)至多有m個(gè)子女；

(2)除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)至少有[m/2]個(gè)子女，根結(jié)點(diǎn)至少有兩個(gè)子女；

(3)有k個(gè)子女的結(jié)點(diǎn)必有k個(gè)關(guān)鍵字。

一般b+樹的葉子節(jié)點(diǎn)，會(huì)用鏈表連接起來，方便遍歷以及范圍遍歷。

這就是b+樹，b+樹相對(duì)于B樹多了以下優(yōu)勢(shì)：

1. b+樹的中間節(jié)點(diǎn)不保存數(shù)據(jù)，每次IO查詢能查到更多的索引，,是一個(gè)矮胖的樹。
2. 對(duì)于范圍查找來說，b+樹只需遍歷葉子節(jié)點(diǎn)鏈表即可，b樹卻需要從根節(jié)點(diǎn)都葉子節(jié)點(diǎn)。

除了上面的樹，其實(shí)還有一種叫Huffman樹：給定N個(gè)權(quán)值作為N個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近。

一般用來作為壓縮使用，因?yàn)閿?shù)據(jù)中，每個(gè)字符出現(xiàn)的頻率不一樣，出現(xiàn)頻率越高的字符，我們用越短的編碼保存，就可以達(dá)到壓縮的目的。那這個(gè)編碼怎么來的呢？

假設(shè)字符是hello,那么編碼可能是（只是編碼的大致雛形，高頻率出現(xiàn)的字符，編碼更短），編碼就是從根節(jié)點(diǎn)到當(dāng)前字符的路徑的01串：

通過不同權(quán)值的編碼，哈夫曼樹到了有效的壓縮。

堆

堆，其實(shí)也是二叉樹中的一種，堆必須是完全二叉樹，完全二叉樹是：除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都是滿的，最后一層的節(jié)點(diǎn)都集中在左部連續(xù)位置。

而堆還有一個(gè)要求：堆中每一個(gè)節(jié)點(diǎn)的值都必須大于等于（或小于等于）其左右子節(jié)點(diǎn)的值。

堆主要分為兩種：

• 大頂堆：每個(gè)節(jié)點(diǎn)都大于等于其子樹節(jié)點(diǎn)（堆頂是最大值）
• 小頂堆：每個(gè)節(jié)點(diǎn)都小于等于其子樹節(jié)點(diǎn)（堆頂是最小值）

一般情況下，我們都是用數(shù)組來表示堆，比如下面的小頂堆：

數(shù)組中父子節(jié)點(diǎn)以及左右節(jié)點(diǎn)的關(guān)系如下：

• i 結(jié)點(diǎn)的父結(jié)點(diǎn) parent = floor((i-1)/2) (向下取整)
• i 結(jié)點(diǎn)的左子結(jié)點(diǎn) 2 * i +1
• i 結(jié)點(diǎn)的右子結(jié)點(diǎn) 2 * i + 2

既然是存儲(chǔ)數(shù)據(jù)的，那么一定會(huì)涉及到插入刪除等操作，堆里面插入刪除，會(huì)涉及到堆的調(diào)整，調(diào)整之后才能重新滿足它的定義，這個(gè)調(diào)整的過程，叫做堆化。

用小頂堆舉例，調(diào)整主要是為了保證：

• 還是完全二叉樹
• 堆中每一個(gè)節(jié)點(diǎn)都還小于等于其左右子節(jié)點(diǎn)

對(duì)于小頂堆，調(diào)整的時(shí)候是：小元素往上浮，大元素往下沉，就是不斷交換的過程。

堆一般可以用來求解TOP K 問題，或者前面我們說的優(yōu)先隊(duì)列等。

圖

終于來到了圖的講解，圖其實(shí)就是二維平面，之前寫過掃雷，掃雷的整個(gè)方塊區(qū)域，其實(shí)也可以說是圖相關(guān)的。圖是非線性的數(shù)據(jù)結(jié)構(gòu)，主要是由邊和頂點(diǎn)組成。

同時(shí)圖又分為有向圖與無(wú)向圖，上面的是無(wú)向圖，因?yàn)檫厸]有指明方向，只是表示兩者關(guān)聯(lián)關(guān)系，而有向圖則是這樣：

如果每個(gè)頂點(diǎn)是一個(gè)地方，每條邊是路徑，那么這就是一張地圖網(wǎng)絡(luò)，因此圖也經(jīng)常被用于求解最短距離。先來看看圖相關(guān)的概念：

• 頂點(diǎn)：圖最基本的單元，那些節(jié)點(diǎn)
• 邊：頂點(diǎn)之間的關(guān)聯(lián)關(guān)系
• 相鄰頂點(diǎn)：由邊直接關(guān)聯(lián)的頂點(diǎn)
• 度：一個(gè)頂點(diǎn)直接連接的相鄰頂點(diǎn)的數(shù)量
• 權(quán)重：邊的權(quán)值

一般表示圖有以下幾種方法：

1. 鄰接矩陣，使用二維數(shù)組表示，為1 表示聯(lián)通，0表示不連通，當(dāng)然如果表示路徑長(zhǎng)度的時(shí)候，可以用大于0的數(shù)表示路徑長(zhǎng)度，用-1表示不連通。

下面的圖片中，0和 1，2連通，我們可以看到第 0行的第1，2列是1 ，表示連通。還有一點(diǎn)：頂點(diǎn)自身我們是標(biāo)識(shí)了0，表示不連通，但是有些情況可以視為連通狀態(tài)。

1. 鄰接表

鄰接表，存儲(chǔ)方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)結(jié)構(gòu)。如這個(gè)表頭結(jié)點(diǎn)所對(duì)應(yīng)的頂點(diǎn)存在相鄰頂點(diǎn)，則把相鄰頂點(diǎn)依次存放于表頭結(jié)點(diǎn)所指向的單向鏈表中。

對(duì)于無(wú)向圖來說，使用鄰接表進(jìn)行存儲(chǔ)也會(huì)出現(xiàn)數(shù)據(jù)冗余，表頭結(jié)點(diǎn)A所指鏈表中存在一個(gè)指向C的表結(jié)點(diǎn)的同時(shí)，表頭結(jié)點(diǎn)C所指鏈表也會(huì)存在一個(gè)指向A的表結(jié)點(diǎn)。

圖里面遍歷一般分為廣度優(yōu)先遍歷和深度優(yōu)先遍歷，廣度優(yōu)先遍歷是指優(yōu)先遍歷與當(dāng)前頂點(diǎn)直接相關(guān)的頂點(diǎn)，一般借助隊(duì)列實(shí)現(xiàn)。而深度優(yōu)先遍歷則是往一個(gè)方向一直走到不能再走，有點(diǎn)不撞南墻不回頭的意思，一般使用遞歸實(shí)現(xiàn)。

圖，除了用了計(jì)算最小路徑以外，還有一個(gè)概念：最小生成樹。

一個(gè)有 n 個(gè)結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊。 最小生成樹可以用kruskal（克魯斯卡爾）算法或prim（普里姆）算法求出。

有一種說法，圖是平面上的點(diǎn)，我們把其中一個(gè)點(diǎn)拎起來，能將其他頂點(diǎn)帶起來的邊，取最小權(quán)值，多余的邊去掉，就是最小生成樹。

當(dāng)然，最小生成樹并不一定是唯一的，可能存在多種結(jié)果。