紅黑樹(shù)(Red Black Tree)

1. 簡(jiǎn)介

紅黑樹(shù)（Red Black Tree）是一種自平衡二叉查找樹(shù)帆啃，是二叉查找樹(shù)的變種之一。它是在1972年由Rudolf Bayer發(fā)明的，當(dāng)時(shí)被稱為平衡二叉B樹(shù)（symmetric binary B-trees）撞反。后來(lái)，在1978年被 Leo J. Guibas 和 Robert Sedgewick修改為如今的“紅黑樹(shù)”搪花。 2008年 Robert Sedgewick 對(duì)其進(jìn)行了改進(jìn)遏片，并命名為 LLRBT(Left-leaning Red Black Tree 左傾紅黑樹(shù))。左傾紅黑樹(shù)相比1978年的紅黑樹(shù)要簡(jiǎn)單很多撮竿，實(shí)現(xiàn)的代碼量也少很多吮便。Robert Sedgewick也是Algorithms（中文版叫《算法》）這本書的作者，在這本書中就講了基于2-3樹(shù)的左傾紅黑樹(shù)幢踏。
現(xiàn)在的使用的工程代碼中的紅黑樹(shù)都是基于78年的算法髓需，比如JDK中的TreeMap。其實(shí)紅黑樹(shù)就是2-3-4樹(shù)的具體實(shí)現(xiàn)房蝉，所以要想理解紅黑樹(shù)就得先理解2-3-4樹(shù)僚匆。而08年左傾紅黑樹(shù)則是基于2-3樹(shù)。

2. 定義

紅黑樹(shù)是2-3-4樹(shù)的實(shí)現(xiàn)搭幻，所以在講紅黑樹(shù)之前想講下2-3-4樹(shù)有助于理解紅黑樹(shù)咧擂。
因?yàn)榧t黑樹(shù)是一棵自平衡二叉搜索樹(shù)，通過(guò)結(jié)點(diǎn)顏色改變和局部旋轉(zhuǎn)來(lái)維持平衡檀蹋，所以除了一些會(huì)改變樹(shù)結(jié)構(gòu)的操作之外松申，其他的操作都和普通的二叉搜索樹(shù)相同。因此這里就只講插入刪除操作俯逾。
因?yàn)槲乙眉t黑樹(shù)實(shí)現(xiàn)一個(gè)符號(hào)表贸桶，所以結(jié)點(diǎn)需要存儲(chǔ)鍵值對(duì)，而且實(shí)現(xiàn)的紅黑樹(shù)是基于2-3-4樹(shù)桌肴。

2-3-4樹(shù)的定義

2-3-4樹(shù)可以存在三種類型結(jié)點(diǎn)皇筛。
2-結(jié)點(diǎn)是一個(gè)結(jié)點(diǎn)有2條鏈接和1個(gè)鍵，其中兩條鏈接對(duì)應(yīng)于二叉搜索樹(shù)中的左右鏈接坠七。
3-結(jié)點(diǎn)是一個(gè)結(jié)點(diǎn)有3條鏈接和2個(gè)鍵水醋。
4-結(jié)點(diǎn)是一個(gè)結(jié)點(diǎn)有4條鏈接和3個(gè)鍵。

一棵2-3-4樹(shù)

紅黑樹(shù)的定義

每個(gè)結(jié)點(diǎn)都有顏色灼捂，不是黑色就是紅色离例。
根結(jié)點(diǎn)是黑色的。
如果一個(gè)空結(jié)點(diǎn)都是黑色的悉稠。
如果一個(gè)結(jié)點(diǎn)是紅色的宫蛆，則與它相連的結(jié)點(diǎn)都只能是黑色的，也就是不可以有兩個(gè)紅色結(jié)點(diǎn)相連。
每個(gè)空結(jié)點(diǎn)到根結(jié)點(diǎn)的簡(jiǎn)單路徑中所含的黑色結(jié)點(diǎn)數(shù)目相同耀盗。

一棵紅黑樹(shù)

通過(guò)觀察以上兩圖基本能看出兩者的關(guān)系了

