数据结构中各种树

阅读目录

1. 二叉树
2. 二叉查找树
3. 平衡二叉树

3.1 平衡查找树之AVL树
3.2 平衡二叉树之红黑树

4. B树
5. B+树
6. B*树
7. Trie树

　　数据结构中有很多树的结构，其中包括二叉树、二叉搜索树、2-3树、红黑树等等。本文中对数据结构中常见的几种树的概念和用途进行了汇总，不求严格精准，但求简单易懂。

回到顶部回到顶部回到顶部wiki百科之红黑树。

红黑树的自平衡操作：

　　因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(logn))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为O(logn) 次。

我们首先以二叉查找树的方法增加节点并标记它为红色。如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的（违背性质5）。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样，我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。注意:

性质1和性质3总是保持着。
性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。
性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁。

插入操作：

　　假设，将要插入的节点标为N，N的父节点标为P，N的祖父节点标为G，N的叔父节点标为U。在图中展示的任何颜色要么是由它所处情形这些所作的假定，要么是假定所暗含的。

　　情形1: 该树为空树，直接插入根结点的位置，违反性质1，把节点颜色有红改为黑即可。

情形2: 插入节点N的父节点P为黑色，不违反任何性质，无需做任何修改。在这种情形下，树仍是有效的。性质5也未受到威胁，尽管新节点N有两个黑色叶子子节点；但由于新节点N是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个性质。

　　注：情形1很简单，情形2中P为黑色，一切安然无事，但P为红就不一样了，下边是P为红的各种情况，也是真正难懂的地方。

　　情形3: 如果父节点P和叔父节点U二者都是红色，(此时新插入节点N做为P的左子节点或右子节点都属于情形3,这里右图仅显示N做为P左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质4)。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点G的父节点也有可能是红色的，这就违反了性质4。为了解决这个问题，我们在祖父节点G上递归地进行上述情形的整个过程（把G当成是新加入的节点进行各种情形的检查）。比如，G为根节点，那我们就直接将G变为黑色（情形1）；如果G不是根节点，而它的父节点为黑色，那符合所有的性质，直接插入即可（情形2）；如果G不是根节点，而它的父节点为红色，则递归上述过程（情形3）。

　　情形4: 父节点P是红色而叔父节点U是黑色或缺少，新节点N是其父节点的左子节点，而父节点P又是其父节点G的左子节点。在这种情形下，我们进行针对祖父节点G的一次右旋转; 在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G的父节点。我们知道以前的祖父节点G是黑色，否则父节点P就不可能是红色(如果P和G都是红色就违反了性质4，所以G必须是黑色)。我们切换以前的父节点P和祖父节点G的颜色，结果的树满足性质4。性质5也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G，现在它们都通过以前的父节点P。在各自的情形下，这都是三个节点中唯一的黑色节点。

情形5 示意图

　　情形5: 父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点。在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色; 接着，我们按情形4处理以前的父节点P以解决仍然失效的性质4。注意这个改变会导致某些路径通过它们以前不通过的新节点N（比如图中1号叶子节点）或不通过节点P（比如图中3号叶子节点），但由于这两个节点都是红色的，所以性质5仍有效。

情形4 示意图

注: 插入实际上是原地算法，因为上述所有调用都使用了尾部递归。

　　删除操作：

　　如果需要删除的节点有两个儿子，那么问题可以被转化成删除另一个只有一个儿子的节点的问题。对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素，并把它的值转移到要删除的节点中。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值，不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。

　　我们只需要讨论删除只有一个儿子的节点(如果它两个儿子都为空，即均为叶子，我们任意将其中一个看作它的儿子)。如果我们删除一个红色节点（此时该节点的儿子将都为叶子节点），它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它，并不会破坏性质3和性质4。通过被删除节点的所有路径只是少了一个红色节点，这样可以继续保证性质5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点，用它的红色儿子顶替上来的话，会破坏性质5，但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5。

　　需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候，这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为N(在新的位置上)，称呼它的兄弟(它父亲的另一个儿子)为S。在下面的示意图中，我们还是使用P称呼N的父亲，S_L称呼S的左儿子，S_R称呼S的右儿子。

