雨羊的博客

红黑树

参考：面试问你红黑树，可以这样回答红黑树详解，对插入旋转独到理解红黑树变色和旋转，图文案例讲解红黑树简介及左旋、右旋、变色 1. 红黑树简介 1.1 为什么要使用红黑树红黑树是一种自平衡的二叉查找树。对于二叉查找树，容易出现严重单边长的情况，会

树

参考：AVL 树 1. 什么是 AVL 树 AVL 树，自平衡二叉查找树，名字来源于作者首字母大写。在 AVL 树中，任一节点对应的两颗子树最大高度差为1，因此，AVL 树也称为高度平衡树。查找、删除、插入平均、最坏复杂度都是O(log n)，增加和删除元素的操作可能触发一次或多次树旋转。 2.

树

参考文档：漫画：什么是B-树？漫画：什么是B+树？ 1. B- 树 B- 树念 B 树，不念 B 减树 1.1 数据库索引为什么不使用二叉查找树？其实从算法逻辑上来讲，二叉查找树查找速度和比较次数都是最小的。但是，我们不得不考虑一个现实问题：磁盘 IO。数据库索引是存储在磁盘上的，当数据量比

树

参考链接据结构——线段树引例给出n个数，n<=100，和m个询问，每次询问区间[l，r]的和，并输出。一种回答：这也太简单了，O（n）枚举搜索就行了。另一种回答：还用得着o(n）枚举，前缀和o(1)就搞定。那好，我再修改一下题目。给出n个数，n<=100，和m个操作，每个操作可能有两种

树

什么是 Trie 树 Trie 树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。如下图：上图是一棵 Trie 树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出 Tr

树

已知先序中序构树 #include <cstdio> #include <iostream> using namespace std; const int N = 50; int pre[N], in[N], post[N]; //存放先序，中序，后序的数组 int n;//树中元素

树

const int MAXN=1005; int father[MAXN]; int find(int x)//寻找根结点 { if(x==father[x])return x; return father[x]=find(father[x]); //压缩路径 } void merge

树