第一張圖已經(jīng)存在三種結(jié)點(diǎn)了想虎，其中1和3都是2-結(jié)點(diǎn)，2和4構(gòu)成一個(gè)3-結(jié)點(diǎn)叛拷，5和6和7構(gòu)成一個(gè)4-結(jié)點(diǎn)舌厨。
第二張圖則是第一張圖中2-3-4樹(shù)在紅黑樹(shù)的表現(xiàn)形式。
現(xiàn)在我總結(jié)一下2-3-4樹(shù)中三種結(jié)點(diǎn)在紅黑樹(shù)中的表示：
2-結(jié)點(diǎn)

2-結(jié)點(diǎn)

3-結(jié)點(diǎn)

3-結(jié)點(diǎn)

4-結(jié)點(diǎn)

4-結(jié)點(diǎn)

3. 實(shí)現(xiàn)

實(shí)現(xiàn)部分的代碼用Java

結(jié)點(diǎn)的定義

每個(gè)結(jié)點(diǎn)的類型是Node忿薇，里面有5個(gè)字段裙椭。

private class Node {
        Key key;
        Value value;
        Node left;
        Node right;
        boolean color;

        public Node(Key key, Value value, Node left, Node right, boolean color) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.color = color;
        }
    }

紅黑樹(shù)的插入

當(dāng)我們想要在樹(shù)中插入一個(gè)新結(jié)點(diǎn)時(shí)，先在樹(shù)中搜索與插入結(jié)點(diǎn)鍵相同的結(jié)點(diǎn)署浩。

如果找到該結(jié)點(diǎn)則直接修改對(duì)應(yīng)的Value字段就完成了揉燃。
如果找不到該結(jié)點(diǎn)則創(chuàng)建一個(gè)新的結(jié)點(diǎn)并把這個(gè)新結(jié)點(diǎn)設(shè)置為紅色（因?yàn)椴迦胍粋€(gè)紅色結(jié)點(diǎn)不會(huì)改變紅黑樹(shù)的性質(zhì)5），隨后插到對(duì)應(yīng)樹(shù)底部對(duì)應(yīng)的結(jié)點(diǎn)下筋栋。然而插入樹(shù)底部對(duì)應(yīng)結(jié)點(diǎn)下炊汤，那這個(gè)對(duì)應(yīng)的結(jié)點(diǎn)有三種可能，分別是上面說(shuō)到的2-弊攘，3-抢腐，4-結(jié)點(diǎn)。
- 如果插到2-結(jié)點(diǎn)下襟交，由于2-結(jié)點(diǎn)是黑色結(jié)點(diǎn)則不會(huì)破壞紅黑樹(shù)的任何性質(zhì)迈倍，所以不用做任何操作就完成了。
- 如果插到3-結(jié)點(diǎn)下婿着，從上面3-結(jié)點(diǎn)的圖看授瘦，3-結(jié)點(diǎn)有三個(gè)位置可以插入醋界。
  - 如果插入黑色結(jié)點(diǎn)的位置下則變成4-結(jié)點(diǎn)也不用做任何操作就完成了竟宋。
  - 如果插到3-結(jié)點(diǎn)的紅色結(jié)點(diǎn)下，則破壞了紅黑樹(shù)的性質(zhì)4形纺。如下圖新插入的0003結(jié)點(diǎn)丘侠，因?yàn)椴迦胛恢迷谟疫叄瑒t需要對(duì)0001做一個(gè)左旋操作：
    
    左旋
  - 如果插入位置在左邊逐样，如下圖新插入的0002結(jié)點(diǎn)蜗字。則需要對(duì)插入結(jié)點(diǎn)的父節(jié)點(diǎn)做一個(gè)右旋操作，再對(duì)0001做一個(gè)左旋操作：
    
    先右旋再左旋
- 無(wú)論插到4-結(jié)點(diǎn)的哪個(gè)地方都會(huì)破壞性質(zhì)4脂新，這時(shí)只要將4-結(jié)點(diǎn)分解為兩個(gè)2-結(jié)點(diǎn)并將中間結(jié)點(diǎn)往上傳給父結(jié)點(diǎn)挪捕。如下圖新插入的0004結(jié)點(diǎn)：
  
  分解4-結(jié)點(diǎn)

紅黑樹(shù)的刪除

首先要?jiǎng)h除一個(gè)結(jié)點(diǎn)的話，這個(gè)結(jié)點(diǎn)有兩種可能的顏色：

