@[toc]
二叉树
没啥好讲的，参考我大一写的二叉树的博客。
二叉搜索树（二叉排序树，二叉查找树，BST）
百度百科讲解
注意没有键值相同的节点。
删除树节点分三种情况：
-
是叶子节点，那么直接
掉就行了，不用再去改变树结构。
-
-
AVL 平衡二叉查找树
参考：百度百科，hxraid博客
AVL树每个节点的平衡因子只可能是-1、0和1（左子树高度减去右子树高度）。
当插入节点后，若破坏了AVL树的平衡性，则找到失去平衡的最小 子树根结点。所谓最小不平衡子树 指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
有四种旋转：
- 当树中节点X的右孩子的右孩子上插入新元素，且平衡因子从-1变成-2后，就需要绕节点X进行左旋转。
- 当树中节点X的左孩子的左孩子上插入新元素，且平衡因子从1变成2后，就需要绕节点X进行右旋转。
- 当树中节点X的左孩子的右孩子上插入新元素，且 平衡因子从1变成2后，就需要 先绕X的左子节点Y左旋转，接着再绕X右旋转
- 当树中节点X的右孩子的左孩子上插入新元素，且 平衡因子从-1变成-2后，就需要 先绕X的右子节点Y右旋转，接着再绕X左旋转
左旋转（你是父节点的右儿子）：把父节点变成你的左儿子，把原来的左儿子给原来的父节点当他的右儿子。
右旋转（你是父节点的左儿子）：把父节点变成你的右儿子，把原来的右儿子给原来的父节点当他的左儿子。
平衡二叉树的缺陷：
(1) 很遗憾的是，为了保证高度平衡，动态插入和删除的代价也随之增加。因此，可以了解《红黑树》 这种更加高效的查找结构。
(2) 所有二叉查找树结构的查找代价都与树高是紧密相关的，能否通过减少树高来进一步降低查找代价呢。我们可以通过多路查找树的结构来做到这一点，将通过《多路查找树/B-树/B+树 》来介绍。
(3) 在大数据量查找环境下(比如说系统磁盘里的文件目录，数据库中的记录查询 等)，所有的二叉查找树结构(BST、AVL、RBT)都不合适。如此大规模的数据量（几G数据），全部组织成平衡二叉树放在内存中是不可能做到的。那么把这棵树放在磁盘中吧。问题就来了：假如构造的平衡二叉树深度有1W层。那么从根节点出发到叶子节点很可能就需要1W次的硬盘IO读写。大家都知道，硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。 查找效率在IO读写过程中将会付出巨大的代价。在大规模数据查询这样一个实际应用背景下，平衡二叉树的效率就很成问题了。对这一问题的解决：也会在《多路查找树/B-树/B+树 》 将详细分析。
上面提到的红黑树和多路查找树都是属于深度有界查找树（depth-bounded tree —DBT）
Splay Tree
伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在内完成插入、查找和删除操作。
在伸展树上的一般操作都基于伸展操作：
假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。
伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
它的优势在于不需要记录用于平衡树的冗余信息。
参考：lazy-people，oi-wiki
其实伸展树的左旋右旋和平衡二叉树是一样的，只是伸展树的操作比较神奇。
当节点和父节点
都是左儿子或者右儿子时，出现了三点一线的情况，要避免单旋导致平衡数失衡。
这时候要先旋转父节点和祖父节点这条边，再旋转节点和新父节点这条边。
伸展树最显著的缺点是它有可能会变成一条链。这种情况可能发生在以非降顺序访问n个元素之后。然而均摊的最坏情况是对数级的——O(logn)。
题目：
loj104普通平衡树
loj105文艺平衡树
2018第三场牛客C题
hzwer
我自己写的模板：https://pasteme.cn/26625，https://paste.ubuntu.com/p/Jcjp6trpcq/
Treap
模板题LOJ104代码：https://pasteme.cn/26829
非旋转Treaphttps://www.luogu.com.cn/problemnew/solution/P3391
红黑树
30张图带你彻底理解红黑树
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
多路查找树/B~树/B+树
STL
手写二叉堆
struct min_heap {
int siz;
int ar[MXN];
void clear() {
siz = 0;
memset(ar, 0, sizeof(ar));
}
void push(int x) {
ar[++ siz] = x;
int p = siz;
while(p > 1) {
if(ar[p/2] > ar[p]) swap(ar[p], ar[p/2]);
else break;
p /= 2;
}
}
void pop() {
if(siz == 0) return ;
swap(ar[1], ar[siz]);
-- siz;
int p = 1, replace;
while(p * 2 <= siz) {
if(ar[p * 2] < ar[p]) replace = p * 2;
else replace = p;
if(p * 2 + 1 <= siz && ar[p<<1|1] <= ar[p<<1] && ar[p<<1|1] < ar[p]) {
replace = p * 2 + 1;
}
if(replace != p) {
swap(ar[replace], ar[p]);
p = replace;
}else break;
}
}
int top() {
return ar[1];
}
bool empty() {
return siz == 0;
}
}que;
LIST
Lst1.assign() 给list赋值
Lst1.back() 返回最后一个元素
Lst1.begin() 返回指向第一个元素的迭代器
Lst1.clear() 删除所有元素
Lst1.empty() 如果list是空的则返回true
Lst1.end() 返回末尾的迭代器
Lst1.erase() 删除一个元素
Lst1.front() 返回第一个元素
Lst1.get_allocator() 返回list的配置器
Lst1.insert() 插入一个元素到list中
Lst1.max_size() 返回list能容纳的最大元素数量
Lst1.merge() 合并两个list
Lst1.pop_back() 删除最后一个元素
Lst1.pop_front() 删除第一个元素
Lst1.push_back() 在list的末尾添加一个元素
Lst1.push_front() 在list的头部添加一个元素
Lst1.rbegin() 返回指向第一个元素的逆向迭代器
Lst1.remove() 从list删除元素
Lst1.remove_if() 按指定条件删除元素
Lst1.rend() 指向list末尾的逆向迭代器
Lst1.resize() 改变list的大小
Lst1.reverse() 把list的元素倒转
Lst1.size() 返回list中的元素个数
Lst1.sort() 给list排序
Lst1.swap() 交换两个list
Lst1.unique() 删除list中重复的元素
Lst1.splice() 合并两个list
//将元素从x转移到容器中，将其插入位置。这有效地将这些元素插入到容器中，并从x中删除它们，从而改变两个容器的大小
链表写的归并排序
#include <random>
#include <cstdio>
#include <iostream>
#include <assert.h>
using namespace std;
class node {
public:
int val;
node *Next;
node() {
val = -1;
Next = nullptr;
}
node(int _val):val(_val){
Next = nullptr;
}
};
node *root = new node(), *last;
void Print(node *cur) {
while(cur != nullptr) {
printf("%d ", cur->val);
cur = cur->Next;
}
printf("\n");
}
int getLen(node *cur) {
int cnt = 0;
while(cur != nullptr) {
cur = cur->Next;
++ cnt;
}
return cnt;
}
node * getNode(node *cur, int len) {
node *tmp = cur;
while(len > 0) {
-- len;
cur = cur->Next;
tmp = cur;
}
return tmp;
}
node *myMerge(node *ar, node *br) {
node * head = new node();
node * tmp = head;
while(ar != nullptr && br != nullptr) {
if(ar->val <= br->val) tmp->Next = ar, tmp = tmp->Next, ar = ar->Next;
else tmp->Next = br, tmp = tmp->Next, br = br->Next;
}
while(ar != nullptr) {
tmp->Next = ar, tmp = tmp->Next, ar = ar->Next;
}
while(br != nullptr) {
tmp->Next = br, tmp = tmp->Next, br = br->Next;
}
return head->Next;
}
node * mySort(node *cur, int len) {
if(cur == nullptr || cur->Next == nullptr) return cur;
node * firstTail = getNode(cur, len/2-1);
node * secHead = firstTail->Next;
firstTail->Next = nullptr;
assert(len/2==getLen(cur));
cur = mySort(cur, len/2);
assert(len-len/2==getLen(secHead));
secHead = mySort(secHead, len-len/2);
cur = myMerge(cur, secHead);
return cur;
}
int main() {
last = root;
for(int i = 1; i <= 837234; ++i) {
node *tmp = new node(rand()%20);
last->Next = tmp;
last = tmp;
}
// Print(root->Next);
int len = getLen(root->Next);
root->Next = mySort(root->Next, len);
// Print(root->Next);
system("pause");
return 0;
}