　　如果N和它初始的父亲是黑色，则删除它的父亲导致通过N的路径都比不通过它的路径少了一个黑色节点。因为这违反了性质5，树需要被重新平衡。有几种情形需要考虑:

　　情形1: N是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。

注意: 在情形2、5和6下，我们假定N是它父亲的左儿子。如果它是右儿子，则在这些情形下的左和右应当对调。

　　情形2: S是红色。在这种情形下我们在N的父亲上做左旋转，把红色兄弟转换成N的祖父，我们接着对调N的父亲和祖父的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在N有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色S的一个儿子），所以我们可以接下去按情形4、情形5或情形6来处理。

情形2 示意图

　　情形3: N的父亲、S和S的儿子都是黑色的。在这种情形下，我们简单的重绘S为红色。结果是通过S的所有路径，它们就是以前不通过N的那些路径，都少了一个黑色节点。因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反性质5。要修正这个问题，我们要从情形1开始，在P上做重新平衡处理。

情形3 示意图

情形4: S和S的儿子都是黑色，但是N的父亲是红色。在这种情形下，我们简单的交换N的兄弟和父亲的颜色。这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。

情形4 示意图

情形5: S是黑色，S的左儿子是红色，S的右儿子是黑色，而N是它父亲的左儿子。在这种情形下我们在S上做右旋转，这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个黑色兄弟，他的右儿子是红色的，所以我们进入了情形6。N和它的父亲都不受这个变换的影响。

情形5 示意图

　　情形6: S是黑色，S的右儿子是红色，而N是它父亲的左儿子。在这种情形下我们在N的父亲上做左旋转，这样S成为N的父亲（P）和S的右儿子的父亲。我们接着交换N的父亲和S的颜色，并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以性质3没有被违反。但是，N现在增加了一个黑色祖先: 要么N的父亲变成黑色，要么它是黑色而S被增加为一个黑色祖父。所以，通过N的路径都增加了一个黑色节点。

　　此时，如果一个路径不通过N，则有两种可能性:

它通过N的新兄弟。那么它以前和现在都必定通过S和N的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。
它通过N的新叔父，S的右儿子。那么它以前通过S、S的父亲和S的右儿子，但是现在只通过S，它被假定为它以前的父亲的颜色，和S的右儿子，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。

　　在任何情况下，在这些路径上的黑色节点数目都没有改变。所以我们恢复了性质4。在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色。

情形6 示意图

红黑树实现源码：

#define BLACK 1
#define RED 0

using namespace std;

class bst {
private:

    struct Node {
        int value;
        bool color;
        Node *leftTree, *rightTree, *parent;

        Node() {
            color = RED;
            leftTree = NULL;
            rightTree = NULL;
            parent = NULL;
            value = 0;
        }

        Node* grandparent() {
            if (parent == NULL) {
                return NULL;
            }
            return parent-&gt;parent;
        }

        Node* uncle() {
            if (grandparent() == NULL) {
                return NULL;
            }
            if (parent == grandparent()-&gt;rightTree)
                return grandparent()-&gt;leftTree;
            else
                return grandparent()-&gt;rightTree;
        }

        Node* sibling() {
            if (parent->leftTree == this)
                return parent-&gt;rightTree;
            else
                return parent-&gt;leftTree;
        }
    };

    void rotate_right(Node *p) {
        Node *gp = p-&gt;grandparent();
        Node *fa = p-&gt;parent;
        Node *y = p-&gt;rightTree;

        fa->leftTree = y;

        if (y != NIL)
            y->parent = fa;
        p->rightTree = fa;
        fa->parent = p;

        if (root == fa)
            root = p;
        p->parent = gp;

        if (gp != NULL) {
            if (gp->leftTree == fa)
                gp->leftTree = p;
            else
                gp->rightTree = p;
        }

    }