刪除一個(gè)紅色結(jié)點(diǎn)不會(huì)破壞紅黑樹(shù)的任何性質(zhì)争便，可以像刪除普通二叉樹(shù)搜索樹(shù)結(jié)點(diǎn)一樣刪除
如果刪除的是一個(gè)黑色結(jié)點(diǎn)則會(huì)破壞紅黑樹(shù)的性質(zhì)5级零，所以我們只要保證刪除的結(jié)點(diǎn)是紅色的就不會(huì)破壞紅黑樹(shù)的性質(zhì)。具體步驟如下：
在自頂向下搜索要?jiǎng)h除結(jié)點(diǎn)過(guò)程中滞乙，保證當(dāng)前結(jié)點(diǎn)是紅色的奏纪。如果當(dāng)前結(jié)點(diǎn)不是要?jiǎng)h除的結(jié)點(diǎn)鉴嗤，在接著再往下搜索時(shí)判斷下一個(gè)結(jié)點(diǎn)的顏色，定義下一個(gè)結(jié)點(diǎn)為左結(jié)點(diǎn)序调，（下個(gè)結(jié)點(diǎn)為右結(jié)點(diǎn)的情況與左結(jié)點(diǎn)相反）：
- 如果下個(gè)結(jié)點(diǎn)是紅色或者為空醉锅，則不需要做任何操作
- 如果下個(gè)結(jié)點(diǎn)為黑色且下個(gè)結(jié)點(diǎn)的兄弟結(jié)點(diǎn)也是黑色的話，直接將當(dāng)前結(jié)點(diǎn)和兩個(gè)子結(jié)點(diǎn)合并為一個(gè)4-結(jié)點(diǎn)发绢。
- 如果下個(gè)結(jié)點(diǎn)為黑色而下個(gè)結(jié)點(diǎn)的兄弟結(jié)點(diǎn)是紅色的話硬耍，直接對(duì)當(dāng)前結(jié)點(diǎn)做一個(gè)左旋操作變成一個(gè)4-結(jié)點(diǎn)。
當(dāng)自頂向下刪除完結(jié)點(diǎn)后边酒，需要向上回溯消除所有破壞紅黑樹(shù)性質(zhì)4的情況默垄，這一步通過(guò)平衡操作來(lái)實(shí)現(xiàn)。

代碼實(shí)現(xiàn)

import java.util.*;

public class RBTree <Key extends Comparable<Key>, Value>{
    private class Node {
        Key key;
        Value value;
        Node left;
        Node right;
        boolean color;

