Skip to content

高级数据结构

约 1093 个字 40 行代码 预计阅读时间 4 分钟

Note

oi wiki 真的是一个好东西，上面的讲解通常深入浅出

Tree

对于一颗普通的二叉树，对其节点的操作代价为\(O(\log n)\)，但是在最坏的情况下，二叉树会退化为一个链表，这是我们最不希望看到的，所以我们需要一些手段去控制树的高度。

Ritation

左旋和右旋是维持平衡的一种常用手段 alt text 代码实现如下 

TreeNode* RotateLeft(TreeNode* y){
    TreeNode* x = y->right;
    TreeNode* T2 = x->left;
    x->left = y;
    y->right = T2;
    return x;
}

TreeNode* RotateRight(TreeNode* y){
    TreeNode* x = y->left;
    TreeNode* T2 = x->right;
    x->right = y;
    y->left = T2;
    return x;
}

AVL Tree

  • 一颗空的二叉树是一个AVL树
  • 如果一个二叉树是一个AVL树，则其左右孩子树\(T_l\)和\(T_r\)，也都应该是AVL树，且有\(|h(T_l)-h(T_r)\leq 1|\)。这里我们引入一个平衡因子(Balance Factor,BF)的概念，定义\(BF(T_p)=h(T_l)-h(T_r)\)。不难证明(由线性递推求出通项)AVL Tree的高度为\(O(\log n)\)。
  • 如何维护一颗AVL Tree呢？需要用到左旋和右旋。一共分为四种情况：
  • 左子树高度比右子树大2：
    • 左子树的左子树比其右子树高：RR
    • 左子树的右子树比其左子树高：LR
  • 反过来是完全对称的
  • 代码实现总体来说还是比较简单，就分情况去旋转就行了

Splay Tree

  • Splay Tree 的核心思想是把目标点旋转到根部，达到任意M次连续的操作时间复杂度为\(O(m\log n)\)
  • 它的情况分类有很多种版本的叫法，大概如下图，显然对称情况就把操作反过来 alt text
  • 核心步骤splay代码实现 
    TreeNode* Splay(TreeNode* node,int val){
    //如果当前节点为空或者当前节点就是要查找的节点，直接返回
    if(node==nullptr||node->val==val){
        return node;
    }
    //如果要查找的节点在左子树中
    //但如果左子树为空，则待查找节点不存在
    if(val<node->val){
        if(node->left==nullptr)
            return node;
        //如果要查找的节点在左子树的左子树中
        if(val<node->left->val){
            node->left->left=Splay(node->left->left,val);
            node=RightRotate(node);
        }
        //如果要查找的节点在左子树的右子树中
        else if(val>node->left->val){
            node->left->right=Splay(node->left->right,val);
            if(node->left->right!=nullptr){
                node->left=LeftRotate(node->left);
            }
            return node->left==nullptr?node:RightRotate(node);
        }
    }
}

Red Black Tree

链接：OI Wiki Red Black Tree，这上面写的很清楚。 * 红黑树是一种自平衡的二叉搜索树。每个节点额外存储了一个 color 字段 ("RED" or "BLACK")，用于确保树在插入和删除时保持平衡。 * 一棵合法的红黑树必须遵循以下四条性质： * 节点为红色或黑色 * 根节点必须为黑色 * NIL 节点（空叶子节点）为黑色 * 红色节点的子节点为黑色 * 从根节点到 NIL 节点的每条路径上的黑色节点数量相同 alt text

B+ Tree

链接：OI Wiki B+ Tree

Warning

CYLL ads 的B+树与Data Base及网上常见的B+树定义的不太一样，具体区别在于ORDER为3的B+树，ads里面的B+树Internal Node最多只能包含两个元素，但DB里面是最多可以包含3个，所以不建议使用网上的可视化程序模拟B+树

B+树通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反。B+树相当于对数据进行了分段。 alt text

Inverted File Index

平时查找 知道关键词然后去检索相关文件，如何能更快？ 1. Scan each page for the intended string,显然这个太慢了 2. Term-Document Incidence Matrix,这个会消耗大量的存储空间，而且维护困难 3. Compact Version-Inverted File Index

Optimizer

stop words

这个需要根据实际情况判断

word stemming

Searching

Search trees

Hashing

同一个词的不同时态可以合并

Heap

Leftist Heap

  • 左倾堆实际上是一种不平衡的二叉树，每个节点左儿子的 dist 都大于等于右儿子的 dist。所以它也可以叫左偏树
  • 对于任意一个节点x，通往一个没有两个子节点的节点的最短路径长称为NPL(x)，空节点的NPL值为-1 alt text

Skew Heap

斜堆是左偏树的自适应形式，就是不管怎么样都要交换左右儿子。当合并两个堆时，它无条件交换合并路径上的所有节点，以此试图维护平衡。

Binomial Heap

二项队列既不是数组，也不是树。二项队列的真身是一个小数组+若干棵树。设数组为root[]，每棵树为\(B_k\)，k为这棵树的高度。 数组root[]里装的是每棵树的根节点指针，root[i]里面的元素要么是空指针，要么是一个固定大小的树的根节点指针，这棵树的高度为i，大小为 \(2^i\)。 alt text