基本数据结构

简介

基本数据结构有：array, list, queue, stack, map, tree, heap, graph, sorting

array, list, queue, stack请参考c++ 标准库.

标准库中一般有对应的类：

array: std::vector, std::array, std::deque
list: std::list
queue: std::queue
stack: std::stack
heap: std::priority_queue
map: std::map(single value with same key), std::multimap(multiple values with same key)
sort: std::sort, std::qsort

对于这些数据结构的具体定义请参考专业书籍。

注意：我们后面仅用数学上的大于来代表实际的大于（比如实际上大于有可能是比较某个字符串，也有可能是非大于，即小于等于）。

暂时省略掉array, list, queue, stack的实现，下面主要实现一些基本的数据: (由于c++模板中没有virutal method，所以全部采用int来作为数据类型。如果是其他类型，可以用一个map来映射int->具体数据类型)

Tree

Tree: 树。

树的遍历：先序、中序、后序遍历。其中先序遍历得到的表达式，我们称为前缀表达式（波兰表达式，Polish Notation），中序遍历得到的表达式称为中缀表达式，后序遍历得到的表达式称为后缀表达式（逆波兰表达式，Reverse Polish Notation）。

这里主要实现二叉树和二叉搜索树

二叉树长这个样子:

bitree

二叉树

// .h

//
// Created on 3/22/18.
//

#ifndef AGORITHM_BITREE_H
#define AGORITHM_BITREE_H

#include <string>
#include <functional>
#include <stack>
#include <iostream>
#include "Node.h"

struct BiTree {
public:
    struct Node;

    using VisitFunc = std::function<void(Node *)>;
    using DeleteFunc = std::function<void(Node *)>;

    BiTree() : BiTree(nullptr, nullptr) {}

    explicit BiTree(int value) : BiTree(NewNode(value), nullptr) {}

    explicit BiTree(const DeleteFunc &func) : BiTree(nullptr, func) {}

    BiTree(Node *root, const DeleteFunc &func) {
        this->root = root;
        if (!func) {
            this->deleteFunc = [](Node *p) { delete p; };
        } else {
            this->deleteFunc = func;
        }
    }

    virtual ~BiTree();

    struct Node {
        Node() = default;

        explicit Node(int value, Node *left = nullptr, Node *right = nullptr) {
            this->value = value;
            this->left = left;
            this->right = right;
        }

        Node *left = nullptr;
        Node *right = nullptr;
        int value = 0;
    };


    virtual bool Empty() { return root == nullptr; }

    static void InOrderTraverse(const BiTree &tree, const VisitFunc &fn);

    static void PreOrderTraverse(const BiTree &tree, const VisitFunc &fn);

    static void PostOrderTraverse(const BiTree &tree, const VisitFunc &fn);

    static Node *NewNode(int value);

    static Node *NewNode();

protected:
    virtual void deleteTree(Node *node);

public:
    Node *root = nullptr;
    DeleteFunc deleteFunc = nullptr;;
};

#endif //AGORITHM_BITREE_H

// .cpp

//
// Created on 3/27/18.
//

#include "BiTree.h"

void BiTree::InOrderTraverse(const BiTree &tree, const BiTree::VisitFunc &fn) {
    auto p = tree.root;
    std::stack<decltype(p)> stk;

    while (p) { // push left
        stk.push(p);
        p = p->left;
    }
    while (!stk.empty()) {
        p = stk.top();
        stk.pop();
        fn(p);
        if (p->right) {
            p = p->right;
            while (p) { // push right first, then push leftmost of right
                stk.push(p);
                p = p->left;
            }
        }
    }
}

void BiTree::PreOrderTraverse(const BiTree &tree, const BiTree::VisitFunc &fn) {
    auto p = tree.root;
    std::stack<decltype(p)> stk;
    stk.push(p);

    while (!stk.empty()) {
        p = stk.top();
        stk.pop();
        if (p->right) {
            stk.push(p->right);
        }
        if (p->left) {
            stk.push(p->left);
        }
        fn(p);     // place at end of block, because it's used in tree destruction
    }
}

void BiTree::PostOrderTraverse(const BiTree &tree, const BiTree::VisitFunc &fn) {
    auto p = tree.root;
    std::stack<decltype(p)> stk;
    decltype(p) pre = nullptr;

    stk.push(p);
    while (!stk.empty()) {
        p = stk.top();
        if ((!p->left && !p->right) || (pre && (p->left == pre || p->right == pre))) {
            stk.pop();
            fn(p);
            pre = p;
        } else {
            // right and left node are always on top of root node. if previous visited node is left
            // or right child of this node, it means that its left and child nodes are visited
            if (p->right) {
                stk.push(p->right);
            }
            if (p->left) {
                stk.push(p->left);
            }
        }
    }
}

BiTree::Node *BiTree::NewNode(int value) {
    return new Node(value);
}

BiTree::Node *BiTree::NewNode() {
    return new Node();
}

BiTree::~BiTree() {
    deleteTree(root);
    root = nullptr;
}

void BiTree::deleteTree(BiTree::Node *node) {
    PreOrderTraverse(*this, this->deleteFunc);
}

二叉搜索树: 对于任一非叶子节点，它的值小于它的左子节点的值，大于它右子节点的值。