    void rotate_left(Node *p) {
        if (p->parent == NULL) {
            root = p;
            return;
        }
        Node *gp = p-&gt;grandparent();
        Node *fa = p-&gt;parent;
        Node *y = p-&gt;leftTree;

        fa->rightTree = y;

        if (y != NIL)
            y->parent = fa;
        p->leftTree = fa;
        fa->parent = p;

        if (root == fa)
            root = p;
        p->parent = gp;

        if (gp != NULL) {
            if (gp->leftTree == fa)
                gp->leftTree = p;
            else
                gp->rightTree = p;
        }
    }

    void inorder(Node *p) {
        if (p == NIL)
            return;

        if (p-&gt;leftTree)
            inorder(p-&gt;leftTree);

        cout << p->value << " ";
                
        if (p-&gt;rightTree)
            inorder(p-&gt;rightTree);
    }

    string outputColor(bool color) {
        return color ? "BLACK" : "RED";
    }

    Node* getSmallestChild(Node *p) {
        if (p->leftTree == NIL)
            return p;
        return getSmallestChild(p-&gt;leftTree);
    }

    bool delete_child(Node *p, int data) {
        if (p->value &gt; data) {
            if (p->leftTree == NIL) {
                return false;
            }
            return delete_child(p-&gt;leftTree, data);
        } else if (p->value &lt; data) {
            if (p->rightTree == NIL) {
                return false;
            }
            return delete_child(p-&gt;rightTree, data);
        } else if (p->value == data) {
            if (p->rightTree == NIL) {
                delete_one_child(p);
                return true;
            }
            Node *smallest = getSmallestChild(p-&gt;rightTree);
            swap(p->value, smallest-&gt;value);
            delete_one_child(smallest);

            return true;
        }
    }

    void delete_one_child(Node *p) {
        Node *child = p->leftTree == NIL ? p->rightTree : p-&gt;leftTree;
        if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL) {
            p = NULL;
            root = p;
            return;
        }
        
        if (p->parent == NULL) {
            delete  p;
            child->parent = NULL;
            root = child;
            root->color = BLACK;
            return;
        }
        
        if (p->parent->leftTree == p) {
            p->parent->leftTree = child;
        } else {
            p->parent->rightTree = child;
        }
        child->parent = p-&gt;parent;

        if (p->color == BLACK) {
            if (child->color == RED) {
                child->color = BLACK;
            } else
                delete_case(child);
        }