        public Node(Key key, Value value, Node left, Node right, boolean color) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.color = color;
        }
    }

    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private int size;
    private Node root;


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

    private boolean isRed(Node node) {
        return node != null && node.color;
    }

    //顏色轉(zhuǎn)換
    private void flipColors(Node h) {
        h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
    }

    //左旋
    private Node rotationLeft(Node node) {
        Node x = node.right;
        node.right = x.left;
        x.left = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }

    //右旋
    private Node rotationRight(Node node) {
        Node x = node.left;
        node.left = x.right;
        x.right = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }

    //平衡操作
    private Node balance(Node node) {

        if (isRed(node.left) && isRed(node.right) && !isRed(node)) {
            if ((isRed(node.left.left) || isRed(node.left.right) || isRed(node.right.left) || isRed(node.right.right)))
                flipColors(node);
        }
        else {
            if (isRed(node.left)){
                if (isRed(node.left.right))
                    node.left = rotationLeft(node.left);
                if (isRed(node.left) && isRed(node.left.left))
                    node = rotationRight(node);
            }else if (isRed(node.right)){
                if (isRed(node.right) && isRed(node.right.left))
                    node.right = rotationRight(node.right);

                if (isRed(node.right) && isRed(node.right.right))
                    node = rotationLeft(node);
            }

            if (isRed(node.left) && isRed(node.right) && !isRed(node)) {
                if ((isRed(node.left.left) || isRed(node.left.right) || isRed(node.right.left) || isRed(node.right.right)))
                    flipColors(node);
            }
        }
        return node;
    }

    private Node max(Node node) {
        if(node == null) {
            return null;
        } else {
            while(node.right != null) {
                node = node.right;
            }

            return node;
        }
    }

    private Node min(Node node) {
        if(node == null) {
            return null;
        } else {
            while(node.left != null) {
                node = node.left;
            }

            return node;
        }
    }

    public Value max() {
        return root == null ? null : max(root).value;
    }

    public Value min() {
        return root == null ? null : min(root).value;
    }


    //插入
    public void put(Key key, Value value) {
        root = put(key, value, root);
        root.color = BLACK;
    }

    private Node put(Key key, Value value, Node node) {
        if(node == null) {
            ++size;
            return new Node(key, value, null, null, RED);
        } else {
            int cmp = key.compareTo(node.key);
            if(cmp < 0) {
                node.left = put(key, value, node.left);
            } else if (cmp > 0){
                node.right = put(key, value, node.right);
            }else{
                node.value = value;
            }

           return balance(node);
        }
    }

    public void deleteMin(){
        if (!isEmpty()){
            root.color = RED;

            root = deleteMin(root);
            --size;
            if (!isEmpty())
                root.color = BLACK;
        }
    }

    private Node deleteMin(Node node){
        if (node.left == null){
            return node.right;
        }

        if (!isRed(node.left)) {
            if(!isRed(node.left) && !isRed(node.right))
                flipColors(node);
            else
                node = rotationLeft(node);
        }

        node.left = deleteMin(node.left);

        return balance(node);

    }

    public void deleteMax(){
        if (!isEmpty()){
            root.color = RED;

            root = deleteMax(root);
            --size;
            if (!isEmpty())
                root.color = BLACK;
        }
    }

    private Node deleteMax(Node node){
        if (node.right == null){
            return node.left;
        }

        if (!isRed(node.right)) {
            if(!isRed(node.left) && !isRed(node.right))
                flipColors(node);
            else
                node = rotationRight(node);
        }

        node.right = deleteMax(node.right);

        return balance(node);

    }

    //刪除
    public void delete(Key key){
        if (!isEmpty()){
            root.color = RED;

            root = delete(key, root);

            if (!isEmpty())
                root.color = BLACK;
        }
    }

    private Node delete(Key key, Node node){
        if (node == null)
            return null;

        int cmp = key.compareTo(node.key);

        if (cmp < 0){
            if (node.left != null && !isRed(node.left)) {
                if(!isRed(node.right))
                    flipColors(node);
                else
                    node = rotationLeft(node);
            }

            node.left = delete(key, node.left);
        }else if (cmp > 0){
            if (node.right != null && !isRed(node.right)) {
                if(!isRed(node.left))
                    flipColors(node);
                else
                    node = rotationRight(node);
            }

            node.right = delete(key, node.right);
        }else {
            --size;
            if (node.left == null)
                return node.right;

            if (node.right == null)
                return node.left;

            Node x = min(node.right);
            node.key = x.key;
            node.value = x.value;

            node.right = deleteMin(node.right);
        }

        return balance(node);
    }



    //判斷樹(shù)是否為一棵紅黑樹(shù)
    public boolean isRBTree() {
        return isRBTree(root);
    }

    public boolean isRBTree(Node node) {
        if(node == null) {
            return true;
        } else if(node.color == RED) {
            return false;
        } else {
            Node x = node;
            int count = 0;

            for(; x != null; x = x.left) {
                if(x.color == BLACK) {
                    ++count;
                }
            }

            return isRBTree(node, count, 0);
        }
    }

    private boolean isRBTree(Node node, int count, int k) {
        if(node == null) {
            return count == k;
        } else if((isRed(node.left) && isRed(node.left.left))
                ||(isRed(node.left) && isRed(node.left.right))
                ||(isRed(node.right) && isRed(node.right.right))
                ||(isRed(node.right) && isRed(node.right.left))) {
            return false;
        } else {
            if(node.color == BLACK) {
                ++k;
            }
            return node.left == null && node.right == null ? k == count:isRBTree(node.left, count, k) && isRBTree(node.right, count, k);
        }
    }

    //樹(shù)的中序遍歷
    public void inTraverse(){
        inTraverse(root);
    }

    private void inTraverse(Node node){
        if (node == null)
            return;
        inTraverse(node.left);
        System.out.print(node.key + " ");
        inTraverse(node.right);
    }

    //測(cè)試
    public static void main(String[] args) {
        int n = 3000, a;
        Random random = new Random();
        RBTree<Integer, String> rbt = new RBTree();

        for (int i = 1; i <= n; ++i) {
            a = random.nextInt(50000);
            rbt.put(a, "naoko");
        }

        for (int i = 0; i < 1500; ++i) {
            rbt.delete(i);
        }

        if (!rbt.isRBTree()) {
            System.out.println("不是紅黑樹(shù)");
            return;
        }

        rbt.inTraverse();

        System.out.print("是紅黑樹(shù)");
    }

}