// .h
#ifndef AGORITHM_BSNODE_H
#define AGORITHM_BSNODE_H


#include "BiTree.h"

class BSTree : public BiTree {
public:
    virtual bool Insert(int value);

    virtual bool Insert(int value, Node *&location);

    virtual bool Search(int value, Node *&location);

    virtual bool Remove(int value);

private:
    bool Search(Node *node, Node *&location, Node *parent, int value);

    void RemoveNode(Node *&node);
};

#endif //AGORITHM_BSNODE_H

//.cpp

#include "BSTree.h"

bool BSTree::Insert(int value) {
    Node *location = nullptr;
    return Insert(value, location);
}

bool BSTree::Insert(int value, Node *&location) {
    if (this->Empty()) {
        this->root = NewNode(value);
        return true;
    }

    Node *pos = nullptr;
    bool found = Search(value, pos);
    if (found) {
        return false;
    }

    auto newNode = NewNode(value);
    if (pos->value > value) {
        pos->left = newNode;
    } else {
        pos->right = newNode;
    }

    location = newNode;
    return true;
}


bool BSTree::Search(int value, Node *&location) {
    if (Empty()) {
        return false;
    }

    return Search(this->root, location, nullptr, value);
}

bool BSTree::Search(Node *node, Node *&location, Node *parent, int value) {
    if (!node) {
        location = parent;
        return false;
    }

    if (node->value < value) {
        return Search(node->right, location, node, value);
    } else if (node->value > value) {
        return Search(node->left, location, node, value);
    }

    location = node;
    return true;
}

bool BSTree::Remove(int value) {
    if (this->Empty()) {
        return false;
    }

    std::stack<std::reference_wrapper<Node *>> stk;
    stk.push(this->root);

    while (!stk.empty()) {
        auto &p = stk.top().get();
        stk.pop();

        if (p) {
            if (p->value == value) {
                RemoveNode(p);
                return true;
            } else if (p->value < value) {
                stk.push(p->right);
            } else {
                stk.push(p->left);
            }
        }
    }
    return false;
}


void BSTree::RemoveNode(Node *&node) {
    Node *old = node;
    if (!node->left) {  // left child null.
        node = node->right;
    } else if (!node->right) {  // right null
        node = node->left;
    } else {    // both left and right not null.
        auto cur = node->left;
        auto pre = node;
        while (cur->right) {  // rightmost element of left child of node
            pre = cur;
            cur = cur->right;
        }

        if (pre != old) {   // rightmost exists
            pre->right = cur->left;
            cur->left = node->left;
        } else {    // rightmost node doesn't exist
//            cur->right = node->right;
        }
        cur->right = node->right;
        node = cur;
    }
    deleteFunc(old);
}

对于一颗普通的二叉搜索树，插入/删除/搜索的时间复杂度为O(n)。

对于一颗AVL树（平衡二叉树），插入/删除/搜索的时间复杂度为O(logn)。（这里没有实现AVL树）

红黑树, B-树，B⁺树

红黑树

AVL树每一次插入删除通常都会引起旋转。而红黑树追求局部平衡，所以整体性能比AVL树更高。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

一颗红黑树长这个样子：

rbtree

B-树

B-树是一种平衡的多路查找树。它在文件系统中很有用。

一颗m阶B-树或为空树，或满足如下特性：

树中每个节点至多有m棵子树
若根节点不是叶子节点，则至少有两颗子树
除根节点之外的所有非终端节点至少有k棵子树，k的值为不小于m/2的最小整数
所有的非叶子节点包含以下信息
(n, A₀, K₁, A₁, K₂, A₂, ... A_n)
其中：n是该节点叶子节点的个数，A_i指向第i个子树（i从0开始），K_i（i从1开始）是第i个关键字。对于K_i，它大于A_i-1指向的子树的所有节点的关键字，它小于A_i指向的子树的所有节点的关键字。
所有的叶子节点出现在同一层次上，并且不带信息。（可视作空指针）

一棵4阶B树如下图：

btree

时间复杂度为logn

B⁺树

B⁺树是应文件系统所需而出的一种B-树的变形树。一棵m阶B-树和B⁺树的差异在与：

有n棵子树的节点中含有n个关键字（B-树是n-1个关键字）
所有的叶子节点包含了全部关键字信息，且叶子节点本身依关键字从小到大顺序链接。
所有的非叶子节点可以看成是全部关键字的一个子集，且节点中仅含有其子树的最大关键字。

一棵3-阶B⁺树如下图所示：

bplustree

时间复杂度为logn

至于为什么会在文件系统中用B⁺树，我们可以自己算一下：假设有n树个节点，如果用AVL树，来找，至多会进行logn次查找，都是从磁盘中读取的。对于B⁺树，也至多会进行logn次查找，但对在某个节点中，查找一个关键字时，是在内存中进行的。由于访问内存的速度比磁盘快，所以B⁺树的查找速度快于AVL树。

具体实现请参考专业书籍

基本数据结构-树

基本数据结构-树

基本数据结构

简介

Tree

红黑树, B-树，B⁺树

红黑树

B-树

B⁺树

基本数据结构-树

基本数据结构

简介

Tree

红黑树, B-树，B+树

红黑树

B-树

B+树

红黑树, B-树，B⁺树

B⁺树