        delete p;
    }

    void delete_case(Node *p) {
        if (p->parent == NULL) {
            p->color = BLACK;
            return;
        }
        if (p->sibling()->color == RED) {
            p->parent->color = RED;
            p->sibling()->color = BLACK;
            if (p == p->parent-&gt;leftTree)
                rotate_left(p-&gt;sibling());
            else
                rotate_right(p-&gt;sibling());
        }
        if (p->parent->color == BLACK && p->sibling()->color == BLACK
                && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
            p->sibling()->color = RED;
            delete_case(p-&gt;parent);
        } else if (p->parent->color == RED && p->sibling()->color == BLACK
                && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
            p->sibling()->color = RED;
            p->parent->color = BLACK;
        } else {
            if (p->sibling()->color == BLACK) {
                if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED
                        && p->sibling()->rightTree->color == BLACK) {
                    p->sibling()->color = RED;
                    p->sibling()->leftTree->color = BLACK;
                    rotate_right(p->sibling()-&gt;leftTree);
                } else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
                        && p->sibling()->rightTree->color == RED) {
                    p->sibling()->color = RED;
                    p->sibling()->rightTree->color = BLACK;
                    rotate_left(p->sibling()-&gt;rightTree);
                }
            }
            p->sibling()->color = p->parent-&gt;color;
            p->parent->color = BLACK;
            if (p == p->parent-&gt;leftTree) {
                p->sibling()->rightTree->color = BLACK;
                rotate_left(p-&gt;sibling());
            } else {
                p->sibling()->leftTree->color = BLACK;
                rotate_right(p-&gt;sibling());
            }
        }
    }

    void insert(Node *p, int data) {
        if (p->value >= data) {
            if (p->leftTree != NIL)
                insert(p-&gt;leftTree, data);
            else {
                Node *tmp = new Node();
                tmp->value = data;
                tmp->leftTree = tmp->rightTree = NIL;
                tmp->parent = p;
                p->leftTree = tmp;
                insert_case(tmp);
            }
        } else {
            if (p->rightTree != NIL)
                insert(p-&gt;rightTree, data);
            else {
                Node *tmp = new Node();
                tmp->value = data;
                tmp->leftTree = tmp->rightTree = NIL;
                tmp->parent = p;
                p->rightTree = tmp;
                insert_case(tmp);
            }
        }
    }

    void insert_case(Node *p) {
        if (p->parent == NULL) {
            root = p;
            p->color = BLACK;
            return;
        }
        if (p->parent->color == RED) {
            if (p->uncle()->color == RED) {
                p->parent->color = p->uncle()->color = BLACK;
                p->grandparent()->color = RED;
                insert_case(p-&gt;grandparent());
            } else {
                if (p->parent->rightTree == p && p->grandparent()->leftTree == p-&gt;parent) {
                    rotate_left(p);
                    rotate_right(p);
                    p->color = BLACK;
                    p->leftTree->color = p->rightTree->color = RED;
                } else if (p->parent->leftTree == p && p->grandparent()->rightTree == p-&gt;parent) {
                    rotate_right(p);
                    rotate_left(p);
                    p->color = BLACK;
                    p->leftTree->color = p->rightTree->color = RED;
                } else if (p->parent->leftTree == p && p->grandparent()->leftTree == p-&gt;parent) {
                    p->parent->color = BLACK;
                    p->grandparent()->color = RED;
                    rotate_right(p-&gt;parent);
                } else if (p->parent->rightTree == p && p->grandparent()->rightTree == p-&gt;parent) {
                    p->parent->color = BLACK;
                    p->grandparent()->color = RED;
                    rotate_left(p-&gt;parent);
                }
            }
        }
    }

    void DeleteTree(Node *p) {
        if (!p || p == NIL) {
            return;
        }
        DeleteTree(p-&gt;leftTree);
        DeleteTree(p-&gt;rightTree);
        delete p;
    }
public:

    bst() {
        NIL = new Node();
        NIL->color = BLACK;
        root = NULL;
    }

    ~bst() {
        if (root)
            DeleteTree(root);
        delete NIL;
    }

    void inorder() {
        if (root == NULL)
            return;
        inorder(root);
        cout <&lt; endl;
    }

    void insert(int x) {
        if (root == NULL) {
            root = new Node();
            root->color = BLACK;
            root->leftTree = root->rightTree = NIL;
            root->value = x;
        } else {
            insert(root, x);
        }
    }

    bool delete_value(int data) {
        return delete_child(root, data);
    }
private:
    Node *root, *NIL;
};
回到顶部回到顶部回到顶部回到顶部
7. Trie树
　　Tire树称为字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
Tire树的三个基本性质：
　　1) 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
　　2) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
　　3) 每个节点的所有子节点包含的字符都不相同。
Tire树的应用：
　　1) 串的快速检索
　　给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。
　　2) “串”排序
　　给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出。用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。
3) 最长公共前缀
　　对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为求公共祖先的问题。

CC++

数据结构中各种树

2. 二叉查找树

3. 平衡二叉树

3.1 平衡查找树之AVL树

3.2 平衡二叉树之红黑树

4. B树

5. B+树

6. B*树

7. Trie树

相关

C/C++避免头文件重复包含的方法

C/C++ 调用API获取当前时间

【转载】VSCode配置C/C++环境

C/C++ Qt ToolBar 菜单组件应用

C/C++ Qt ToolBar 菜单组件应用

Python与C/C++的混合调用

c/c++中的友元设计

Mac(M1)配置VSCode中C/C++环境(只需三步)

c/c++ # and ## in macros以及宏debug

cmake生成Makefile时指定c/c++编译器

C/C++双叹号!!运算符

winexec()函数的参数说明(C/C++)

标签