算法復(fù)雜度

紅黑樹(shù)和AVL樹(shù)類似甚纲，都是在進(jìn)行插入和刪除操作時(shí)通過(guò)特定操作保持樹(shù)的平衡口锭，從而獲得較高的查找性能。不同的是紅黑樹(shù)并不是向AVL樹(shù)那樣追求完美平衡介杆，而是黑色平衡鹃操，即從根結(jié)點(diǎn)到任意一個(gè)空結(jié)點(diǎn)的簡(jiǎn)單路徑上黑色結(jié)點(diǎn)數(shù)都相同。因?yàn)橐豢眉t黑樹(shù)的高度最高不超過(guò)2lg(N+1)春哨，因此其查找時(shí)間復(fù)雜度也是O(lgN)級(jí)別的荆隘。而對(duì)于插入和刪除操作產(chǎn)生不平衡情況都會(huì)在3次旋轉(zhuǎn)之內(nèi)快速解決，所以復(fù)雜度基本為O(lgN)級(jí)別赴背，也因?yàn)檫@一點(diǎn)紅黑樹(shù)的效率比AVL樹(shù)快椰拒。

最后

紅黑樹(shù)的插入和刪除操作都有自頂向下和自頂向上兩種方法，其中自頂向下較為容易凰荚，我的刪除操作實(shí)現(xiàn)屬于自頂向下的方法燃观。在JDK中的TreeMap中插入和刪除就用了自底向上的方法。

最后編輯于：2019.03.20 00:30:28

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末便瑟，一起剝皮案震驚了整個(gè)濱河市缆毁，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌到涂，老刑警劉巖脊框，帶你破解...
沈念sama閱讀 211,194評(píng)論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異践啄，居然都是意外死亡浇雹，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,058評(píng)論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門屿讽，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)昭灵，“玉大人，你說(shuō)我怎么就攤上這事』⒚” “怎么了硫痰？”我有些...
開(kāi)封第一講書人閱讀 156,780評(píng)論 0贊 346
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)窜护。經(jīng)常有香客問(wèn)我效斑，道長(zhǎng)，這世上最難降的妖魔是什么柱徙？我笑而不...
開(kāi)封第一講書人閱讀 56,388評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任缓屠，我火速辦了婚禮，結(jié)果婚禮上护侮，老公的妹妹穿的比我還像新娘敌完。我一直安慰自己，他們只是感情好羊初，可當(dāng)我...
茶點(diǎn)故事閱讀 65,430評(píng)論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布滨溉。她就那樣靜靜地躺著，像睡著了一般长赞。火紅的嫁衣襯著肌膚如雪晦攒。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書人閱讀 49,764評(píng)論 1贊 290
城市分裂傳說(shuō)
那天得哆，我揣著相機(jī)與錄音脯颜，去河邊找鬼。笑死贩据，一個(gè)胖子當(dāng)著我的面吹牛栋操，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播饱亮，決...
沈念sama閱讀 38,907評(píng)論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼矾芙，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了近尚？” 一聲冷哼從身側(cè)響起蠕啄，我...
開(kāi)封第一講書人閱讀 37,679評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤场勤，失蹤者是張志新（化名）和其女友劉穎戈锻，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體和媳，經(jīng)...
沈念sama閱讀 44,122評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡格遭，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,459評(píng)論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了留瞳。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片拒迅。...
茶點(diǎn)故事閱讀 38,605評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出璧微，到底是詐尸還是另有隱情作箍，我是刑警寧澤，帶...
沈念sama閱讀 34,270評(píng)論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布前硫，位于F島的核電站胞得，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏屹电。R本人自食惡果不足惜阶剑，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,867評(píng)論 3贊 312
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望危号。院中可真熱鬧牧愁，春花似錦、人聲如沸外莲。這莊子的主人今日做“春日...
開(kāi)封第一講書人閱讀 30,734評(píng)論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)偷线。三九已至办龄，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間淋昭，已是汗流浹背俐填。一陣腳步聲響...
開(kāi)封第一講書人閱讀 31,961評(píng)論 1贊 265
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留翔忽，地道東北人英融。一個(gè)月前我還...
沈念sama閱讀 46,297評(píng)論 2贊 360
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像歇式，于是被迫代替她去往敵國(guó)和親驶悟。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,472評(píng)論 2贊 348