共计 117776 个字符，预计需要花费 295 分钟才能阅读完成。
树的基本概念
树的存储构造
双亲表示法
假如以一组间断空间存储树的结点，同时在每一个结点中，设置一个指示器指示器双亲结点在数组的地位
// 结点
struct Node{
Element data;
int parent; // 双亲地位
};
// 树结构
struct Tree{Node node[MAX_TREE_SIZE];
int r, n; // 根的地位和结点
};找双亲的效率高，但找孩子的效率低。
当然如果须要，咱们能够持续扩大数据结构，给其减少一个长子域…..
数据结构的设计是非常灵活的，一个数据结构是否正当次要取决于工夫和空间复杂度是否适宜以后场景
孩子表示法
因为每个结点可能有多个子树，所以能够应用多重链表，即每一个结点有多个指针域，其中每个指针指向一颗子树的根结点。
计划一 ：
依照树中最大度来调配指针域的个数
例如：一个数最多有 3 个子树，其余的数都不够或者等于 3 个子树时，就设置指针域为 3
如果每个树之间的子树数量差距过大，那么这个办法效率就很低。空间节约很大。
计划二：
为了使得空间利用更加正当，咱们专门设置一个空间来存储该节点孩子的个数。
计划三：
把一个树的子树用一个链表串起来。
// 孩子结点
struct CTNode{
int child;
struct CTNode * next;
};
// 表头构造
struct CTBox{
Element data;
CTNode * firstChild;// 链表头，即长子.
};
struct CTree{CTBox nodes[MAX_TREE_SIZE];
int r , n;// 根的地位和结点数。};这个办法想晓得双亲的话须要遍历，效率低
孩子双亲表示法
依照上述计划三，为表头 CTBox 减少一个双亲地位的索引即可。
孩子兄弟表示法
任意一棵树，它的结点的第一个孩子如果存在就惟一的，它的右兄弟如果存在就是惟一的。所以，咱们设置两个指针，别离指向该结点的第一个孩子和此结点的右兄弟。
struct CSNode {
Element data;
struct CSNode * firstChild, * rightsib;
};其实这个表示法最大的益处就是能 把一颗任意的树转变成一颗二叉树
二叉树
二叉树的定义
一个树的集和中任意一颗子树都最多只有两个子树（左子树和右子树），子树非左即右。和有最多有两个子树的树不同。二叉树规定了孩子是左还是右，而一般的树对孩子是没有程序要求的（也就是说，二叉树只有一个左子树和只有一个右子树这是两个不同的二叉树，然而如果是一般的树那就是一样的树了。）
二叉树的性质
$$
性质 1：在二叉树的第 i 层至少有 2^{i-1} 个结点(i\ge 1)
$$
$$
性质 2：深度为 k 的二叉树至少有 2^{k}- 1 个结点(k\ge 1)
$$
$$
性质 3: 对于任意一颗二叉树 T，如果其终端节点数为 n_{0}, 度为 2 的结点数为 n_{2}, 则 n_{0} = n_{2}+1
$$
$$
性质 4: 具备 n 个结点的齐全二叉树的深度为 \left \lfloor long_{2}n \right \rfloor +1
$$
$$
\displaylines{性质 5: 如果对一颗有 n 个结点的齐全二叉树 (其深度为 \left \lfloor log_{2} \right \rfloor )+ 1 的结点按层序编号(从第 1 层到第 \left \lfloor log_{2} \right \rfloor 层, 从左到右), 对于任意结点 i(1\le i \le n) 有:
\\ \begin{cases}1. 如果 i = 1, 则结点 i 是二叉树的根，无双亲；如果 i > 1, 则其双亲是结点 \left \lfloor i/2 \right \rfloor
\\ 2. 如果 2i > n, 则结点 i 无左孩子(结点 i 为叶子结点)；否则其做孩子就是结点 2i
\\ 3. 如果 2i+1 > n。则结点 i 无右孩子；否则其右孩子是结点 2i+1 \end{cases}}
$$
二叉树的建设
树自身就是递归定义，所以建树的过程也是递归建设
#include <stdio.h>
#include <stdlib.h>
typedef struct BinNode{
char data;
struct BinNode * lchild, * rchild;
}BinNode, * BinTree;
void CreatBinTree(BinTree * T){
char ch;
scanf("%d",&ch);
if(ch == '#')
*T = NULL;
else{*T = (BinTree)malloc(sizeof(BinNode));
if(! *T)
printf("ERROR!");
(*T)->data = ch;
CreatBinTree(& (*T)->lchild);
CreatBinTree(& (*T)->rchild);
}
}
int main(){
BinTree * T;
printf("Ceeeeeeeeb!");
CreatBinTree(T);
return 0;
}
这样写尽管能够输出，但因为没有提醒，也没有遍历。所以，测试的时候肯定要留神根左右的程序。
Code
#include<stdio.h>
#include<iostream>
using namespace std;
struct btnode{
char data;
struct btnode *lchild,*rchild;
};
extern int level=0;
extern int count=0;
int depth(btnode*);
void create(btnode* &T)
{
char c;
scanf("%c",&c);
if(c=='/') // 若为 '/', 则该结点为空
return;
T=new btnode;
T->data=c;
T->lchild=NULL;
T->rchild=NULL;
create(T->lchild);
create(T->rchild);
}
void prior_order1(btnode* T)// 递归先序遍历二叉树
{if(T)
{
cout<<T->data<<" ";
prior_order1(T->lchild);
prior_order1(T->rchild);
}
}
void mid_order(btnode* T)// 递归中序遍历二叉树
{if(T)
{mid_order(T->lchild);
cout<<T->data<<" ";
mid_order(T->rchild);
}
}
void behind_bt(btnode*T)// 后续遍历二叉树
{if(T)
{behind_bt(T->lchild);
behind_bt(T->rchild);
cout<<T->data<<" ";
}
}
void prior_order(btnode* T)// 先序输入二叉树，并且同时输入每个节点对应的位数
{
int count=1;
if(T==NULL)
return;
printf("(%c,%d)",T->data,count++);
if(T->lchild)
printf("(%c,%d)",T->lchild->data,count);
if(T->rchild)
printf("(%c,%d)",T->rchild->data,count);
}
void numbers_of_node(btnode* T,int &count)// 计算二叉树中结点个数，赋值给 count
{if(T)
{
++count;
numbers_of_node(T->lchild,count);
numbers_of_node(T->rchild,count);
}
}
int depth(btnode* T)// 求二叉树的深度, 规定根节点所在档次为 0 层
{
int leftlen,rightlen;
if(T==NULL)
return 0;
else
{leftlen=depth(T->lchild)+1;
rightlen=depth(T->rchild)+1;
}
if(leftlen>rightlen)
return leftlen;
return rightlen;
}
void leaf(btnode* T,int &count)// 求叶子节点个数
{if(T)
{if(T->lchild==NULL&&T->rchild==NULL)
count=count+1;
leaf(T->lchild,count);
leaf(T->rchild,count);
}
}
int main()
{
btnode *T=new btnode;
T=NULL;
int num1,node;
num1=node=0;
create(T);
leaf(T,num1);//num1 保留叶子结点个数
numbers_of_node(T,node);//node 保留结点个数
cout<<"先序序列输入后果为";
prior_order1(T); cout<<'\n';
cout<<"中序序列输入后果为";
mid_order(T); cout<<'\n';
cout<<"后序序列输入后果为";
behind_bt(T); cout<<'\n';
cout<<"叶子结点个数为"<<num1<<endl;
cout<<"二叉树结点个数为"<< node<<endl;
cout<<"二叉树深度为"<<depth(T);
return 0;
}
二叉树的遍历
递归遍历
因为树是递归定义，所以其遍历也是能够递归表白的。
void PreOrderTraverse(BinTree T){if(T == NULL)
return ;
printf("%c", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}非递归遍历
然而如果树的数据量十分大的话，那么递归定义的遍历函数很可能会使你的程序宕机，所以咱们通过栈来手动模仿遍历。
中序遍历
https://blog.csdn.net/happyja…
- 遇到一个结点，就把它压栈，并去遍历它的左子树；
- 当左子树遍历完结后，从栈顶弹出这个结点并拜访它；
- 而后按其右指针再去中序遍历该结点的右子树。
void midOrder(BiTree pRoot)
{if (pRoot == NULL)
return;
BiTree p = pRoot;
stack<BiTree>s;
while (p != NULL || !s.empty())
{while (p!=NULL)
{s.push(p);
p = p->lchild;
}
if (!s.empty())
{p = s.top();
cout << p->data << " "; // 第二次遇见的时候输入
s.pop();
p = p->rchild;
}
}
}
后序遍历
https://blog.csdn.net/happyja…
第一种思路：对于任一结点 P，将其入栈，而后沿其左子树始终往下搜寻，直到搜寻到没有左孩子的结点，此时该结点呈现在栈顶，然而此时不能将其出栈并拜访，因而其右孩子还为被拜访。所以接下来依照雷同的规定对其右子树进行雷同的解决，当拜访完其右孩子时，该结点又呈现在栈顶，此时能够将其出栈并拜访。这样就 保障了正确的拜访程序。能够看出，在这个过程中，每个结点都两次呈现在栈顶，只有在第二次呈现在栈顶时，能力拜访它。因而须要多设置一个变量标识该结点是 否是第一次呈现在栈顶
// 思路 1：typedef struct Node
{
BiTree btnode;
bool isfirst;
}Node,*node;
void postOrder(BiTree pRoot)
{if (pRoot == NULL)
return;
stack<node>s;
BiTree p = pRoot;
node tmp;
while (p!=NULL || !s.empty())
{while (p != NULL) // 沿左子树始终往下搜寻，直至呈现没有左子树的结点
{node btn = (node)malloc(sizeof(Node));
btn->btnode = p;
btn->isfirst = true;
s.push(btn);
p = p->lchild;
}
if (!s.empty())
{tmp = s.top();
s.pop();
if (tmp->isfirst == true) // 第一次呈现在栈顶
{
tmp->isfirst = false;
s.push(tmp);
p = tmp->btnode->rchild;
}
else // 第二次呈现在栈顶
{
cout << tmp->btnode->data<<" ";
p = NULL;
}
}
}
}
// 思路 2：void postorder(BiTree pRoot)
{if (pRoot == NULL)
return;
stack<BiTree>s;
BiTree cur = pRoot, pre = NULL;
s.push(pRoot);
while (!s.empty())
{cur = s.top();
if ((cur->lchild == NULL&&cur->rchild == NULL) ||
((pre == cur->lchild || pre == cur->rchild) && pre != NULL))
{
cout << cur->data << " ";
s.pop();
pre = cur;
}
else
{if (cur->rchild != NULL)
s.push(cur->rchild);
if (cur->lchild != NULL)
s.push(cur->lchild);
}
}
}
C 语言 code
// 这里是应用 C 语言，首先本人先手动写了栈。如果是 C ++ 能够应用 STL 中的 stack
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR -1
typedef char TElemType;
typedef int Status;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
typedef BiTNode * StackElemType;
typedef struct LinkNode // 栈的节点
{
StackElemType data ;
LinkNode * next ;
} LinkNode,*LiStack;
typedef BiTNode * QueueElemType ; // 定义队列蕴含的数据类型
typedef struct QNode // 定义队列节点
{
QueueElemType data ;
struct QNode * next ;
} QNode,*QueuePtr;
typedef struct
{
QueuePtr fronts;
QueuePtr rears;
} LinkQueue;
Status creatBiTree(BiTree &T);
void Visit(char ch,int level);
void PreOrderTraverse(BiTree T,int level);
void InOrderTraverse(BiTree T,int level);
void PostOrderTraverse(BiTree T,int level);
Status InitStack(LiStack &S);
void Push(LiStack &S, StackElemType data);
void Pop(LiStack & S, StackElemType &data);
int StackEmpty(LiStack &S);
int GetTop(LiStack &S, StackElemType & data);
Status InitQueue(LinkQueue &Q);
Status EnQueue(LinkQueue &Q, QueueElemType data);
Status DeQueue(LinkQueue &Q, QueueElemType & data);
int QueueEmpty(LinkQueue Q);
void PreOrderTraverse_Nonrecursion(BiTree T);
void InOrderTraverse_Nonrecursion(BiTree T);
void PostOrderTraverse_Nonrecursion(BiTree T);
/*********************************************************************/
/***************************** 栈的办法 ********************************/
// 栈的函数定义
Status InitStack(LiStack &S)
{S = (LinkNode *)malloc(sizeof(LinkNode)) ;
if(NULL == S)
{printf("内存不足，不能调配栈！\n") ;
exit(0) ;
}
S->next = NULL ;
}
void Push(LiStack &S, StackElemType data)
{
LiStack q ;
q = (LinkNode *)malloc(sizeof(LinkNode)) ;
if(NULL == q)
{printf("内存不足，不能调配栈！\n") ;
exit(0) ;
}
/*
插入程序相当于头插法.
*/
q->data = data ;
q->next = S->next ;
S->next = q ;
}
void Pop(LiStack & S, StackElemType &data)
{
LiStack q;
if(NULL == S->next)
{printf("栈为空，无返回值！\n") ;
}
q = S->next ;
data = q->data ;
S->next = q->next ;
free(q) ;
}
int StackEmpty(LiStack &S)
{if(NULL == S->next)
{return(1) ;
}
return(0) ;
}
int GetTop(LiStack &S, StackElemType & data)
{if(NULL != S->next)
{
data = S->next->data ;
return(1) ;
}
else
{
//data = NULL ;
return(0) ;
}
}
/*********************************************************************/
/***************************** 队列的办法 ******************************/
// 队列函数的定义
Status InitQueue(LinkQueue &Q)
{Q.fronts = Q.rears = (QNode *)malloc(sizeof(QNode)) ;
if(NULL == Q.fronts)
{printf("内存不足！\n") ;
return ERROR;
}
Q.fronts->next = NULL;
}
Status EnQueue(LinkQueue &Q, QueueElemType data)
{
QueuePtr q ;
q = (QNode*)malloc(sizeof(QNode));
if(NULL == q)
{printf("内存不足！\n") ;
return ERROR;
}
// 结构 q
q->data = data ;
q->next = NULL;
q->next = Q.rears->next ;
Q.rears = q ;
return OK;
}
Status DeQueue(LinkQueue &Q, QueueElemType & data)
{
QueuePtr p ;
if(Q.fronts == Q.rears)
{printf("队列为空！\n") ;
return ERROR ;
}
p = Q.fronts->next ;
data = p->data ;
Q.fronts->next = p->next ;
if(Q.rears == p)
Q.rears = Q.fronts ;
free(p);
return OK;
}
int QueueEmpty(LinkQueue Q)
{if(Q.fronts == Q.rears)
return(1) ;
else
return(0) ;
}
/*********************************************************************/
/*
先序创立二叉树
*/
Status creatBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if('@' == ch)
{T = NULL;}
else
{
// 申请失败
if(!(T = (BiTNode*)malloc(sizeof(BiTNode))))
return ERROR;
T->data = ch;
creatBiTree(T->lchild);
creatBiTree(T->rchild);
}
return OK;
}
void VisitF(char ch)
{printf("%c",ch);
}
void Visit(char ch,int level)
{printf("%c 位于第 %d 层 \n",ch,level);
}
/*
先序遍历二叉树
*/
void PreOrderTraverse(BiTree T,int level)
{if( T)
{VisitF(T->data);
PreOrderTraverse(T->lchild,++level);
PreOrderTraverse(T->rchild,++level);
}
}
void PreOrderTraverse_Nonrecursion(BiTree T)
{
LiStack S ;
BiTree p ;
S = NULL ;
p = T ;
InitStack(S) ;
if(NULL == p)
{printf("树为空！\n") ;
return ;
}
while(p || !StackEmpty(S))
{if(p)
{Push(S, p) ;
VisitF(p->data);
p = p->lchild ;
}
else
{Pop(S, p) ;
p = p->rchild ;
}
}
free(S) ;
}
/*
中序遍历二叉树
*/
void InOrderTraverse(BiTree T)
{if( T)
{InOrderTraverse(T->lchild);
VisitF(T->data);
InOrderTraverse(T->rchild);
}
}
void InOrderTraverse_Nonrecursion(BiTree T)
{
LiStack S ;
BiTree p ;
S = NULL ;
p = T ;
InitStack(S) ;
if(NULL == p)
{printf("树为空！\n") ;
return ;
}
while(p || !StackEmpty(S))
{if(p)
{Push(S, p) ;
p = p->lchild ;
}
else
{Pop(S, p) ;
VisitF(p->data);
p = p->rchild ;
}
}
free(S) ;
}
/*
后续遍历二叉树
*/
void PostOrderTraverse(BiTree T)
{if( T)
{PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
VisitF(T->data);
}
}
void PostOrderTraverse_Nonrecursion(BiTree T)
{
LiStack S ;
BiTree cur, pre ;
S = NULL ;
InitStack(S) ;
if(NULL == T)
{printf("树为空！\n") ;
return ;
}
pre = NULL ;
cur = NULL ;
Push(S,T) ;
while(!StackEmpty(S))
{
cur = NULL ;
GetTop(S,cur) ;
if((cur->lchild == NULL && cur->rchild == NULL) || (pre != NULL && (pre == cur->lchild ||pre == cur->rchild)))
{VisitF(cur->data);
pre = cur ;
Pop(S,cur) ;
}
else
{if(cur->rchild != NULL)
{Push(S,cur->rchild) ;
}
if(cur->lchild != NULL)
{Push(S,cur->lchild) ;
}
}
}
free(S) ;
}
int main()
{
int level = 1;
BiTree T = NULL;
creatBiTree(T);
printf("先序遍历二叉树，每个结点在第几行 \n");
PreOrderTraverse(T,level);
printf("\n\n");
printf("先序遍历二叉树, 非递归算法 \n");
PreOrderTraverse_Nonrecursion(T);
printf("\n\n\n");
/***************************************************/
printf("中序遍历二叉树 \n");
InOrderTraverse(T);
printf("\n\n");
printf("中序遍历二叉树, 非递归算法 \n");
InOrderTraverse_Nonrecursion(T);
printf("\n\n\n");
/***************************************************/
printf("后序遍历二叉树 \n");
PostOrderTraverse(T);
printf("\n\n");
printf("后序遍历二叉树, 非递归算法 \n");
PostOrderTraverse_Nonrecursion(T);
printf("\n\n\n");
return 0;
}C++Code
#include<iostream>
#include<stdlib.h>
#include<stack>
using namespace std;
#define len 15 // 定义一个长度
typedef int ElemType;
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
typedef struct Node
{
BiTree btnode;
bool isfirst;
}Node,*node;
// 向下遍历，找到节点 s 应该插入的地位，节点有反复时，疏忽这个节点
void SearchTreeNode(BiTree &root, BiTree &s) // 留神：应用援用传递
{if (root == NULL)
return;
if (s->data > root->data)
{if (root->rchild == NULL)
{
root->rchild = s;
return;
}
SearchTreeNode(root->rchild, s);// s 值大于根节点值，未达到叶子节点，持续向右孩子遍历
}
else if (s->data < root->data)
{if (root->lchild == NULL)
{
root->lchild = s;
return;
}
SearchTreeNode(root->lchild, s);// s 值小于根节点值，未达到叶子节点，持续向左孩子遍历
}
}
// 插入一个节点，树为空，插入节点即为根节点，否则找适合的地位插入
void InsertNode(BiTree &tree, BiTree &s) // 留神：应用援用传递
{if (tree == NULL)
tree = s;
else
SearchTreeNode(tree, s);
}
// 二叉排序树创立，每次减少一个结点，插到现有的二叉树下来
void CreateOrderBinaryTree(BiTree &tree, int *a)
{for (int i = 0; i < len; i++)
{BiTree s = (BiTree)malloc(sizeof(BiTNode));
s->data = a[i];
s->lchild = NULL;
s->rchild = NULL;
InsertNode(tree, s);
}
}
// 前序遍历
void ProOrderTraverse(BiTree tree)
{if (tree == NULL)
return;
cout << tree->data << " ";
ProOrderTraverse(tree->lchild);
ProOrderTraverse(tree->rchild);
}
// 非递归前序遍历
void ProOrder(BiTree pRoot)
{if (pRoot == NULL)
return;
BiTree p = pRoot;
stack<BiTree>s;
while (p != NULL || !s.empty())
{while (p != NULL)
{s.push(p);
cout << p->data << " "; // 第一次遇见的时候输入
p = p->lchild;
}
if (!s.empty())
{p = s.top();
s.pop();
p = p->rchild;
}
}
}
// 中序遍历
void midOrderTraverse(BiTree tree)
{if (tree == NULL)
return;
midOrderTraverse(tree->lchild);
cout << tree->data << " ";
midOrderTraverse(tree->rchild);
}
// 非递归中序遍历
void midOrder(BiTree pRoot)
{if (pRoot == NULL)
return;
BiTree p = pRoot;
stack<BiTree>s;
while (p != NULL || !s.empty())
{while (p!=NULL)
{s.push(p);
p = p->lchild;
}
if (!s.empty())
{p = s.top();
cout << p->data << " "; // 第二次遇见的时候输入
s.pop();
p = p->rchild;
}
}
}
// 后序遍历
void postOrderTraverse(BiTree pRoot)
{if (pRoot == NULL)
return;
postOrderTraverse(pRoot->lchild);
postOrderTraverse(pRoot->rchild);
cout << pRoot->data<<" ";
}
// 非递归实现后续遍历
void postOrder(BiTree pRoot)
{if (pRoot == NULL)
return;
stack<node>s;
BiTree p = pRoot;
node tmp;
while (p!=NULL || !s.empty())
{while (p != NULL) // 沿左子树始终往下搜寻，直至呈现没有左子树的结点
{node btn = (node)malloc(sizeof(Node));
btn->btnode = p;
btn->isfirst = true;
s.push(btn);
p = p->lchild;
}
if (!s.empty())
{tmp = s.top();
s.pop();
if (tmp->isfirst == true) // 第一次呈现在栈顶
{
tmp->isfirst = false;
s.push(tmp);
p = tmp->btnode->rchild;
}
else // 第二次呈现在栈顶
{
cout << tmp->btnode->data<<" ";
p = NULL;
}
}
}
}
// 非递归实现后续遍历
void postorder(BiTree pRoot)
{if (pRoot == NULL)
return;
stack<BiTree>s;
BiTree cur = pRoot, pre = NULL;
s.push(pRoot);
while (!s.empty())
{cur = s.top();
if ((cur->lchild == NULL&&cur->rchild == NULL) ||
((pre == cur->lchild || pre == cur->rchild) && pre != NULL))
{
cout << cur->data << " ";
s.pop();
pre = cur;
}
else
{if (cur->rchild != NULL)
s.push(cur->rchild);
if (cur->lchild != NULL)
s.push(cur->lchild);
}
}
}
int main()
{int a[len] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93, 23, 27, 45, 21, 12};
BiTree tree = NULL;
// 创立一个二叉树，并中序遍历
CreateOrderBinaryTree(tree, a);
cout << "前序遍历" << endl;
ProOrderTraverse(tree);
cout << endl;
ProOrder(tree);
cout << endl<<endl;
cout << "中序遍历" << endl;
midOrderTraverse(tree);
cout << endl;
midOrder(tree);
cout << endl<<endl;
cout << "后序遍历" << endl;
postOrderTraverse(tree);
cout << endl;
postOrder(tree);
cout << endl;
postorder(tree);
cout << endl<<endl;
return 0;
}
线索二叉树
线索二叉树实际上是为了将一般二叉树中泛滥的空节点利用起来而进行的操作的后果。同时能够使得咱们二叉树更加灵便。
其原理是与抉择的遍历形式密不可分的。具体是在结点中减少新的线索地位，而线索位寄存指向前驱和后继的指针，而前驱和后继的抉择就与遍历形式相干。
typedef enum {Link, Thread} PointerTag;
//Link == 0：示意指向左右孩子的指针
//Thread == 1：示意指向前驱和后继的线索
typedef struct BinThrNode {
Element data;
struct BinThrNode * lchild, * rchild;
PointerTag LTag, RTag;
};线索化的过程就是在遍历过程中批改空指针的过程。
// 中序遍历线索化
BinThrTree pre;// 全局变量，始终指向刚刚拜访过的结点
void InThreading(BinThrTree p){if(p){InThreading(p->lchild);// 递归左子树线索化
if(!p->lchild){// 没有左孩子
p->LTag = Thread;// 前驱线索
p->lchild = pre;// 左孩子指针指向前驱
}
if(!pre->rchild){
pre->RTag = Thread;
pre->rchild = p;// 前驱右孩子指针指向后继
}
pre = p;
InThreading(p->rchild);// 递归右孩子线索化
}
}
// 其实只是将打印的操作换成了对应的线索化的操作而已。if(!p->lchild) 示意如果某结点的左指针域为空，因为前驱结点刚刚曾经拜访过，赋值给 pre，所以能够将 pre 赋值给 p ->lchild, 并批改 p ->LTag = Thread (也就是定义为 1)以实现前驱结点的线索化。
后继此时并没有被拜访到，因而只能对它的前驱结点 pre 的右指针 rchild 做判断，if(!pre->rchild) 示意为空，则 p 就是 pre 的后继，于是 pre->rchild = p，并设置 pre->RTag = Thread;，实现后续的线索化。
线索化之后的遍历就如同双向链表一样。
// 线索二叉树中序遍历伪代码
Status InOrderTraverse_Thr(BinTree T){
BinThrTree p;
p = T->lchild;
while(p != T){while(p->LTag == Link)
p = p->lchild;
printf("%c",p->data);
while(p->RTag == Thread && p->rchild != T){
p = p->rchild;
printf("%c",p->data);
}
p = p->rchild;
}
return OK;
}
森林
二叉树和森林的转换
https://www.cnblogs.com/wangw…
树转换为二叉树
（1）加线。在所有兄弟结点之间加一条连线。
（2）去线。树中的每个结点，只保留它与第一个孩子结点的连线，删除它与其它孩子结点之间的连线。
（3）档次调整。以树的根节点为轴心，将整棵树顺时针旋转肯定角度，使之构造层次分明。（留神第一个孩子是结点的左孩子，兄弟转换过去的孩子是结点的右孩子）
森林转换为二叉树
（1）把每棵树转换为二叉树。
（2）第一棵二叉树不动，从第二棵二叉树开始，顺次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。
二叉树转换为树
是树转换为二叉树的逆过程。
（1）加线。若某结点 X 的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点 X 的孩子。将结点 X 与这些右孩子结点用线连接起来。
（2）去线。删除原二叉树中所有结点与其右孩子结点的连线。
（3）档次调整。
二叉树转换为森林
如果一棵二叉树的根节点有右孩子，则这棵二叉树可能转换为森林，否则将转换为一棵树。
（1）从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看拆散后的二叉树，若其根节点的右孩子存在，则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。
（2）将每棵拆散后的二叉树转换为树。
并查集
https://www.jianshu.com/p/fc1…
根本构造
咱们能够应用树这种数据结构来示意汇合，不同的树就是不同的汇合，并查集中蕴含了多棵树，示意并查集中不同的子集，树的汇合是 森林，所以并查集属于森林。
若汇合 S ={0, 1, 2, 3, 4, 5, 6}，最后每一个元素都是一棵树。
图 1
对于 Union 操作，咱们只须要将两棵树合并，例如合并 0、1、2 失去 S1={0, 1, 2}, 合并 3 和 4 失去 S2={3, 4}
图 2
对于 Find 操作，咱们只须要返回该元素所在树的根节点。所以，如果咱们想要比拟判断 1 和 2 是否在一个汇合，只须要通过 Find(1)和 Find(2)返回各自的根节点比拟是否相等便可。已知树中的一个节点，找到其根节点的工夫复杂度为 O(D)，D 为节点的深度。
咱们能够应用数组来示意树，数组下标示意树的一个节点，该下表所对应的值示意树的父节点。例如P[i] 示意元素 i 的父节点。对于图 2 中的汇合，咱们能够存储在上面的数组中（第二行为数组下标）
| 0 | 0 | 0 | 3 | 3 | 5 | 6 |
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
对于树的根节点，咱们规定其元素值为其自身（即父节点为本人）。
合并
咱们应用一个 parent 数组存储树，先实现未经优化的版本。
对于 Find 操作，代码非常简单
int find(int x)
{return parent[x] == x ? x : find(parent[x]);
}该代码比拟元素 x 的父节点 parent[x]是否等于 x 本身，如果是便阐明找到了根节点（根节点的父节点是本身），间接返回；否则，把 x 的父节点 parent[x]传入 find，直到找到根节点。
查问
void to_union(int x1, int x2)
{int p1 = find(x1);
int p2 = find(x2);
parent[p1] = p2;
}传入两个元素，别离找到根节点，使根节点 p1 的父节点为 p2，行将 p1 为根节点的这棵树合并到 p2 为根节点的树上。
残缺 Code
#include <vector>
class DisjSet
{
private:
std::vector<int> parent;
public:
DisjSet(int max_size) : parent(std::vector<int>(max_size))
{
// 初始化每一个元素的根节点都为本身
for (int i = 0; i < max_size; ++i)
parent[i] = i;
}
int find(int x)
{return parent[x] == x ? x : find(parent[x]);
}
void to_union(int x1, int x2)
{parent[find(x1)] = find(x2);
}
// 判断两个元素是否属于同一个汇合
bool is_same(int e1, int e2)
{return find(e1) == find(e2);
}
};下面的实现，能够看出每一次 Find 操作的工夫复杂度为O(H)，H 为树的高度，因为咱们没有对树做非凡解决，所以树的一直合并可能会使树重大不均衡，最坏状况每个节点都只有一个子节点，如下图 3（第一个点为根节点）
图 3
此时 Find 操作的工夫复杂度为O(n)，这显然不是咱们想要的。上面引入两个优化的办法。
Code 优化
办法一：
“ 按秩合并 ”。实际上就是在合并两棵树时，将高度较小的树合并到高度较大的树上。这里咱们应用“秩”(rank)代替高度，秩示意高度的上界，通常状况咱们令只有一个节点的树的秩为 0，严格来说，rank + 1 才是高度的上界；两棵秩别离为 r1、r2 的树合并，如果秩不相等，咱们将秩小的树合并到秩大的树上，这样就能保障新树秩不大于原来的任意一棵树。如果 r1 与 r2 相等，两棵树任意合并，并令新树的秩为 r1 + 1。
办法二：
“门路压缩”。在执行 Find 的过程中，将门路上的所有节点都间接连贯到根节点上。
图 4
同时应用这两种办法的均匀工夫复杂度为
$$
O(\alpha (n) )
$$
$$
\alpha (n) 是 n = f(x)=A(x,x)的反函数，A(x,x)是阿克曼函数
$$
A(x,x)增长率十分之高，所以在 n 十分大的时候，α(n)仍然小于 5。上面是采纳 ” 按秩合并 ” 与“门路压缩”两中优化算法的实现。
Code(优化版)
#include <vector>
class DisjSet
{
private:
std::vector<int> parent;
std::vector<int> rank; // 秩
public:
DisjSet(int max_size) : parent(std::vector<int>(max_size)),
rank(std::vector<int>(max_size, 0))
{for (int i = 0; i < max_size; ++i)
parent[i] = i;
}
int find(int x)
{return x == parent[x] ? x : (parent[x] = find(parent[x]));
}
void to_union(int x1, int x2)
{int f1 = find(x1);
int f2 = find(x2);
if (rank[f1] > rank[f2])
parent[f2] = f1;
else
{parent[f1] = f2;
if (rank[f1] == rank[f2])
++rank[f2];
}
}
bool is_same(int e1, int e2)
{return find(e1) == find(e2);
}
};
总结
https://blog.csdn.net/zjy_cod…
1) 初始化: 初始的时候每个结点各自为一个汇合,father[i]示意结点 i 的父亲结点, 如果 father[i]=i, 咱们认为这个结点是以后汇合根结点。
void init() {for (int i = 1; i <= n; ++i) {father[i] = i;
}
}2) 查找: 查找结点所在汇合的根结点, 结点 x 的根结点必然也是其父亲结点的根结点。
int get(int x) {if (father[x] == x) { // x 结点就是根结点
return x;
}
return get(father[x]); // 返回父结点的根结点
}3) 合并: 将两个元素所在的汇合合并在一起, 通常来说, 合并之前先判断两个元素是否属于同一汇合。
void merge(int x, int y) {x = get(x);
y = get(y);
if (x != y) { // 不在同一个汇合
father[y] = x;
}
}下面三个操作是并查集罕用的操作
后面的并查集的复杂度实际上在有些极其状况会很慢。比方树的构造正好是一条链，那么最坏状况下，每次查问的复杂度达到了 O(n)。这并不是咱们冀望的后果。门路压缩的思维是，咱们只关怀每个结点的父结点，而并不太关怀树的真正的构造。
这样咱们在一次查问的时候，能够把查问门路上的所有结点的 father[i]都赋值成为根结点。只须要在咱们之前的查问函数下面进行很小的改变
int get(int x) {if (father[x] == x) { // x 结点就是根结点
return x;
}
return father[x] = get(father[x]); // 返回父结点的根结点，并另以后结点父结点间接为根结点
}门路压缩在理论利用中效率很高, 其一次查问复杂度平摊下来能够认为是一个常数。并且在理论利用中, 咱们根本都用带门路压缩的并查集。
带权并查集
所谓带权并查集，是指结点存有权值信息的并查集。并查集以森林的模式存在，而结点的权值，大多是记录该结点与先人关系的信息。比方权值能够记录该结点到根节点的间隔。
例题
在排队过程中，初始时，一人一列。一共有如下两种操作。
合并：令其中的两个队列 A，B 合并，也就是将队列 A 排在队列 B 的前面。
查问：询问某个人在其所在队列中排在第几位。
例题解析
咱们无妨设 size[]为汇合中的元素个数，dist[]为元素到队首的间隔，合并时，dist[A.root]须要加上 size[B.root] (每个元素到队首的间隔应该是到根门路上所有点的 dist[]求和)，size[B.root]须要加上 size[A.root] (每个元素所在汇合的元素个数只需查问该汇合中根的 size[x.root])。
1)初始化：
void init() {for(int i = 1; i <= n; i++) {father[i] = i, dist[i] = 0, size[i] = 1;
}
}2)查找：查找元素所在的汇合，即根节点。
int get(int x) {if(father[x] == x) {return x;}
int y = father[x];
father[x] = get(y);
dist[x] += dist[y]; // x 到根结点的间隔等于 x 到之前父亲结点间隔加上之前父亲结点到根结点的间隔
return father[x];
}门路压缩的时候，不须要思考 size[]，但 dist[] 须要更新成到整个汇合根的间隔。
3)合并
将两个元素所在的汇合合并为一个汇合。
通常来说，合并之前，应先判断两个元素是否属于同一个汇合，这可用下面的“查找”操作实现。
void merge(int a, int b) {a = get(a);
b = get(b);
if(a != b) { // 判断两个元素是否属于同一汇合
father[a] = b;
dist[a] = size[b];
size[b] += size[a];
}
}通过小小的改变，咱们就能够查问并查集这一森林中，每个元素到先人的相干信息。
例题
在社交的过程中，通过敌人，也能意识新的敌人。在某个敌人关系图中，假设 A 和 B 是敌人，B 和 C 是敌人，那么 A 和 C 也会成为敌人。即，咱们规定敌人的敌人也是敌人。
当初，已知若干对敌人关系，询问某两个人是不是敌人。
请编写一个程序来解决这个问题吧。
输出格局
第一行：三个整数 n,m,p(n≤5000,m≤5000,p≤5000)别离示意有 n 集体，m 个敌人关系，询问 p 对敌人关系。
接下来 m 行：每行两个数 Ai,Bi1≤Ai,Bi≤N，示意 Ai 和 Bi 具备敌人关系。
接下来 p 行：每行两个数，询问两人是否为敌人。
输入格局
输入共 p 行，每行一个 Yes 或 No。示意第 i 个询问的答案为是否敌人。
样例输出
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
样例输入
Yes
Yes
No
解题：
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int mark[5005],fa[5005];
int get(int x)
{if(fa[x]==x)
return x;
return fa[x]=get(fa[x]);
}
int main()
{
int n,m,p;
cin>>n>>m>>p;
int a,b;
memset(mark,0,sizeof(mark));
for(int i=1;i<=n;i++)
fa[i]=i;
while(m--)
{
cin>>a>>b;
a=get(a);
b=get(b);
if(a!=b)
{fa[a]=b;
}
}
for(int i=1;i<=p;i++)
{
cin>>a>>b;
a=get(a);
b=get(b);
if(a==b)
mark[i]=1;
}
for(int i=1;i<=p;i++)
{if(mark[i])
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}树的利用
哈夫曼树
https://www.cnblogs.com/smile…
相干概念
1、叶子结点的权值（weight）是对叶子结点赋予的一个有意义的数值量。
2、设二叉树有 n 个带权值的叶子结点，从根节点到各个叶子结点的门路长度与相应叶子结点权值的乘积之和叫做 二叉树的带权门路长度。
3、给定一组具备确定权值的叶子结点，能够结构出不同的二叉树，将其中带权门路长度最小的二叉树称为 哈夫曼树。
哈夫曼算法根本思维
(1) 以权值别离为 W1,W2．．．Wn的n各结点，形成 n 棵二叉树 T1,T2,．．．Tn 并组成森林 F ={T1,T2,．．．Tn}, 其中每棵二叉树 Ti 仅有一个权值为 Wi 的根结点；
(2) 在 F 中选取两棵根结点权值最小的树作为左右子树结构一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值 = 左右孩子权值之和，叶结点的权值 = Wi）；
(3) 从 F 中删除这两棵二叉树，同时将新二叉树退出到 F 中;
(4) 反复 (2)、(3) 直到 F 中只含一棵二叉树为止，这棵二叉树就是 Huffman 树。
哈夫曼算法的存储构造
思考到对于有 n 个叶子结点的哈夫曼树有 2n- 1 个结点，并且进行 n - 1 次合并操作，为了便于选取根节点权值最小的二叉树以及合并操作，设置一个数组 haftree[2n-1], 保留哈夫曼树中的各个结点的信息，数组元素的结点构造如下图所示：
| weight | lchild | rchild | parent |
|---|---|---|---|
哈夫曼树的结点构造
其中，weight 保留结点权值；
lchild 保留该节点的左孩子在数组中的下标；
rchild 保留该节点的右孩子在数组中的下标；
parent 保留该节点的双亲孩子在数组中的下标。
能够用 C ++ 语言中的构造体类型定义上述结点，如下：
/ 哈夫曼树的结点构造
struct element
{
int weight; // 权值域
int lchild, rchild, parent; // 该结点的左、右、双亲结点在数组中的下标
};哈夫曼编码 C ++ 实现
为了断定一个结点是否曾经退出哈夫曼树中，可通过 parent 域的值来确定。初始时 parent 的值为 -1，当某结点退出到树中时，该节点 parent 域的值为其双亲结点在数组中的下标。
结构哈夫曼树时，首先将 n 个权值的叶子结点寄存到数组 haftree 的前 n 个重量中，而后一直将两棵子树合并为一棵子树，并将新子树的根节点程序寄存到数组 haftree 的前 n 个重量的前面。
哈夫曼算法用伪代码形容为：
1、数组 haftree 初始化，所有数组元素的双亲、左右孩子都置为 -1；2、数组 haftree 的前 n 个元素的权值置给定权值；3、进行 n - 1 次合并
3.1 在二叉树汇合中选取两个权值最小的根节点，其下标别离为 i1，i2；3.2 将二叉树 i1、i2 合并为一棵新的二叉树 k。Code
#include<iostream>
#include <iomanip>// 这个头文件是申明一些“流操作符”的
// 比拟罕用的有:setw(int);// 设置显示宽度，left//right// 设置左右对齐。setprecision(int);// 设置浮点数的精确度。using namespace std;
// 哈夫曼树的结点构造
struct element
{
int weight; // 权值域
int lchild, rchild, parent; // 该结点的左、右、双亲结点在数组中的下标
};
// 选取权值最小的两个结点
void selectMin(element a[],int n, int &s1, int &s2)
{for (int i = 0; i < n; i++)
{if (a[i].parent == -1)// 初始化 s1,s1 的双亲为 -1
{
s1 = i;
break;
}
}
for (int i = 0; i < n; i++)// s1 为权值最小的下标
{if (a[i].parent == -1 && a[s1].weight > a[i].weight)
s1 = i;
}
for (int j = 0; j < n; j++)
{if (a[j].parent == -1&&j!=s1)// 初始化 s2,s2 的双亲为 -1
{
s2 = j;
break;
}
}
for (int j = 0; j < n; j++)// s2 为另一个权值最小的结点
{if (a[j].parent == -1 && a[s2].weight > a[j].weight&&j != s1)
s2 = j;
}
}
// 哈夫曼算法
// n 个叶子结点的权值保留在数组 w 中
void HuffmanTree(element huftree[], int w[], int n)
{for (int i = 0; i < 2*n-1; i++) // 初始化，所有结点均没有双亲和孩子
{huftree[i].parent = -1;
huftree[i].lchild = -1;
huftree[i].rchild = -1;
}
for (int i = 0; i < n; i++) // 结构只有根节点的 n 棵二叉树
{huftree[i].weight = w[i];
}
for (int k = n; k < 2 * n - 1; k++) // n- 1 次合并
{
int i1, i2;
selectMin(huftree, k, i1, i2); // 查找权值最小的俩个根节点，下标为 i1,i2
// 将 i1，i2 合并，且 i1 和 i2 的双亲为 k
huftree[i1].parent = k;
huftree[i2].parent = k;
huftree[k].lchild = i1;
huftree[k].rchild = i2;
huftree[k].weight = huftree[i1].weight + huftree[i2].weight;
}
} // 打印哈夫曼树
void print(element hT[],int n)
{
cout << "index weight parent lChild rChild" << endl;
cout << left; // 左对齐输入
for (int i = 0; i < n; ++i)
{cout << setw(5) << i << " ";
cout << setw(6) << hT[i].weight << " ";
cout << setw(6) << hT[i].parent << " ";
cout << setw(6) << hT[i].lchild << " ";
cout << setw(6) << hT[i].rchild << endl;
}
}
int main()
{int x[] = {5,29,7,8,14,23,3,11}; // 权值汇合
element *hufftree=new element[2*8-1]; // 动态创建数组
HuffmanTree(hufftree, x, 8);
print(hufftree,15);
system("pause");
return 0;
}二叉均衡树（AVL 树）
AVL 简介
AVL 树种的任意节点的左右子树的高度差的绝对值最大为 1，其本质是带了 均衡性能的二叉搜寻树。
二叉搜寻树在数据极其状况下会进化成单链表，工夫复杂度也会进化成 O(n)。而 AVL 树定义了旋转操作，在均衡因子大于 2 时，通过旋转来调整树的构造，来从新满足均衡因子小于 2，确保在查找、插入和删除在均匀和最坏状况下都是 O(logn)。
AVL 旋转
AVL 旋转是 AVL 树最外围的局部，须要重点把握。在了解 AVL 旋转之前先晓得以下几个概念：
- AVL 树节点的插入总是在叶子节点；
- AVL 树在插入节点之前是满足平衡条件的；
- 插入新节点后有可能满足平衡条件也可能不满足；
- 当不满足平衡条件时须要对新的树进行旋转。
旋转之前首先须要找到插入节点向上第一个不均衡的节点(记为 A），新插入节点只能在 A 的的左子树的左子树、左子树的右子树、右子树的左子树、右子树的右子树上，对应四种不同的旋转形式。
如果在 AVL 树中进行插入或删除节点后，可能导致 AVL 树失去平衡。这种失去平衡的能够概括为 4 种姿势：LL(左左)，LR(左右)，RR(右右)和 RL(右左)。上面给出它们的示意图：
上图中的 4 棵树都是 ” 失去平衡的 AVL 树 ”，从左往右的状况顺次是：LL、LR、RL、RR。除了下面的状况之外，还有其它的失去平衡的 AVL 树，如下图：
下面的两张图都是为了便于了解，而列举的对于 ” 失去平衡的 AVL 树 ” 的例子。总的来说，AVL 树失去平衡时的状况肯定是 LL、LR、RL、RR 这 4 种之一，它们都由各自的定义：
(1) LL：LeftLeft，也称为 ” 左左 ”。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致 ” 根的左子树的高度 ” 比 ” 根的右子树的高度 ” 大 2，导致 AVL 树失去了均衡。
例如，在下面 LL 状况中，因为 ” 根节点 (8) 的左子树 (4) 的左子树 (2) 还有非空子节点 ”，而 ” 根节点 (8) 的右子树 (12) 没有子节点 ”；导致 ” 根节点 (8) 的左子树 (4) 高度 ” 比 ” 根节点 (8) 的右子树(12)” 高 2。
(2) LR：LeftRight，也称为 ” 左右 ”。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致 ” 根的左子树的高度 ” 比 ” 根的右子树的高度 ” 大 2，导致 AVL 树失去了均衡。
例如，在下面 LR 状况中，因为 ” 根节点 (8) 的左子树 (4) 的左子树 (6) 还有非空子节点 ”，而 ” 根节点 (8) 的右子树 (12) 没有子节点 ”；导致 ” 根节点 (8) 的左子树 (4) 高度 ” 比 ” 根节点 (8) 的右子树(12)” 高 2。
(3) RL：RightLeft，称为 ” 右左 ”。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致 ” 根的右子树的高度 ” 比 ” 根的左子树的高度 ” 大 2，导致 AVL 树失去了均衡。
例如，在下面 RL 状况中，因为 ” 根节点 (8) 的右子树 (12) 的左子树 (10) 还有非空子节点 ”，而 ” 根节点 (8) 的左子树 (4) 没有子节点 ”；导致 ” 根节点 (8) 的右子树 (12) 高度 ” 比 ” 根节点 (8) 的左子树(4)” 高 2。
(4) RR：RightRight，称为 ” 右右 ”。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致 ” 根的右子树的高度 ” 比 ” 根的左子树的高度 ” 大 2，导致 AVL 树失去了均衡。
例如，在下面 RR 状况中，因为 ” 根节点 (8) 的右子树 (12) 的右子树 (14) 还有非空子节点 ”，而 ” 根节点 (8) 的左子树 (4) 没有子节点 ”；导致 ” 根节点 (8) 的右子树 (12) 高度 ” 比 ” 根节点 (8) 的左子树(4)” 高 2。
后面说过，如果在 AVL 树中进行插入或删除节点后，可能导致 AVL 树失去平衡。AVL 失去平衡之后，能够通过旋转使其复原均衡，上面别离介绍 ”LL(左左)，LR(左右)，RR(右右)和 RL(右左)” 这 4 种状况对应的旋转办法。
3.1 LL 旋转
/*
LL
在左左旋转中，一共波及到三代节点，咱们把爷爷节点命名为 K2，K2 的左儿子命名为 K1。问题呈现的起因是 K1 的左儿子减少了一个节点导致均衡树失衡
解决思路：让 K1 成为爷爷节点，K2 成为 K1 的右儿子，并且将 K1 的右儿子接为 K2 的左儿子，而后返回爷爷节点 K1 取代原来 K2 的地位
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::LL_Rotation(AVLTreeNode<T>* k2){
AVLTreeNode<T>* k1;
k1 = k2->Left;
k2->Left = k1->Right;
k1->Right = k2;
k2->height = max(height(k2->Left), height(k2->Right)) + 1;
k1->height = max(height(k1->Left), k2->height) + 1;
return k1;
}3.2RR 旋转
/*
RR
在右右旋转中，一共波及到三代节点，咱们把爷爷节点命名为 K1，K1 的右儿子命名为 K2。问题呈现的起因是 K2 的右儿子减少了一个节点导致均衡树失衡
解决思路：让 K2 成为爷爷节点，K1 成为 K2 的左儿子，并且将 K2 的左儿子接为 K1 的右儿子，而后返回爷爷节点 K2 取代原来 K1 的地位
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::RR_Rotation(AVLTreeNode<T>* k1){
AVLTreeNode<T>* k2;
k2 = k1->Right;
k1->Right = k2->Left;
k2->Left = k1;
k1->height = max(height(k1->Left), height(k1->Right)) + 1;
k2->height = max(height(k2->Right), k1->height) + 1;
return k2;
}3.3LR 旋转
/*
LR
在左右旋转中，一共波及到四代节点，咱们把做基本的节点成为 K3（曾爷爷节点），K3 的左儿子称为 K1（爷爷节点），K1 的右儿子称为 K2
问题呈现的起因时 K2 的右儿子减少了一个节点之后导致树的失衡
解决思路：因为波及到四代节点，所以须要两次旋转，首先对 K1，K2 进行一次右右旋转 =》K2 成为爷爷节点（即 K3 的左儿子），k2 本来的左儿子称为 K1 的右儿子，K1 成为 K2 的左儿子
接下来对 K2，K3 进行一次左左旋转 =》K2 称为曾爷爷节点，K2 本来的右儿子成为 K3 的左儿子，K3 成为 K2 的右儿子
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::LR_Rotation(AVLTreeNode<T>* k3){k3->Left = RR_Rotation(k3->Left);
return LL_Rotation(k3);
}3.4RL 旋转
/*
RL
在右左旋转中，一共波及到四代节点，咱们把做基本的节点成为 K1（曾爷爷节点），K1 的右儿子称为 K3（爷爷节点），K3 的左儿子称为 K2
问题呈现的起因时 K2 的左儿子减少了一个节点之后导致树的失衡
解决思路：因为波及到四代节点，所以须要两次旋转，首先对 K2，K3 进行一次左左旋转 =》K2 成为爷爷节点（即 K1 的右儿子），k2 本来的右儿子称为 K3 的左儿子，K3 成为 K2 的右儿子
接下来对 K1，K2 进行一次右右旋转 =》K2 称为曾爷爷节点，K2 本来的左儿子成为 K1 的右儿子，K1 成为 K2 的左儿子
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::RL_Rotation(AVLTreeNode<T>* k1){k1->Right = LL_Rotation(k1->Right);
return RR_Rotation(k1);
}4. 插入节点
template <class T>
AVLTreeNode<T>* AVLTree<T>::add(AVLTreeNode<T>* &tree, T data){if (tree == NULL) {tree = new AVLTreeNode<T>(data, NULL, NULL);
}
else if (data < tree->data){
// 将新退出的节点插入左子树
tree->Left = add(tree->Left, data);
// 查看退出新的结点之后树是否失去平衡
if (height(tree->Left) - height(tree->Right) == 2)
{if (data < tree->Left->data)
tree = LL_Rotation(tree);// 左左，新退出之后左儿子的左儿子深了
else
tree = LR_Rotation(tree);// 左右，新退出之后左儿子的右儿子深了
}
}
// 将新退出的节点插入右子树
else if (data > tree->data) {tree->Right = add(tree->Right, data);
// 查看退出新的结点之后树是否失去平衡
if (height(tree->Right) - height(tree->Left) == 2)
{if (data > tree->Right->data)
tree = RR_Rotation(tree);// 右右，新退出之后右儿子的右儿子深了
else
tree = RL_Rotation(tree);// 右左，新退出之后右儿子的左儿子深了
}
}
else // 该节点曾经在树中
{cout << "该节点曾经存在树中" << endl;}
// 更新更前以后节点的高度
tree->height = max(height(tree->Left), height(tree->Right)) + 1;
return tree;
}
template <class T>
void AVLTree<T>::add(T data){add(Root, data);
}Code
#include <cstdio>
#include <iostream>
using namespace std;
template <class T>
struct AVLTreeNode{
T data;
int height;
AVLTreeNode* Left;
AVLTreeNode* Right;
AVLTreeNode(T v,AVLTreeNode* l,AVLTreeNode* r):data(v),height(0),Left(l),Right(r){}};
/*
AVL 树的定义
为了爱护类内数据，仿照网络实例把函数写成了内接口和外接口的模式。还有模板类。感觉代码有点繁冗，写完之后调式的时候感觉不太棘手，当前写程序要留神内接口和外接口的模式
*/
template <class T>
class AVLTree{
private:
AVLTreeNode<T>* Root;
public:
AVLTree():Root(NULL){}
void add(T data);
int height();
int max(int a, int b);
private:
AVLTreeNode<T>* add(AVLTreeNode<T>* &tree, T data);
int height(AVLTreeNode<T>* tree);
AVLTreeNode<T>* LL_Rotation(AVLTreeNode<T>* k2);
AVLTreeNode<T>* RR_Rotation(AVLTreeNode<T>* k1);
AVLTreeNode<T>* LR_Rotation(AVLTreeNode<T>* k3);
AVLTreeNode<T>* RL_Rotation(AVLTreeNode<T>* k1);
};
/*
高度
作用：获取树的高度
*/
template <class T>
int AVLTree<T>::height(AVLTreeNode<T>* tree)
{if (tree != NULL)
return tree->height;
return 0;
}
template <class T>
int AVLTree<T>::height() {return height(Root);
}
/* 模板类革新比拟两个值的大小 */
template <class T>
int AVLTree<T>::max(int a, int b) {return a>b ? a : b;}
/*
LL
在左左旋转中，一共波及到三代节点，咱们把爷爷节点命名为 K2，K2 的左儿子命名为 K1。问题呈现的起因是 K1 的左儿子减少了一个节点导致均衡树失衡
解决思路：让 K1 成为爷爷节点，K2 成为 K1 的右儿子，并且将 K1 的右儿子接为 K2 的左儿子，而后返回爷爷节点 K1 取代原来 K2 的地位
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::LL_Rotation(AVLTreeNode<T>* k2){
AVLTreeNode<T>* k1;
k1 = k2->Left;
k2->Left = k1->Right;
k1->Right = k2;
k2->height = max(height(k2->Left), height(k2->Right)) + 1;
k1->height = max(height(k1->Left), k2->height) + 1;
return k1;
}
/*
RR
在右右旋转中，一共波及到三代节点，咱们把爷爷节点命名为 K1，K1 的右儿子命名为 K2。问题呈现的起因是 K2 的右儿子减少了一个节点导致均衡树失衡
解决思路：让 K2 成为爷爷节点，K1 成为 K2 的左儿子，并且将 K2 的左儿子接为 K1 的右儿子，而后返回爷爷节点 K2 取代原来 K1 的地位
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::RR_Rotation(AVLTreeNode<T>* k1){
AVLTreeNode<T>* k2;
k2 = k1->Right;
k1->Right = k2->Left;
k2->Left = k1;
k1->height = max(height(k1->Left), height(k1->Right)) + 1;
k2->height = max(height(k2->Right), k1->height) + 1;
return k2;
}
/*
LR
在左右旋转中，一共波及到四代节点，咱们把做基本的节点成为 K3（曾爷爷节点），K3 的左儿子称为 K1（爷爷节点），K1 的右儿子称为 K2
问题呈现的起因时 K2 的右儿子减少了一个节点之后导致树的失衡
解决思路：因为波及到四代节点，所以须要两次旋转，首先对 K1，K2 进行一次右右旋转 =》K2 成为爷爷节点（即 K3 的左儿子），k2 本来的左儿子称为 K1 的右儿子，K1 成为 K2 的左儿子
接下来对 K2，K3 进行一次左左旋转 =》K2 称为曾爷爷节点，K2 本来的右儿子成为 K3 的左儿子，K3 成为 K2 的右儿子
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::LR_Rotation(AVLTreeNode<T>* k3){k3->Left = RR_Rotation(k3->Left);
return LL_Rotation(k3);
}
/*
RL
在右左旋转中，一共波及到四代节点，咱们把做基本的节点成为 K1（曾爷爷节点），K1 的右儿子称为 K3（爷爷节点），K3 的左儿子称为 K2
问题呈现的起因时 K2 的左儿子减少了一个节点之后导致树的失衡
解决思路：因为波及到四代节点，所以须要两次旋转，首先对 K2，K3 进行一次左左旋转 =》K2 成为爷爷节点（即 K1 的右儿子），k2 本来的右儿子称为 K3 的左儿子，K3 成为 K2 的右儿子
接下来对 K1，K2 进行一次右右旋转 =》K2 称为曾爷爷节点，K2 本来的左儿子成为 K1 的右儿子，K1 成为 K2 的左儿子
*/
template <class T>
AVLTreeNode<T>* AVLTree<T>::RL_Rotation(AVLTreeNode<T>* k1){k1->Right = LL_Rotation(k1->Right);
return RR_Rotation(k1);
}
template <class T>
AVLTreeNode<T>* AVLTree<T>::add(AVLTreeNode<T>* &tree, T data){if (tree == NULL) {tree = new AVLTreeNode<T>(data, NULL, NULL);
}
else if (data < tree->data){
// 将新退出的节点插入左子树
tree->Left = add(tree->Left, data);
// 查看退出新的结点之后树是否失去平衡
if (height(tree->Left) - height(tree->Right) == 2)
{if (data < tree->Left->data)
tree = LL_Rotation(tree);// 左左，新退出之后左儿子的左儿子深了
else
tree = LR_Rotation(tree);// 左右，新退出之后左儿子的右儿子深了
}
}
// 将新退出的节点插入右子树
else if (data > tree->data) {tree->Right = add(tree->Right, data);
// 查看退出新的结点之后树是否失去平衡
if (height(tree->Right) - height(tree->Left) == 2)
{if (data > tree->Right->data)
tree = RR_Rotation(tree);// 右右，新退出之后右儿子的右儿子深了
else
tree = RL_Rotation(tree);// 右左，新退出之后右儿子的左儿子深了
}
}
else // 该节点曾经在树中
{cout << "该节点曾经存在树中" << endl;}
// 更新更前以后节点的高度
tree->height = max(height(tree->Left), height(tree->Right)) + 1;
return tree;
}
template <class T>
void AVLTree<T>::add(T data){add(Root, data);
}
int main(){
int num;
AVLTree<int>* tree=new AVLTree<int>();
cin>>num;
for(int i=0;i<num;i++){
int x;
cin>>x;
tree->add(x);
}
cout<<"高度为："<<tree->height()<<endl;
return 0;
}
/*
实例输出：16
3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9
实例输入：5
*/B 树和 B + 树
https://blog.csdn.net/qq_2594…
https://blog.csdn.net/z_ryan/…
B 树
如果后面的 2 - 3 树与 2 -3- 4 树了解了，B 树也就了解了，因为 2 - 3 树就是 3 阶的 B 树，2-3- 4 树就是 4 阶的 B 树。所以，对于 B 树的性质，依据 2 -3- 4 树都能够推导进去了，即，
一颗 m 阶的 B 树（B-tree）定义如下：
（1）每个节点最多有 m-1 个 key；
（2）根节点至多有 1 个 key；
（3）非根节点至多有 Math.ceil(m/2)-1 个 key；
（4）每个节点中的 key 都依照从小到大的顺序排列，每个 key 的左子树中的所有 key 都小于它，而右子树中的所有 key 都大于它；
（5）所有叶子节点都位于同一层，即根节点到每个叶子节点的长度都雷同。
在后面的章节我就曾经说过，呈现多路查找树的起因，是因为多路查找树的数据结构，用在内存读取外存的场景下，能够缩小磁盘的 IO 次数，因为在高阶的状况下，树不必很高就能够标识很大的数据量了，那这个怎么算的呢？
打个比方，以 2 - 3 树为例，树高为 3 的时候，一棵 2 - 3 树能够保留 2 +3×2+3x2x2=20 个 key，若当 B 树的阶数达到 1001 阶，即一个节点能够放 1000 个 key，而后树高还是 3，即 1000+1000×1001+1000x1001x1000，零头不算了，即至多能够放 10 个亿的 key，此时咱们只有让根节点读取到内存中，把子节点及子孙节点长久化到硬盘中，那么在这棵树上，寻找某一个 key 至少须要 2 次硬盘的读取即可。
而对于 B 树节点的插入，能够类比 2 -3- 4 树，即，若节点插入节点的 key 还未“饱满”，则直接插入，若节点插入节点的 key 已“饱满”，则插入节点之后决裂，再以决裂之后的父节点看作向下层插入的节点调整，直至满足该 m 阶的 B 树。如下，为 5 阶 B 树插入节点的动态图，
对于 B 树节点的删除，也一样类比 2 -3- 4 树，如下，
（1）若删除非叶子节点，找后继节点替换之，将问题转化为删除叶子节点；
（2）若删除叶子节点，且叶子节点的 key 数大于定义中的最小值（根节点至多有 1 个 key，非根节点至多有 Math.ceil(m/2)-1 个 key），则间接删除即可，无需调整，
（3）若删除叶子节点，且叶子节点的 key 数刚好满足定义中的最小值，即刚好“脱贫”，则将节点删除，此时树必定须要调整，即：
a. 若删除节点的相邻兄弟节点的 key 数“富裕”（节点的 key 大于定义中的最小值），则父节点的 1 个 key 下移与待删除的节点合并，相邻兄弟节点的 1 个 key 上移与父节点合并，实现调整；
b. 若删除节点的相邻兄弟节点的 key 数刚好“脱贫”（节点的 key 刚好满足定义的最小值），则父节点的 1 个 key 下移与待删除的节点及相邻兄弟节点，三者进行合并成一个节点，若下移 1 个 key 后的父节点的 key 数刚好“脱贫”或“富裕”，则调整实现，反之，即此时父节点曾经陷入“贫困”，则将父节点看作以后待删除的节点，反复 a，b 的判断。
特色
一个 m 阶的 B 树具备如下几个 特色：B 树中所有结点的孩子结点最大值称为 B 树的阶，通常用 m 示意。一个结点有 k 个孩子时，必有 k - 1 个关键字能力将子树中所有关键字划分为 k 个子集。
1. 根结点至多有两个子女。
2. 每个两头节点都蕴含 k - 1 个元素和 k 个孩子，其中 ceil（m/2）≤ k ≤ m
3. 每一个叶子节点都蕴含 k - 1 个元素，其中 ceil（m/2）≤ k ≤ m
4. 所有的叶子结点都位于同一层。
5. 每个节点中的元素从小到大排列，节点当中 k - 1 个元素正好是 k 个孩子蕴含的元素的值域划分
6. 每个结点的构造为：（n，A0，K1，A1，K2，A2，…，Kn，An）其中，Ki(1≤i≤n)为关键字，且 Ki<Ki+1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且 Ai 所指子树所有结点中的关键字均小于 Ki+1。
n 为结点中关键字的个数，满足 ceil(m/2)-1≤n≤m-1。
示例：三阶 B 树（理论中节点中元素很多）
查问
以上图为例：若查问的数值为5：
第一次磁盘IO：在内存中定位（与 17、35 比拟），比 17 小，左子树；
第二次磁盘IO：在内存中定位（与8、12 比拟），比8小，左子树；
第三次磁盘IO：在内存中定位（与 3、5 比拟），找到 5，终止。
整个过程中，咱们能够看出：比拟的次数并不比二叉查找树少，尤其适当某一节点中的数据很多时，然而磁盘 IO 的次数却是大大减少。比拟是在内存中进行的，相比于磁盘 IO 的速度，比拟的耗时简直能够疏忽。所以当树的高度足够低的话，就能够极大的提高效率。相比之下，节点中的元素多点也没关系，仅仅是多了几次内存交互而已，只有不超过磁盘页的大小即可。
插入
对高度为k的 m 阶 B 树，新结点个别是插在叶子层。通过检索能够确定关键码应插入的结点地位。而后分两种状况探讨：
1、若该结点中关键码个数小于 m -1，则直接插入即可。
2、若该结点中关键码个数等于 m -1，则将引起结点的决裂。以两头关键码为界将结点一分为二，产生一个新结点，并把两头关键码插入到父结点 (k- 1 层) 中
反复上述工作，最坏状况始终决裂到根结点，建设一个新的根结点，整个 B 树减少一层。
例如：在上面的 B 树中插入 key：4
第一步：检索 key 插入的节点地位如上图所示，在 3,5 之间；
第二步：判断节点中的关键码个数：
节点 3，5 曾经是两元素节点，无奈再减少。父亲节点 2，6 也是两元素节点，也无奈再减少。根节点 9 是单元素节点，能够降级为两元素节点。；
第三步：结点决裂：
拆分节点 3，5 与节点 2，6，让根节点 9 降级为两元素节点 4，9。节点 6 独立为根节点的第二个孩子。
最终后果如下图：尽管插入比拟麻烦，然而这也能确保B树是一个自均衡的树
删除
B树中关键字的删除比插入更简单，在这里，只介绍其中的一种办法：
在 B 树上删除关键字 k 的过程分两步实现：
（1）找出该关键字所在的结点。而后依据 k 所在结点是否为叶子结点有不同的解决办法。
（2）若该结点为非叶结点，且被删关键字为该结点中第 i 个关键字 key[i]，则可从指针 son[i]所指的子树中
找出最小关键字 Y，代替 key[i] 的地位，而后在叶结点中删去 Y。
因而，把在非叶结点删除关键字 k 的问题就变成了删除叶子结点中的关键字的问题了。
在 B - 树叶结点上删除一个关键字的办法：
首先将要删除的关键字 k 间接从该叶子结点中删除。而后依据不同状况别离作相应的解决，共有三种可能状况：
（1）如果被删关键字所在结点的原关键字个数 n >=ceil(m/2)，阐明删去该关键字后该结点仍满足 B 树的定义。
这种状况最为简略，只需从该结点中间接删去关键字即可。（2）如果被删关键字所在结点的关键字个数 n 等于 ceil(m/2)-1，阐明删去该关键字后该结点将不满足 B 树的定义，
须要调整。调整过程为：
如果其左右兄弟结点中有“多余”的关键字, 即与该结点相邻的右（左）兄弟结点中的关键字数目大于
ceil(m/2)-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上
移关键字的关键字下移至被删关键字所在结点中。
如果左右兄弟结点中没有“多余”的关键字，即与该结点相邻的右（左）兄弟结点中的关键字数目均等于
ceil(m/2)-1。这种状况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中宰割二者
的关键字合并成一个结点, 即在删除关键字后，该结点中残余的关键字加指针，加上双亲结点中的关键字 Ki 一起，
合并到 Ai（是双亲结点指向该删除关键字结点的左（右）兄弟结点的指针）所指的兄弟结点中去。如果因而使双亲
结点中关键字个数小于 ceil(m/2)-1，则对此双亲结点做同样解决。以致于可能直到对根结点做这样的解决而使
整个树缩小一层。
总之，设所删关键字为非终端结点中的 Ki，则能够指针 Ai 所指子树中的最小关键字 Y 代替 Ki，而后在相应结点中删除 Y。对任意关键字的删除都能够转化为对最上层关键字的删除。
上面举一个简略的例子：删除元素 11.
第一步：判断该元素是否在叶子结点上。
该元素在叶子节点上，能够间接删去，然而删除之后，两头节点 12 只有一个孩子，不合乎 B 树的定义：每个两头节点都蕴含 k 个孩子，（其中 ceil（m/2）<= k <= m）所以须要调整；
第二步：判断其左右兄弟结点中有“多余”的关键字，即：原关键字个数 n >=ceil(m/2) – 1；
显然结点 11 的右兄弟节点中有多余的关键字。那么可将右兄弟结点中最小关键字上移至双亲结点。而将双亲结点中小于该上移关键字的关键字下移至被删关键字所在结点中即可
留神
①、B 树次要用于文件系统以及局部数据库索引，例如：MongoDB。而大部分关系数据库则应用 B + 树做索引，例如：mysql 数据库；
②、从查找效率思考个别要求 B 树的阶数 m >= 3;
③、B- 树上算法的执行工夫次要由读、写磁盘的次数来决定，故一次 I / O 操作应读写尽可能多的信息。因而 B - 树的结点规模个别以一个磁盘页为单位。一个结点蕴含的关键字及其孩子个数取决于磁盘页的大小。
B+ 树
尽管 B 树这种数据结构，利用在内外存交互，能够极大的缩小磁盘的 IO 次数，但还是有些小瑕疵，如下 5 阶的 B 树图，若我须要读取 key 为“66”与“73”的数据，则此时从根节点“50”开始，“66”大于“50”，找右孩子，即到“60 70 120”的节点，再锁定到“64 66”的节点，找到 key 为“66”的数据，而后读“73”的数据，再从新从根开始往下寻找 key 为“73”的数据，如果须要查问的数据量一多，性能就很蹩脚。还有一点，就是 B 树的每个节点都蕴含 key 及其 value 数据，这样的话，我每次读取叶子节点的数据时，在通过门路上的非叶子节点也会被读出，但实际上这部分数据我是不须要的，这样又占用了没有必要的内存空间。
所以，B+ 树在 B 树的根底上做了优化，它与 B 树的差别在于：
（1）有 k 个子节点的节点必然有 k 个 key；
（2）非叶子节点仅具备索引作用，跟记录无关的信息均寄存在叶子节点中。
（3）树的所有叶子节点形成一个有序链表，能够依照 key 排序的秩序遍历全副记录。
即，B 和 B + 树的区别在于，B+ 树的非叶子结点只蕴含导航信息，不蕴含理论的值，所有的叶子结点和相连的节点应用链表相连，便于区间查找和遍历。
B+ 树的长处在于：
1. 因为 B + 树在外部节点上不蕴含数据信息，因而在内存页中可能寄存更多的 key。
数据寄存的更加严密，具备更好的空间局部性。
因而拜访叶子节点上关联的数据也具备更好的缓存命中率。
2.B+ 树的叶子结点都是相链的，因而对整棵树的便当只须要一次线性遍历叶子结点即可。
而且因为数据顺序排列并且相连，所以便于区间查找和搜寻。
而 B 树则须要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有 B + 树好。然而 B 树也有长处，其长处在于：
因为 B 树的每一个节点都蕴含 key 和 value，因而常常拜访的元素可能离根节点更近，因而拜访也更迅速。
特色
一个 m 阶的 B + 树具备如下几个特色：
1. 有 k 个子树的两头节点蕴含有 k 个元素（B 树中是 k - 1 个元素），每个元素不保留数据，只用来索引，所有数据
都保留在叶子节点。2. 所有的叶子结点中蕴含了全副元素的信息，及指向含这些元素记录的指针，且叶子结点自身依关键字的大小
自小而大程序链接。3. 所有的两头节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
上面是一棵 3 阶的 B + 树：
B+ 树通常有两个指针，一个指向根结点，另一个指向关键字最小的叶子结点。因些，对于 B + 树进行查找两种运算：一种是从最小关键字起程序查找，另一种是从根结点开始，进行随机查找。
查找
B+ 树的劣势在于查找效率上，上面咱们做一具体阐明：
首先，B+树的查找和B树一样，相似于二叉查找树。起始于根节点，自顶向下遍历树，抉择其拆散值在要查找值的任意一边的子指针。在节点外部典型的应用是二分查找来确定这个地位。
（1）、不同的是，B+树两头节点没有卫星数据（索引元素所指向的数据记录），只有索引，而B树每个结点中的每个关键字都有卫星数据；这就意味着同样的大小的磁盘页能够包容更多节点元素，在雷同的数据量下，B+树更加“矮胖”，IO操作更少
B 树的卫星数据：
fcnlhbg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)
B+ 树的卫星数据：
须要补充的是，在数据库的汇集索引（Clustered Index）中，叶子节点间接蕴含卫星数据。在非汇集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。
（2）、其次，因为卫星数据的不同，导致查问过程也不同；B树的查找只需找到匹配元素即可，最好状况下查找到根节点，最坏状况下查找到叶子结点，所说性能很不稳固，而B+树每次必须查找到叶子结点，性能稳固
（3）、在范畴查问方面，B+ 树的劣势更加显著
B 树的范畴查找须要一直依赖中序遍历。首先二分查找到范畴上限，在一直通过中序遍历，晓得查找到范畴的下限即可。整个过程比拟耗时。
而 B + 树的范畴查找则简略了许多。首先通过二分查找，找到范畴上限，而后同过叶子结点的链表程序遍历，直至找到下限即可，整个过程简略许多，效率也比拟高。
例如：同样查找范畴[3-11]，两者的查问过程如下：
B 树的查找过程：
B+ 树的查找过程：
插入
B+ 树的插入与 B 树的插入过程相似。不同的是 B + 树在叶结点上进行，如果叶结点中的关键码个数超过 m，就必须决裂成关键码数目大致相同的两个结点，并保障下层结点中有这两个结点的最大关键码。
删除
B+ 树中的关键码在叶结点层删除后，其在下层的复本能够保留，作为一个”合成关键码”存在，如果因为删除而造成结点中关键码数小于 ceil(m/2)，其处理过程与 B - 树的解决一样。在此，我就不多做介绍了。
B+ 树 Code
不肯定能跑，仅供参考
#ifndef BPLUS_NODE
#define BPLUS_NODE
#define NULL 0
enum NODE_TYPE{INTERNAL, LEAF}; // 结点类型：内结点、叶子结点
enum SIBLING_DIRECTION{LEFT, RIGHT}; // 兄弟结点方向：左兄弟结点、右兄弟结点
typedef float KeyType; // 键类型
typedef int DataType; // 值类型
const int ORDER = 7; // B+ 树的阶（非根内结点的最小子树个数）const int MINNUM_KEY = ORDER-1; // 最小键值个数
const int MAXNUM_KEY = 2*ORDER-1; // 最大键值个数
const int MINNUM_CHILD = MINNUM_KEY+1; // 最小子树个数
const int MAXNUM_CHILD = MAXNUM_KEY+1; // 最大子树个数
const int MINNUM_LEAF = MINNUM_KEY; // 最小叶子结点键值个数
const int MAXNUM_LEAF = MAXNUM_KEY; // 最大叶子结点键值个数
// 结点基类
class CNode{
public:
CNode();
virtual ~CNode();
NODE_TYPE getType() const {return m_Type;}
void setType(NODE_TYPE type){m_Type = type;}
int getKeyNum() const {return m_KeyNum;}
void setKeyNum(int n){m_KeyNum = n;}
KeyType getKeyValue(int i) const {return m_KeyValues[i];}
void setKeyValue(int i, KeyType key){m_KeyValues[i] = key;}
int getKeyIndex(KeyType key)const; // 找到键值在结点中存储的下标
// 纯虚函数，定义接口
virtual void removeKey(int keyIndex, int childIndex)=0; // 从结点中移除键值
virtual void split(CNode* parentNode, int childIndex)=0; // 决裂结点
virtual void mergeChild(CNode* parentNode, CNode* childNode, int keyIndex)=0; // 合并结点
virtual void clear()=0; // 清空结点，同时会清空结点所蕴含的子树结点
virtual void borrowFrom(CNode* destNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d)=0; // 从兄弟结点中借一个键值
virtual int getChildIndex(KeyType key, int keyIndex)const=0; // 依据键值获取孩子结点指针下标
protected:
NODE_TYPE m_Type;
int m_KeyNum;
KeyType m_KeyValues[MAXNUM_KEY];
};
// 内结点
class CInternalNode : public CNode{
public:
CInternalNode();
virtual ~CInternalNode();
CNode* getChild(int i) const {return m_Childs[i];}
void setChild(int i, CNode* child){m_Childs[i] = child;}
void insert(int keyIndex, int childIndex, KeyType key, CNode* childNode);
virtual void split(CNode* parentNode, int childIndex);
virtual void mergeChild(CNode* parentNode, CNode* childNode, int keyIndex);
virtual void removeKey(int keyIndex, int childIndex);
virtual void clear();
virtual void borrowFrom(CNode* destNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d);
virtual int getChildIndex(KeyType key, int keyIndex)const;
private:
CNode* m_Childs[MAXNUM_CHILD];
};
// 叶子结点
class CLeafNode : public CNode{
public:
CLeafNode();
virtual ~CLeafNode();
CLeafNode* getLeftSibling() const {return m_LeftSibling;}
void setLeftSibling(CLeafNode* node){m_LeftSibling = node;}
CLeafNode* getRightSibling() const {return m_RightSibling;}
void setRightSibling(CLeafNode* node){m_RightSibling = node;}
DataType getData(int i) const {return m_Datas[i];}
void setData(int i, const DataType& data){m_Datas[i] = data;}
void insert(KeyType key, const DataType& data);
virtual void split(CNode* parentNode, int childIndex);
virtual void mergeChild(CNode* parentNode, CNode* childNode, int keyIndex);
virtual void removeKey(int keyIndex, int childIndex);
virtual void clear();
virtual void borrowFrom(CNode* destNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d);
virtual int getChildIndex(KeyType key, int keyIndex)const;
private:
CLeafNode* m_LeftSibling;
CLeafNode* m_RightSibling;
DataType m_Datas[MAXNUM_LEAF];
};
#endif#include "BPlus_node.h"
// CNode
CNode::CNode(){setType(LEAF);
setKeyNum(0);
}
CNode::~CNode(){setKeyNum(0);
}
int CNode::getKeyIndex(KeyType key)const
{
int left = 0;
int right = getKeyNum()-1;
int current;
while(left!=right)
{current = (left+right)/2;
KeyType currentKey = getKeyValue(current);
if (key>currentKey)
{left = current+1;}
else
{right = current;}
}
return left;
}
// CInternalNode
CInternalNode::CInternalNode():CNode(){setType(INTERNAL);
}
CInternalNode::~CInternalNode(){}
void CInternalNode::clear()
{for (int i=0; i<=m_KeyNum; ++i)
{m_Childs[i]->clear();
delete m_Childs[i];
m_Childs[i] = NULL;
}
}
void CInternalNode::split(CNode* parentNode, int childIndex)
{CInternalNode* newNode = new CInternalNode();// 决裂后的右节点
newNode->setKeyNum(MINNUM_KEY);
int i;
for (i=0; i<MINNUM_KEY; ++i)// 拷贝关键字的值
{newNode->setKeyValue(i, m_KeyValues[i+MINNUM_CHILD]);
}
for (i=0; i<MINNUM_CHILD; ++i) // 拷贝孩子节点指针
{newNode->setChild(i, m_Childs[i+MINNUM_CHILD]);
}
setKeyNum(MINNUM_KEY); // 更新左子树的关键字个数
((CInternalNode*)parentNode)->insert(childIndex, childIndex+1, m_KeyValues[MINNUM_KEY], newNode);
}
void CInternalNode::insert(int keyIndex, int childIndex, KeyType key, CNode* childNode){
int i;
for (i=getKeyNum(); i>keyIndex; --i)// 将父节点中的 childIndex 后的所有关键字的值和子树指针向后移一位
{setChild(i+1,m_Childs[i]);
setKeyValue(i,m_KeyValues[i-1]);
}
if (i==childIndex)
{setChild(i+1, m_Childs[i]);
}
setChild(childIndex, childNode);
setKeyValue(keyIndex, key);
setKeyNum(m_KeyNum+1);
}
void CInternalNode::mergeChild(CNode* parentNode, CNode* childNode, int keyIndex)
{
// 合并数据
insert(MINNUM_KEY, MINNUM_KEY+1, parentNode->getKeyValue(keyIndex), ((CInternalNode*)childNode)->getChild(0));
int i;
for (i=1; i<=childNode->getKeyNum(); ++i)
{insert(MINNUM_KEY+i, MINNUM_KEY+i+1, childNode->getKeyValue(i-1), ((CInternalNode*)childNode)->getChild(i));
}
// 父节点删除 index 的 key
parentNode->removeKey(keyIndex, keyIndex+1);
delete ((CInternalNode*)parentNode)->getChild(keyIndex+1);
}
void CInternalNode::removeKey(int keyIndex, int childIndex)
{for (int i=0; i<getKeyNum()-keyIndex-1; ++i)
{setKeyValue(keyIndex+i, getKeyValue(keyIndex+i+1));
setChild(childIndex+i, getChild(childIndex+i+1));
}
setKeyNum(getKeyNum()-1);
}
void CInternalNode::borrowFrom(CNode* siblingNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d)
{switch(d)
{
case LEFT: // 从左兄弟结点借
{insert(0, 0, parentNode->getKeyValue(keyIndex), ((CInternalNode*)siblingNode)->getChild(siblingNode->getKeyNum()));
parentNode->setKeyValue(keyIndex, siblingNode->getKeyValue(siblingNode->getKeyNum()-1));
siblingNode->removeKey(siblingNode->getKeyNum()-1, siblingNode->getKeyNum());
}
break;
case RIGHT: // 从右兄弟结点借
{insert(getKeyNum(), getKeyNum()+1, parentNode->getKeyValue(keyIndex), ((CInternalNode*)siblingNode)->getChild(0));
parentNode->setKeyValue(keyIndex, siblingNode->getKeyValue(0));
siblingNode->removeKey(0, 0);
}
break;
default:
break;
}
}
int CInternalNode::getChildIndex(KeyType key, int keyIndex)const
{if (key==getKeyValue(keyIndex))
{return keyIndex+1;}
else
{return keyIndex;}
}
// CLeafNode
CLeafNode::CLeafNode():CNode(){setType(LEAF);
setLeftSibling(NULL);
setRightSibling(NULL);
}
CLeafNode::~CLeafNode(){}
void CLeafNode::clear()
{for (int i=0; i<m_KeyNum; ++i)
{
// if type of m_Datas is pointer
//delete m_Datas[i];
//m_Datas[i] = NULL;
}
}
void CLeafNode::insert(KeyType key, const DataType& data)
{
int i;
for (i=m_KeyNum; i>=1 && m_KeyValues[i-1]>key; --i)
{setKeyValue(i, m_KeyValues[i-1]);
setData(i, m_Datas[i-1]);
}
setKeyValue(i, key);
setData(i, data);
setKeyNum(m_KeyNum+1);
}
void CLeafNode::split(CNode* parentNode, int childIndex)
{CLeafNode* newNode = new CLeafNode();// 决裂后的右节点
setKeyNum(MINNUM_LEAF);
newNode->setKeyNum(MINNUM_LEAF+1);
newNode->setRightSibling(getRightSibling());
setRightSibling(newNode);
newNode->setLeftSibling(this);
int i;
for (i=0; i<MINNUM_LEAF+1; ++i)// 拷贝关键字的值
{newNode->setKeyValue(i, m_KeyValues[i+MINNUM_LEAF]);
}
for (i=0; i<MINNUM_LEAF+1; ++i)// 拷贝数据
{newNode->setData(i, m_Datas[i+MINNUM_LEAF]);
}
((CInternalNode*)parentNode)->insert(childIndex, childIndex+1, m_KeyValues[MINNUM_LEAF], newNode);
}
void CLeafNode::mergeChild(CNode* parentNode, CNode* childNode, int keyIndex)
{
// 合并数据
for (int i=0; i<childNode->getKeyNum(); ++i)
{insert(childNode->getKeyValue(i), ((CLeafNode*)childNode)->getData(i));
}
setRightSibling(((CLeafNode*)childNode)->getRightSibling());
// 父节点删除 index 的 key，parentNode->removeKey(keyIndex, keyIndex+1);
}
void CLeafNode::removeKey(int keyIndex, int childIndex)
{for (int i=keyIndex; i<getKeyNum()-1; ++i)
{setKeyValue(i, getKeyValue(i+1));
setData(i, getData(i+1));
}
setKeyNum(getKeyNum()-1);
}
void CLeafNode::borrowFrom(CNode* siblingNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d)
{switch(d)
{
case LEFT: // 从左兄弟结点借
{insert(siblingNode->getKeyValue(siblingNode->getKeyNum()-1), ((CLeafNode*)siblingNode)->getData(siblingNode->getKeyNum()-1));
siblingNode->removeKey(siblingNode->getKeyNum()-1, siblingNode->getKeyNum()-1);
parentNode->setKeyValue(keyIndex, getKeyValue(0));
}
break;
case RIGHT: // 从右兄弟结点借
{insert(siblingNode->getKeyValue(0), ((CLeafNode*)siblingNode)->getData(0));
siblingNode->removeKey(0, 0);
parentNode->setKeyValue(keyIndex, siblingNode->getKeyValue(0));
}
break;
default:
break;
}
}
int CLeafNode::getChildIndex(KeyType key, int keyIndex)const
{return keyIndex;}#ifndef BPLUS_TREE_H
#define BPLUS_TREE_H
#include "BPlus_node.h"
#include <vector>
using namespace std;
enum COMPARE_OPERATOR{LT, LE, EQ, BE, BT, BETWEEN}; // 比拟操作符：<、<=、=、>=、>、<>
const int INVALID_INDEX = -1;
struct SelectResult
{
int keyIndex;
CLeafNode* targetNode;
};
class CBPlusTree{
public:
CBPlusTree();
~CBPlusTree();
bool insert(KeyType key, const DataType& data);
bool remove(KeyType key);
bool update(KeyType oldKey, KeyType newKey);
// 定值查问，compareOperator 能够是 LT(<)、LE(<=)、EQ(=)、BE(>=)、BT(>)
vector<DataType> select(KeyType compareKey, int compareOpeartor);
// 范畴查问，BETWEEN
vector<DataType> select(KeyType smallKey, KeyType largeKey);
bool search(KeyType key); // 查找是否存在
void clear(); // 清空
void print()const; // 打印树关键字
void printData()const; // 打印数据
private:
void recursive_insert(CNode* parentNode, KeyType key, const DataType& data);
void recursive_remove(CNode* parentNode, KeyType key);
void printInConcavo(CNode *pNode, int count)const;
bool recursive_search(CNode *pNode, KeyType key)const;
void changeKey(CNode *pNode, KeyType oldKey, KeyType newKey);
void search(KeyType key, SelectResult& result);
void recursive_search(CNode* pNode, KeyType key, SelectResult& result);
void remove(KeyType key, DataType& dataValue);
void recursive_remove(CNode* parentNode, KeyType key, DataType& dataValue);
private:
CNode* m_Root;
CLeafNode* m_DataHead;
KeyType m_MaxKey; // B+ 树中的最大键
};
#endif#include "BPlus_tree.h"
#include <iostream>
#include <algorithm>
using namespace std;
CBPlusTree::CBPlusTree(){
m_Root = NULL;
m_DataHead = NULL;
}
CBPlusTree::~CBPlusTree(){clear();
}
bool CBPlusTree::insert(KeyType key, const DataType& data){
// 是否曾经存在
if (search(key))
{return false;}
// 找到能够插入的叶子结点，否则创立新的叶子结点
if(m_Root==NULL)
{m_Root = new CLeafNode();
m_DataHead = (CLeafNode*)m_Root;
m_MaxKey = key;
}
if (m_Root->getKeyNum()>=MAXNUM_KEY) // 根结点已满，决裂
{CInternalNode* newNode = new CInternalNode(); // 创立新的根节点
newNode->setChild(0, m_Root);
m_Root->split(newNode, 0); // 叶子结点决裂
m_Root = newNode; // 更新根节点指针
}
if (key>m_MaxKey) // 更新最大键值
{m_MaxKey = key;}
recursive_insert(m_Root, key, data);
return true;
}
void CBPlusTree::recursive_insert(CNode* parentNode, KeyType key, const DataType& data)
{if (parentNode->getType()==LEAF) // 叶子结点，直接插入
{((CLeafNode*)parentNode)->insert(key, data);
}
else
{
// 找到子结点
int keyIndex = parentNode->getKeyIndex(key);
int childIndex= parentNode->getChildIndex(key, keyIndex); // 孩子结点指针索引
CNode* childNode = ((CInternalNode*)parentNode)->getChild(childIndex);
if (childNode->getKeyNum()>=MAXNUM_LEAF) // 子结点已满，需进行决裂
{childNode->split(parentNode, childIndex);
if (parentNode->getKeyValue(childIndex)<=key) // 确定指标子结点
{childNode = ((CInternalNode*)parentNode)->getChild(childIndex+1);
}
}
recursive_insert(childNode, key, data);
}
}
void CBPlusTree::clear()
{if (m_Root!=NULL)
{m_Root->clear();
delete m_Root;
m_Root = NULL;
m_DataHead = NULL;
}
}
bool CBPlusTree::search(KeyType key)
{return recursive_search(m_Root, key);
}
bool CBPlusTree::recursive_search(CNode *pNode, KeyType key)const
{if (pNode==NULL) // 检测节点指针是否为空，或该节点是否为叶子节点
{return false;}
else
{int keyIndex = pNode->getKeyIndex(key);
int childIndex = pNode->getChildIndex(key, keyIndex); // 孩子结点指针索引
if (keyIndex<pNode->getKeyNum() && key==pNode->getKeyValue(keyIndex))
{return true;}
else
{if (pNode->getType()==LEAF) // 查看该节点是否为叶子节点
{return false;}
else
{return recursive_search(((CInternalNode*)pNode)->getChild(childIndex), key);
}
}
}
}
void CBPlusTree::print()const
{printInConcavo(m_Root, 10);
}
void CBPlusTree::printInConcavo(CNode *pNode, int count) const{if (pNode!=NULL)
{
int i, j;
for (i=0; i<pNode->getKeyNum(); ++i)
{if (pNode->getType()!=LEAF)
{printInConcavo(((CInternalNode*)pNode)->getChild(i), count-2);
}
for (j=count; j>=0; --j)
{cout<<"-";}
cout<<pNode->getKeyValue(i)<<endl;
}
if (pNode->getType()!=LEAF)
{printInConcavo(((CInternalNode*)pNode)->getChild(i), count-2);
}
}
}
void CBPlusTree::printData()const
{
CLeafNode* itr = m_DataHead;
while(itr!=NULL)
{for (int i=0; i<itr->getKeyNum(); ++i)
{cout<<itr->getData(i)<<" ";
}
cout<<endl;
itr = itr->getRightSibling();}
}
bool CBPlusTree::remove(KeyType key)
{if (!search(key)) // 不存在
{return false;}
if (m_Root->getKeyNum()==1)// 非凡状况解决
{if (m_Root->getType()==LEAF)
{clear();
return true;
}
else
{CNode *pChild1 = ((CInternalNode*)m_Root)->getChild(0);
CNode *pChild2 = ((CInternalNode*)m_Root)->getChild(1);
if (pChild1->getKeyNum()==MINNUM_KEY && pChild2->getKeyNum()==MINNUM_KEY)
{pChild1->mergeChild(m_Root, pChild2, 0);
delete m_Root;
m_Root = pChild1;
}
}
}
recursive_remove(m_Root, key);
return true;
}
// parentNode 中蕴含的键值数 >MINNUM_KEY
void CBPlusTree::recursive_remove(CNode* parentNode, KeyType key)
{int keyIndex = parentNode->getKeyIndex(key);
int childIndex= parentNode->getChildIndex(key, keyIndex); // 孩子结点指针索引
if (parentNode->getType()==LEAF)// 找到指标叶子节点
{if (key==m_MaxKey&&keyIndex>0)
{m_MaxKey = parentNode->getKeyValue(keyIndex-1);
}
parentNode->removeKey(keyIndex, childIndex); // 间接删除
// 如果键值在外部结点中存在，也要相应的替换外部结点
if (childIndex==0 && m_Root->getType()!=LEAF && parentNode!=m_DataHead)
{changeKey(m_Root, key, parentNode->getKeyValue(0));
}
}
else // 内结点
{CNode *pChildNode = ((CInternalNode*)parentNode)->getChild(childIndex); // 蕴含 key 的子树根节点
if (pChildNode->getKeyNum()==MINNUM_KEY) // 蕴含关键字达到下限值，进行相干操作
{CNode *pLeft = childIndex>0 ? ((CInternalNode*)parentNode)->getChild(childIndex-1) : NULL; // 左兄弟节点
CNode *pRight = childIndex<parentNode->getKeyNum() ? ((CInternalNode*)parentNode)->getChild(childIndex+1) : NULL;// 右兄弟节点
// 先思考从兄弟结点中借
if (pLeft && pLeft->getKeyNum()>MINNUM_KEY)// 左兄弟结点可借
{pChildNode->borrowFrom(pLeft, parentNode, childIndex-1, LEFT);
}
else if (pRight && pRight->getKeyNum()>MINNUM_KEY)// 右兄弟结点可借
{pChildNode->borrowFrom(pRight, parentNode, childIndex, RIGHT);
}
// 左右兄弟节点都不可借，思考合并
else if (pLeft) // 与左兄弟合并
{pLeft->mergeChild(parentNode, pChildNode, childIndex-1);
pChildNode = pLeft;
}
else if (pRight) // 与右兄弟合并
{pChildNode->mergeChild(parentNode, pRight, childIndex);
}
}
recursive_remove(pChildNode, key);
}
}
void CBPlusTree::changeKey(CNode *pNode, KeyType oldKey, KeyType newKey)
{if (pNode!=NULL && pNode->getType()!=LEAF)
{int keyIndex = pNode->getKeyIndex(oldKey);
if (keyIndex<pNode->getKeyNum() && oldKey==pNode->getKeyValue(keyIndex)) // 找到
{pNode->setKeyValue(keyIndex, newKey);
}
else // 持续找
{changeKey(((CInternalNode*)pNode)->getChild(keyIndex), oldKey, newKey);
}
}
}
bool CBPlusTree::update(KeyType oldKey, KeyType newKey)
{if (search(newKey)) // 查看更新后的键是否曾经存在
{return false;}
else
{
int dataValue;
remove(oldKey, dataValue);
if (dataValue==INVALID_INDEX)
{return false;}
else
{return insert(newKey, dataValue);
}
}
}
void CBPlusTree::remove(KeyType key, DataType& dataValue)
{if (!search(key)) // 不存在
{
dataValue = INVALID_INDEX;
return;
}
if (m_Root->getKeyNum()==1)// 非凡状况解决
{if (m_Root->getType()==LEAF)
{dataValue = ((CLeafNode*)m_Root)->getData(0);
clear();
return;
}
else
{CNode *pChild1 = ((CInternalNode*)m_Root)->getChild(0);
CNode *pChild2 = ((CInternalNode*)m_Root)->getChild(1);
if (pChild1->getKeyNum()==MINNUM_KEY && pChild2->getKeyNum()==MINNUM_KEY)
{pChild1->mergeChild(m_Root, pChild2, 0);
delete m_Root;
m_Root = pChild1;
}
}
}
recursive_remove(m_Root, key, dataValue);
}
void CBPlusTree::recursive_remove(CNode* parentNode, KeyType key, DataType& dataValue)
{int keyIndex = parentNode->getKeyIndex(key);
int childIndex= parentNode->getChildIndex(key, keyIndex); // 孩子结点指针索引
if (parentNode->getType()==LEAF)// 找到指标叶子节点
{if (key==m_MaxKey&&keyIndex>0)
{m_MaxKey = parentNode->getKeyValue(keyIndex-1);
}
dataValue = ((CLeafNode*)parentNode)->getData(keyIndex);
parentNode->removeKey(keyIndex, childIndex); // 间接删除
// 如果键值在外部结点中存在，也要相应的替换外部结点
if (childIndex==0 && m_Root->getType()!=LEAF && parentNode!=m_DataHead)
{changeKey(m_Root, key, parentNode->getKeyValue(0));
}
}
else // 内结点
{CNode *pChildNode = ((CInternalNode*)parentNode)->getChild(childIndex); // 蕴含 key 的子树根节点
if (pChildNode->getKeyNum()==MINNUM_KEY) // 蕴含关键字达到下限值，进行相干操作
{CNode *pLeft = childIndex>0 ? ((CInternalNode*)parentNode)->getChild(childIndex-1) : NULL; // 左兄弟节点
CNode *pRight = childIndex<parentNode->getKeyNum() ? ((CInternalNode*)parentNode)->getChild(childIndex+1) : NULL;// 右兄弟节点
// 先思考从兄弟结点中借
if (pLeft && pLeft->getKeyNum()>MINNUM_KEY)// 左兄弟结点可借
{pChildNode->borrowFrom(pLeft, parentNode, childIndex-1, LEFT);
}
else if (pRight && pRight->getKeyNum()>MINNUM_KEY)// 右兄弟结点可借
{pChildNode->borrowFrom(pRight, parentNode, childIndex, RIGHT);
}
// 左右兄弟节点都不可借，思考合并
else if (pLeft) // 与左兄弟合并
{pLeft->mergeChild(parentNode, pChildNode, childIndex-1);
pChildNode = pLeft;
}
else if (pRight) // 与右兄弟合并
{pChildNode->mergeChild(parentNode, pRight, childIndex);
}
}
recursive_remove(pChildNode, key, dataValue);
}
}
vector<DataType> CBPlusTree::select(KeyType compareKey, int compareOpeartor)
{
vector<DataType> results;
if (m_Root!=NULL)
{if (compareKey>m_MaxKey) // 比拟键值大于 B + 树中最大的键值
{if (compareOpeartor==LE || compareOpeartor==LT)
{for(CLeafNode* itr = m_DataHead; itr!=NULL; itr= itr->getRightSibling())
{for (int i=0; i<itr->getKeyNum(); ++i)
{results.push_back(itr->getData(i));
}
}
}
}
else if (compareKey<m_DataHead->getKeyValue(0)) // 比拟键值小于 B + 树中最小的键值
{if (compareOpeartor==BE || compareOpeartor==BT)
{for(CLeafNode* itr = m_DataHead; itr!=NULL; itr= itr->getRightSibling())
{for (int i=0; i<itr->getKeyNum(); ++i)
{results.push_back(itr->getData(i));
}
}
}
}
else // 比拟键值在 B + 树中
{
SelectResult result;
search(compareKey, result);
switch(compareOpeartor)
{
case LT:
case LE:
{
CLeafNode* itr = m_DataHead;
int i;
while (itr!=result.targetNode)
{for (i=0; i<itr->getKeyNum(); ++i)
{results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();}
for (i=0; i<result.keyIndex; ++i)
{results.push_back(itr->getData(i));
}
if (itr->getKeyValue(i)<compareKey ||
(compareOpeartor==LE && compareKey==itr->getKeyValue(i)))
{results.push_back(itr->getData(i));
}
}
break;
case EQ:
{if (result.targetNode->getKeyValue(result.keyIndex)==compareKey)
{results.push_back(result.targetNode->getData(result.keyIndex));
}
}
break;
case BE:
case BT:
{
CLeafNode* itr = result.targetNode;
if (compareKey<itr->getKeyValue(result.keyIndex) ||
(compareOpeartor==BE && compareKey==itr->getKeyValue(result.keyIndex))
)
{results.push_back(itr->getData(result.keyIndex));
}
int i;
for (i=result.keyIndex+1; i<itr->getKeyNum(); ++i)
{results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();
while (itr!=NULL)
{for (i=0; i<itr->getKeyNum(); ++i)
{results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();}
}
break;
default: // 范畴查问
break;
}
}
}
sort<vector<DataType>::iterator>(results.begin(), results.end());
return results;
}
vector<DataType> CBPlusTree::select(KeyType smallKey, KeyType largeKey)
{
vector<DataType> results;
if (smallKey<=largeKey)
{
SelectResult start, end;
search(smallKey, start);
search(largeKey, end);
CLeafNode* itr = start.targetNode;
int i = start.keyIndex;
if (itr->getKeyValue(i)<smallKey)
{++i;}
if (end.targetNode->getKeyValue(end.keyIndex)>largeKey)
{--end.keyIndex;}
while (itr!=end.targetNode)
{for (; i<itr->getKeyNum(); ++i)
{results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();
i = 0;
}
for (; i<=end.keyIndex; ++i)
{results.push_back(itr->getData(i));
}
}
sort<vector<DataType>::iterator>(results.begin(), results.end());
return results;
}
void CBPlusTree::search(KeyType key, SelectResult& result)
{recursive_search(m_Root, key, result);
}
void CBPlusTree::recursive_search(CNode* pNode, KeyType key, SelectResult& result)
{int keyIndex = pNode->getKeyIndex(key);
int childIndex = pNode->getChildIndex(key, keyIndex); // 孩子结点指针索引
if (pNode->getType()==LEAF)
{
result.keyIndex = keyIndex;
result.targetNode = (CLeafNode*)pNode;
return;
}
else
{return recursive_search(((CInternalNode*)pNode)->getChild(childIndex), key, result);
}
}红黑树
https://www.cnblogs.com/sgatb…
性质
在一棵红黑树中，其每个结点上减少了一个存储位（属性 color）来示意结点的色彩，且色彩只能是 red or black。通过对任何一条从根到叶子的简略门路上各个结点的色彩进行束缚，红黑树确保没有一条门路会比其余门路长出 2 倍，因而是近似于均衡的。
树中每个结点蕴含 5 个属性：color、val、lchild、rchild 和 p（可选）。如果一个结点没有子结点或父结点，则该结点相应指针属性的值为 NIL。咱们能够把这些 NIL 视为指向二叉搜寻树的叶结点（内部结点）的指针，而把带关键字的结点视为树的外部结点。
一棵红黑树是满足上面红黑性质的二叉搜寻树：
- 每个结点或是红色的，或是彩色的。
- 根结点是彩色的。
- 每个叶结点（NIL）是彩色的。
- 如果一个结点是红色的，则它的两个子结点都是彩色的。
- 对每个结点，从该结点到其所有后辈叶结点的简略门路上，均蕴含雷同数目的彩色结点。
为了便于解决红黑树代码中的边界条件，应用一个哨兵来代表 NIL。对于一棵红黑树 tree，哨兵 NIL 是与一个与树中一般结点有雷同属性的对象。它的 color 属性为 black，其余属性能够为任意值。
旋转
在一棵含有 n 个关键字的红黑树上，进行插入和删除操作，须要的工夫复杂度为 O(logn)，因为这两个操作，会导致插入和删除后的树不满足红黑树的性质。为了保护这些性质，须要扭转树中某些结点的色彩以及指针构造。
指针构造的批改是通过旋转来实现的，这是一种能放弃二叉搜寻树性质的搜寻树部分操作，旋转分为左旋和右旋。如下图所示：
上面给出左旋和右旋操作的代码为：
Code
template<typename T>
void RedBlackTree<T>::LeftRotation(RedBlackNode<T>* &t){
RedBlackNode<T> *temp = t->rchild;
t->rchild = temp->lchild;
if(Parent(t)==NIL){root = temp;}
temp->lchild = t;
Parent(t)->rchild = temp;
}
template<typename T>
void RedBlackTree<T>::RightRotation(RedBlackNode<T>* &t){
RedBlackNode<T> *temp = t->lchild;
t->lchild = temp->rchild;
if(Parent(t)==NIL){root = temp;}
temp->rchild = t;
Parent(t)->lchild = temp;
}插入
后面说过，在一棵含有 n 个关键字的红黑树上，执行插入操作，须要工夫复杂度为 O(logn)。为了做到这一点，须要往原红黑树中插入一个红色的结点。那么问题来了，为什么插入的是红色结点，而不是彩色结点呢？咱们晓得，红黑树有五个性质，如果插入红色结点，则可能会违反性质 4，而如果是插入彩色结点，则肯定会违反性质 5。也就是说，插入红色结点比插入彩色结点更不容易违反红黑树的性质，而违反性质条数越多，相应的要做的调整操作也就越多，导致算法的工夫复杂度也就越高，从而影响算法的执行速度。在《数据结构算法与解析》（高一凡著，清华大学出版社）一书中，给出了插入结点为红色以及插入结点为彩色两种操作的算法，本文以插入结点为红色进行解说。
对于一棵红黑树来说，插入一个红色结点，次要有六种状况，其中三种与另外三种是对称的。这一点取决于插入结点 z 的父亲结点是插入结点的祖父结点的左孩子还是右孩子。
上面给出两种对称下，所对应的三种状况：
- case1：插入结点 z 的叔结点 y 是红色的。
上图显示了该状况的情景，这种状况切实插入结点 z 的父结点 z.p 和其叔结点 y 都是红色时产生的。因为插入结点 z 的祖父结点 z.p.p 是彩色的，所以将 z.p 和 y 都着为彩色，来解决 z 和 z.p 都是红色的问题，而因为性质 5 的要求，如果只是把 z.p 和 y 的色彩改为彩色，则会毁坏该性质，因而须要对 z.p.p 结点的色彩进行调整，以保障性质 5 的满足。
然而，性质 1 调整当前，就肯定能维持红黑树的性质吗？咱们以 z 示意新插入的结点，z’ 示意通过此次操作后的结点，由上述操作能够晓得，z’=z.p.p。则通过此次操作后，有以下后果：
-
- 因为这次操作把 z.p.p 着为红色，结点 z ’ 在下次操作的开始是红色的。
- 在这次操作中结点 z ’.p 是 z.p.p.p，且这个结点的色彩不会扭转。如果它是根结点，则在此次迭代之前它是彩色的，且它在下次操作的结尾任然是彩色的。
- 咱们也晓得，case1 放弃性质 5，而且它也不会引起性质 1 或性质 3 的毁坏。
如果结点 z ’ 在下一次操作开始时是根结点，则在这次操作中 case1 修改了惟一被毁坏的性质 4。因为 z ’ 是红色的而且是根结点，所以性质 2 成为惟一被违反的性质，这是由 z ’ 导致的。
如果结点 z ’ 在下一次操作开始时不是根结点，则 case1 不会导致性质 2 被毁坏，case1 修改了在这次操作的开始惟一违反的性质 4。而后把 z’着色为红色而 z ’.p 不变，因而，如果 z ’.p 是彩色的，则没有违反性质 4，若是 z ’.p 是红色的，则违反了性质 4。
- case2：插入结点 z 的叔结点 y 是彩色的且 z 是一个右孩子。
- case3：插入结点 z 的叔结点 y 是彩色的且 z 是一个左孩子。
在 case2 和 case3 中，z 的叔结点是彩色的。通过 z 是 z.p 的右孩子还是左孩子来区别这两种状况（叔结点都是彩色，无奈在逻辑上进行区别）。对于这两种状况，如下图所示：
左图为 case2，右图为 case3
咱们发现 case2 与 case3 存在某种指针构造上的关系，很显著二者之间能够通过左旋和右旋操作进行互相转换。因为 z 和 z.p 都是红色的，因而，旋转操作对树的黑高和性质 5 都无影响。无论怎么进入哪两种状况，y 总是彩色的，否则就要执行 case1 对应的操作。此外，这种旋转操作，有个益处是，并不扭转旋转后，z 的身份，只管会导致 z 的左右孩子身份扭转了，但仍旧是 z.p 的孩子。在 case3 中，咱们能够通过扭转某些结点的色彩，并作一次右旋，就能保障性质 5。这样，因为在一行中不会再存在有两个红色结点，因而，保障了红黑树的性质，所有的解决也到此结束了。如下所示：
能够看到，case2 和 case3 的操作，会最终使得插入结点后的树，维持红黑树的性质。由此，不禁狐疑，这样的操作能齐全保障吗？答案是必定的。上面来证实：
- case2 让 z 指向红色的 z.p。在 case2 和 case3 中，z 或 z 的色彩都不会扭转，所以，在由 case2 转为 case3 后，这并不会产生其余性质的扭转。
- case3 把 z.p 着成彩色，使得如果 z.p 在下一次操作开始时是根结点，则它是彩色的。
- 和 case1 一样，红黑树的性质 1、3、5 都在 case2 和 case3 中得以放弃。
因为结点 z 在 case2 和 case3 中都不是根结点，因而，性质 2 未被毁坏，这两种状况因而也不会引起性质 2 的违反。由此，证实了 z.p 为 z.p.p 的左孩子时候，对插入 z 后的红黑树，依照上述调整，能够做到复原红黑树的性质。而当 z.p 为 z.p.p 的右孩子时，因为与后面一大状况是对称的，因而，通过批改 left 和 right 的对应，就可实现。而齐全实现树的回复，能够通过 while 循环来放弃。以下是实现树的插入的代码：
template<typename T>
bool RedBlackTree<T>::Insert(T e){
RedBlackNode<T> *p, *f;
p = f = NULL;
if(!searchBST(root, p, e, f)){//not found, need to create, p points to the last node.
RedBlackNode<T> *s = createNewNode(e);
if(root==NULL){
root = s;
root->color = "black";
}
else{if(e<p->val){p->lchild = s;}
else{p->rchild = s;}
if(p->color == "red"){//double red node, need to adjust
adjustDoubleRed(s, p);
}
}
return true;
}
else{//node exists. return false
return false;
}
}
template<typename T>
RedBlackNode<T>* RedBlackTree<T>::Parent(RedBlackNode<T>* &t)const{
/*
*@Parameter:
*q: a queue to save rb-node.
*t: a point which points to a node in the RBTree.
*father: a point which points to the father node of t.
*/
queue<RedBlackNode<T>*> q;
RedBlackNode<T>* father;
if(root!=NULL){q.push(root);
while(!q.empty()){//BFSTraverse to find the father node of t.
father = q.front();
q.pop();
if((father->lchild!=NIL&&father->lchild==t)||(father->rchild!=NIL&&father->rchild==t)){return father;}
else{if(father->lchild!=NIL){q.push(father->lchild);
}
if(father->rchild!=NIL){q.push(father->rchild);
}
}
}
}
return NIL; //not found, return NIL
}
template<typename T>
bool RedBlackTree<T>::searchBST(RedBlackNode<T>* &t, RedBlackNode<T>* &p, T &e, RedBlackNode<T>* f)const{
// 在树中 t 中递归地查找其值等于 e 的数据，若查找胜利，则指针 p 指向该数据
// 结点，并返回 true，否则指针 p 指向查找门路上拜访的最初一个结点以便插入
// 并返回 false，指针 f 指向 p 的双亲，其初始调用值为 NULL。Insert()调用
if(t==NULL||t==NIL){
p = f;
return false;
}
if(e==t->val){
p = t;
return true;
}
else if(e<t->val){return searchBST(t->lchild, p, e, t);
}
else{return searchBST(t->rchild, p, e, t);
}
}
template<typename T>
void RedBlackTree<T>::LeftRotation(RedBlackNode<T>* &t){
RedBlackNode<T> *temp = t->rchild;
t->rchild = temp->lchild;
if(Parent(t)==NIL){root = temp;}
temp->lchild = t;
Parent(t)->rchild = temp;
}
template<typename T>
void RedBlackTree<T>::RightRotation(RedBlackNode<T>* &t){
RedBlackNode<T> *temp = t->lchild;
t->lchild = temp->rchild;
if(Parent(t)==NIL){root = temp;}
temp->rchild = t;
Parent(t)->lchild = temp;
}
template<typename T>
void RedBlackTree<T>::adjustDoubleRed(RedBlackNode<T>* &s, RedBlackNode<T>* &p){
/*
*@Parameter:
*s: rb-node.
*p: the father node of s.
*/
RedBlackNode<T> *y, *gp;
while(p->color=="red"){gp = Parent(p);
if(p==gp->lchild){
y = gp->rchild;
if(y->color=="red"){//case 1
p->color = "black";
y->color = "black";
gp->color = "red";
s = gp;
p = Parent(s);
}
else if(s==p->rchild){//case 2
s = p;
LeftRotation(p);
}
else{
p->color = "black";
gp->color = "red";
RightRotation(gp);
}
}
else{
y = gp->lchild;
if(y->color=="red"){//case 1
p->color = "black";
y->color = "black";
gp->color = "red";
s = gp;
p = Parent(s);
}
else if(s==p->lchild){//case 2
s = p;
RightRotation(s);
}
else{
p->color = "black";
gp->color = "red";
LeftRotation(gp);
}
}
}
root->color = "black";
}删除
因为红黑树与 BST 树类似，因而，其删除操作与 BST 树在逻辑上是基本一致的，惟一的区别在于，红黑树须要对删除结点后的树进行调整，使其合乎红黑树的性质。对于一棵红黑树来说，如果先不思考结点的色彩，删除一个结点无非是三种状况，这一点与 BST 树是统一的，即：
- 被删除结点没有左右子结点；
- 被删除结点仅有一个子节点（左或右都有可能）；
- 被删除结点左右子结点都存在；
根据上述三种状况，能够编写出 BST 树的删除结点操作的代码，上面给出 BST 树的删除操作示意图：
很显著，红黑树在结点的构造上，也是合乎上述模式的，即左 < 根 < 右，因而，红黑树的删除操作是从 BST 输的删除操作的根底上，批改失去的，为什么须要批改呢？就是因为红黑树的每个结点具备红黑属性。
因为红黑属性的影响，导致，删除结点后红黑树将不合乎红黑树原有的个性，咱们晓得，删除某个结点，依照上述调整，将会使得被删除结点所在的子树不合乎原红黑树的个性 1、2、4 或 5（非删除结点不受影响）。因而，只须要对子树进行色彩调整，就能使红黑树性质放弃不变。
伪代码中 Transplant 函数实现
如何删除的原理曾经讲明确了，那么咱们看，两个结点是如何替换（也就是产生删除操作的）。
在伪码中，结点 u 为被替换结点，你能够了解为，被删除结点，而 v 是用来替换被删除结点的结点（通常为 u 的子节点或者 u 的右子树结点的最小节点）。
Code
template<typename T>
void RedBlackTree<T>::Transplant(RedBlackNode<T>* &u, RedBlackNode<T>* &v){
/*
*a function to achieve node u is replaced by v.
*@Parameter:
*u: a node which is replaced by v.
*v: a node wants to replace u.
*/
if(Parent(u) == NIL){// 待删除结点为根结点.
root = v;
}
else if(u==Parent(u)->lchild){Parent(u)->lchild = v;
}
else{Parent(u)->rchild = v;
}
}具体实现
上面给出删除操作的伪代码（源自《算法导论》）。
在上述代码中，结点 z 为删除结点，y 为指向结点 z 的指针。咱们晓得，BST 的删除操作是很容易实现的，对于红黑树来说，关键在于，删除操作当前，什么状况下，会毁坏红黑树的红黑性质。
因为 y 的色彩有可能产生扭转（因为依据代码，y 始终指向树结构中被删除结点的地位），用变量 y_original_color 存储了产生扭转前的 y 地位的色彩。第 2 行和第 10 行在给 y 赋值之后，立刻设置该变量。当 z 有两个子结点时，则 y！= z 且结点 y 移至红黑树中结点 z 的原始地位；第 20 行给 y 赋予和 z 一样的色彩。而后保留 y 的原始色彩，以在删除操作完结时，测试它；如果它是彩色的，那么删除或挪动 y 会引起红黑性质的毁坏，为什么会是彩色引起红黑性质的毁坏呢？
- 对于状况 1，即不存在子结点的被删除结点来说，什么状况下删除该结点当前会扭转原有红黑树的性质呢？很显然，被删除结点是彩色的时候，删除它会违反红黑树的性质 5，而被删除结点为红色的时候，删除它并不会影响红黑树的性质，间接批改即可（如下所示），在这里，就产生了删除结点后，后续批改色彩的第一种状况。
如上图所示，如果删除结点 5，对于左侧的树，如果删除结点 y，则结点 7 不会违反任何红黑树的性质，因为结点 y 的子结点为必然为彩色（因为红黑树的性质），因而，y 为红色不会引起红黑树性质的扭转；对于右侧的树，如果删除结点 y，则如果结点 y 的子结点为 NIL（彩色），不会引起结点 7 与结点 y 子结点之间都为红色，从而不违反了红黑树的性质。
- 对于状况 2，即存在左结点或者右结点，因为红黑树结点存在 color 属性，因而，常见的做法是将用来替换删除结点的结点的色彩改成与删除结点色彩统一，这样，只须要对批改过指针构造后的子树进行批改其色彩，即可实现红黑树性质的放弃。那么，因为色彩的存在，又会有那些状况的呈现呢？咱们晓得，一个结点无非是红色或者彩色，且依据性质，红结点的子结点色彩必为彩色，那么，以被删除结点为左结点为例，有上面两种状况：
从右边的红黑树来看，如果待删除结点色彩为彩色，当对该结点进行操作时，则因为，其子结点为红色，与 y 结点的父结点同为红色，因而，会违反红黑树的性质，而如果是左边的状况，则不会，因为删除结点 y 当前，因为结点 4 仍旧为彩色，不会毁坏红黑树的性质。对于这种状况下，左子树结点不存在而右子树结点存在的状况，也是同样的情理，读者能够本人画图思考一下。
- 对于状况 3，即被删除结点同时存在左右子结点，如下图所示：
从上图来看，如果删除结点 5，会与状况 2 一样而违反性质，而对于左边的树，则不会，因为，咱们删除的形式，是将 z 结点也就是结点 5 的左子树，连贯到结点 5 右子树的值最小的结点上。而后用这个最小结点来替换原来结点 z（也就是图上结点 5 的地位）。这样做的益处是，仍能够保障删除后的树仍满足 BST 树的性质，咱们只须要对被删除结点的子树进行批改色彩性质就能够了，而且，不管最小结点的色彩如何，都不会导致呈现两个红结点的状况。这一点可能很多人会存在纳闷，咱们来剖析一下：
对于左右子树都存在的的删除结点来说，此时，y 从指向 z 转向了指向删除结点 z 的右子树种最小的一个结点（右子树的最左结点），这样的指向，无非两种状况，一种是右子树的最左结点就是被删除结点 z 的右孩子，即其右孩子的左孩子为 NIL，这样，以上右图为例，y 指向了结点 6，然 6 后，用 y_original_color 来保留结点 6 的色彩，用 x 指向 6 的右孩子，因为在这里，y 的父亲结点仍旧为删除结点 z，因而，设置好结点属性 x.p = y，而后，执行替换操作（Transplant）来实现删除的目标，能够看到，transplant 操作是对删除结点 z 和替换结点 y 进行操作的，对于这种状况来说，是将 z 与其右孩子进行替换，依据伪码，结点 7 的左孩子指向了结点 6。而后结点 6 也就是当初的结点 y 的左孩子指向了结点 z 的左孩子，这样就实现了而后将结点 y 的色彩，改成结点 z 的色彩，为什么这么做呢，是为了放弃与原来红黑树雷同的个性，因为咱们晓得，在删除结点 5 之前，结点 5 左右两棵子树的一条门路上的彩色结点数目是雷同的，然而，因为结点 6 的上位（替换了其父结点），而父结点的左孩子间接成为其左子树，这就导致了左右两子树的不均衡，调整为与 z 结点雷同的色彩当前，能够使得对红黑树批改操作仅局限于结点 y 这棵子树中进行。
另一种状况则是右子树的最左结点不是被删除结点 z 的右孩子，即其右孩子的左孩子非空，那么，其余操作不变，比拟奇妙的是，这里使用了最左结点的左孩子为 NIL 的个性，将最左结点的右子树接到了其父节点的右边（这就保障了 BST 树的有序性），且这样的做法，使得该结点与树在结构上断开，无奈通过树的根结点拜访到，因而，后续再执行一次删除结点 z 与结点 y 的替换操作，就能够实现这样的删除操作。这种状况下，会产生 y 为红色或者彩色结点的问题，同样，也只会有彩色会违反红黑树的性质。
删除操作之后扭转色彩
通过下面的剖析，咱们很容易失去这样的论断，那就是，只有当 y 为彩色结点的时候，才会产生违反红黑树性质的状况，因而，须要对这样的状况进行批改，来放弃红黑树的性质。上面给出《算法导论》中，对于该操作的伪代码：
在剖析源码以前，咱们首先来剖析，执行删除操作当前，会呈现哪些违反红黑树性质的状况。在这个操作中，联合删除操作的代码，咱们能够发现，x 始终指向具备双重彩色的非根结点。那么，就会有 4 种状况，这四种状况与插入操作中的是相似的，请读者联合上述删除操作，自行剖析。
Code
template<typename T>
void RedBlackTree<T>::Delete(RedBlackNode<T>* &t){
/*
*function to delete node t in redblacktree.
*@Parameter:
*t: a node need to be deleted.
*/
RedBlackNode<T> *y;
RedBlackNode<T> *p;
y = t;
string y_original_color = y->color;
if(t->lchild==NIL){
p = t->rchild;
Transplant(t, t->rchild);
}
else if(t->rchild==NIL){
p = t->lchild;
Transplant(t, t->lchild);
}
else{y = TreeMinimum(t->rchild);
y_original_color = y->color;
p = y->rchild;
if(Parent(y)!=t){Transplant(y, y->rchild);
y->rchild = t->rchild;
}
Transplant(t, y);
y->lchild = t->lchild;
y->color = t->color;
}
if(y_original_color=="black"){RBDeleteFixup(p);
}
delete t;
t = NULL;
}Code
https://www.cnblogs.com/skywa…
（举荐）
//RBTree.h
/**
* C++ 语言: 红黑树
*
* @author skywang
* @date 2013/11/07
*/
#ifndef _RED_BLACK_TREE_HPP_
#define _RED_BLACK_TREE_HPP_
#include <iomanip>
#include <iostream>
using namespace std;
enum RBTColor{RED, BLACK};
template <class T>
class RBTNode{
public:
RBTColor color; // 色彩
T key; // 关键字(键值)
RBTNode *left; // 左孩子
RBTNode *right; // 右孩子
RBTNode *parent; // 父结点
RBTNode(T value, RBTColor c, RBTNode *p, RBTNode *l, RBTNode *r):
key(value),color(c),parent(),left(l),right(r) {}};
template <class T>
class RBTree {
private:
RBTNode<T> *mRoot; // 根结点
public:
RBTree();
~RBTree();
// 前序遍历 "红黑树"
void preOrder();
// 中序遍历 "红黑树"
void inOrder();
// 后序遍历 "红黑树"
void postOrder();
// (递归实现)查找 "红黑树" 中键值为 key 的节点
RBTNode<T>* search(T key);
// (非递归实现)查找 "红黑树" 中键值为 key 的节点
RBTNode<T>* iterativeSearch(T key);
// 查找最小结点：返回最小结点的键值。T minimum();
// 查找最大结点：返回最大结点的键值。T maximum();
// 找结点 (x) 的后继结点。即，查找 "红黑树中数据值大于该结点" 的 "最小结点"。RBTNode<T>* successor(RBTNode<T> *x);
// 找结点 (x) 的前驱结点。即，查找 "红黑树中数据值小于该结点" 的 "最大结点"。RBTNode<T>* predecessor(RBTNode<T> *x);
// 将结点 (key 为节点键值) 插入到红黑树中
void insert(T key);
// 删除结点(key 为节点键值)
void remove(T key);
// 销毁红黑树
void destroy();
// 打印红黑树
void print();
private:
// 前序遍历 "红黑树"
void preOrder(RBTNode<T>* tree) const;
// 中序遍历 "红黑树"
void inOrder(RBTNode<T>* tree) const;
// 后序遍历 "红黑树"
void postOrder(RBTNode<T>* tree) const;
// (递归实现)查找 "红黑树 x" 中键值为 key 的节点
RBTNode<T>* search(RBTNode<T>* x, T key) const;
// (非递归实现)查找 "红黑树 x" 中键值为 key 的节点
RBTNode<T>* iterativeSearch(RBTNode<T>* x, T key) const;
// 查找最小结点：返回 tree 为根结点的红黑树的最小结点。RBTNode<T>* minimum(RBTNode<T>* tree);
// 查找最大结点：返回 tree 为根结点的红黑树的最大结点。RBTNode<T>* maximum(RBTNode<T>* tree);
// 左旋
void leftRotate(RBTNode<T>* &root, RBTNode<T>* x);
// 右旋
void rightRotate(RBTNode<T>* &root, RBTNode<T>* y);
// 插入函数
void insert(RBTNode<T>* &root, RBTNode<T>* node);
// 插入修改函数
void insertFixUp(RBTNode<T>* &root, RBTNode<T>* node);
// 删除函数
void remove(RBTNode<T>* &root, RBTNode<T> *node);
// 删除修改函数
void removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent);
// 销毁红黑树
void destroy(RBTNode<T>* &tree);
// 打印红黑树
void print(RBTNode<T>* tree, T key, int direction);
#define rb_parent(r) ((r)->parent)
#define rb_color(r) ((r)->color)
#define rb_is_red(r) ((r)->color==RED)
#define rb_is_black(r) ((r)->color==BLACK)
#define rb_set_black(r) do {(r)->color = BLACK; } while (0)
#define rb_set_red(r) do {(r)->color = RED; } while (0)
#define rb_set_parent(r,p) do {(r)->parent = (p); } while (0)
#define rb_set_color(r,c) do {(r)->color = (c); } while (0)
};
/*
* 构造函数
*/
template <class T>
RBTree<T>::RBTree():mRoot(NULL)
{mRoot = NULL;}
/*
* 析构函数
*/
template <class T>
RBTree<T>::~RBTree()
{destroy();
}
/*
* 前序遍历 "红黑树"
*/
template <class T>
void RBTree<T>::preOrder(RBTNode<T>* tree) const
{if(tree != NULL)
{
cout<< tree->key << " " ;
preOrder(tree->left);
preOrder(tree->right);
}
}
template <class T>
void RBTree<T>::preOrder()
{preOrder(mRoot);
}
/*
* 中序遍历 "红黑树"
*/
template <class T>
void RBTree<T>::inOrder(RBTNode<T>* tree) const
{if(tree != NULL)
{inOrder(tree->left);
cout<< tree->key << " " ;
inOrder(tree->right);
}
}
template <class T>
void RBTree<T>::inOrder()
{inOrder(mRoot);
}
/*
* 后序遍历 "红黑树"
*/
template <class T>
void RBTree<T>::postOrder(RBTNode<T>* tree) const
{if(tree != NULL)
{postOrder(tree->left);
postOrder(tree->right);
cout<< tree->key << " " ;
}
}
template <class T>
void RBTree<T>::postOrder()
{postOrder(mRoot);
}
/*
* (递归实现)查找 "红黑树 x" 中键值为 key 的节点
*/
template <class T>
RBTNode<T>* RBTree<T>::search(RBTNode<T>* x, T key) const
{if (x==NULL || x->key==key)
return x;
if (key < x->key)
return search(x->left, key);
else
return search(x->right, key);
}
template <class T>
RBTNode<T>* RBTree<T>::search(T key)
{search(mRoot, key);
}
/*
* (非递归实现)查找 "红黑树 x" 中键值为 key 的节点
*/
template <class T>
RBTNode<T>* RBTree<T>::iterativeSearch(RBTNode<T>* x, T key) const
{while ((x!=NULL) && (x->key!=key))
{if (key < x->key)
x = x->left;
else
x = x->right;
}
return x;
}
template <class T>
RBTNode<T>* RBTree<T>::iterativeSearch(T key)
{iterativeSearch(mRoot, key);
}
/*
* 查找最小结点：返回 tree 为根结点的红黑树的最小结点。*/
template <class T>
RBTNode<T>* RBTree<T>::minimum(RBTNode<T>* tree)
{if (tree == NULL)
return NULL;
while(tree->left != NULL)
tree = tree->left;
return tree;
}
template <class T>
T RBTree<T>::minimum()
{RBTNode<T> *p = minimum(mRoot);
if (p != NULL)
return p->key;
return (T)NULL;
}
/*
* 查找最大结点：返回 tree 为根结点的红黑树的最大结点。*/
template <class T>
RBTNode<T>* RBTree<T>::maximum(RBTNode<T>* tree)
{if (tree == NULL)
return NULL;
while(tree->right != NULL)
tree = tree->right;
return tree;
}
template <class T>
T RBTree<T>::maximum()
{RBTNode<T> *p = maximum(mRoot);
if (p != NULL)
return p->key;
return (T)NULL;
}
/*
* 找结点 (x) 的后继结点。即，查找 "红黑树中数据值大于该结点" 的 "最小结点"。*/
template <class T>
RBTNode<T>* RBTree<T>::successor(RBTNode<T> *x)
{
// 如果 x 存在右孩子，则 "x 的后继结点" 为 "以其右孩子为根的子树的最小结点"。if (x->right != NULL)
return minimum(x->right);
// 如果 x 没有右孩子。则 x 有以下两种可能：// (01) x 是 "一个左孩子"，则 "x 的后继结点" 为 "它的父结点"。// (02) x 是 "一个右孩子"，则查找 "x 的最低的父结点，并且该父结点要具备左孩子"，找到的这个 "最低的父结点" 就是 "x 的后继结点"。RBTNode<T>* y = x->parent;
while ((y!=NULL) && (x==y->right))
{
x = y;
y = y->parent;
}
return y;
}
/*
* 找结点 (x) 的前驱结点。即，查找 "红黑树中数据值小于该结点" 的 "最大结点"。*/
template <class T>
RBTNode<T>* RBTree<T>::predecessor(RBTNode<T> *x)
{
// 如果 x 存在左孩子，则 "x 的前驱结点" 为 "以其左孩子为根的子树的最大结点"。if (x->left != NULL)
return maximum(x->left);
// 如果 x 没有左孩子。则 x 有以下两种可能：// (01) x 是 "一个右孩子"，则 "x 的前驱结点" 为 "它的父结点"。// (01) x 是 "一个左孩子"，则查找 "x 的最低的父结点，并且该父结点要具备右孩子"，找到的这个 "最低的父结点" 就是 "x 的前驱结点"。RBTNode<T>* y = x->parent;
while ((y!=NULL) && (x==y->left))
{
x = y;
y = y->parent;
}
return y;
}
/*
* 对红黑树的节点 (x) 进行左旋转
*
* 左旋示意图(对节点 x 进行左旋)：* px px
* / /
* x y
* / \ --(左旋)--> / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
template <class T>
void RBTree<T>::leftRotate(RBTNode<T>* &root, RBTNode<T>* x)
{
// 设置 x 的右孩子为 y
RBTNode<T> *y = x->right;
// 将“y 的左孩子”设为“x 的右孩子”；// 如果 y 的左孩子非空，将“x”设为“y 的左孩子的父亲”x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
// 将“x 的父亲”设为“y 的父亲”y->parent = x->parent;
if (x->parent == NULL)
{root = y; // 如果“x 的父亲”是空节点，则将 y 设为根节点}
else
{if (x->parent->left == x)
x->parent->left = y; // 如果 x 是它父节点的左孩子，则将 y 设为“x 的父节点的左孩子”else
x->parent->right = y; // 如果 x 是它父节点的左孩子，则将 y 设为“x 的父节点的左孩子”}
// 将“x”设为“y 的左孩子”y->left = x;
// 将“x 的父节点”设为“y”x->parent = y;
}
/*
* 对红黑树的节点 (y) 进行右旋转
*
* 右旋示意图(对节点 y 进行左旋)：* py py
* / /
* y x
* / \ --(右旋)--> / \ #
* x ry lx y
* / \ / \ #
* lx rx rx ry
*
*/
template <class T>
void RBTree<T>::rightRotate(RBTNode<T>* &root, RBTNode<T>* y)
{
// 设置 x 是以后节点的左孩子。RBTNode<T> *x = y->left;
// 将“x 的右孩子”设为“y 的左孩子”；// 如果 "x 的右孩子" 不为空的话，将“y”设为“x 的右孩子的父亲”y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
// 将“y 的父亲”设为“x 的父亲”x->parent = y->parent;
if (y->parent == NULL)
{root = x; // 如果“y 的父亲”是空节点，则将 x 设为根节点}
else
{if (y == y->parent->right)
y->parent->right = x; // 如果 y 是它父节点的右孩子，则将 x 设为“y 的父节点的右孩子”else
y->parent->left = x; // (y 是它父节点的左孩子) 将 x 设为“x 的父节点的左孩子”}
// 将“y”设为“x 的右孩子”x->right = y;
// 将“y 的父节点”设为“x”y->parent = x;
}
/*
* 红黑树插入修改函数
*
* 在向红黑树中插入节点之后(失去平衡)，再调用该函数；* 目标是将它从新塑造成一颗红黑树。*
* 参数阐明：* root 红黑树的根
* node 插入的结点 // 对应《算法导论》中的 z
*/
template <class T>
void RBTree<T>::insertFixUp(RBTNode<T>* &root, RBTNode<T>* node)
{
RBTNode<T> *parent, *gparent;
// 若“父节点存在，并且父节点的色彩是红色”while ((parent = rb_parent(node)) && rb_is_red(parent))
{gparent = rb_parent(parent);
// 若“父节点”是“祖父节点的左孩子”if (parent == gparent->left)
{
// Case 1 条件：叔叔节点是红色
{
RBTNode<T> *uncle = gparent->right;
if (uncle && rb_is_red(uncle))
{rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
// Case 2 条件：叔叔是彩色，且以后节点是右孩子
if (parent->right == node)
{
RBTNode<T> *tmp;
leftRotate(root, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3 条件：叔叔是彩色，且以后节点是左孩子。rb_set_black(parent);
rb_set_red(gparent);
rightRotate(root, gparent);
}
else// 若“z 的父节点”是“z 的祖父节点的右孩子”{
// Case 1 条件：叔叔节点是红色
{
RBTNode<T> *uncle = gparent->left;
if (uncle && rb_is_red(uncle))
{rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
// Case 2 条件：叔叔是彩色，且以后节点是左孩子
if (parent->left == node)
{
RBTNode<T> *tmp;
rightRotate(root, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3 条件：叔叔是彩色，且以后节点是右孩子。rb_set_black(parent);
rb_set_red(gparent);
leftRotate(root, gparent);
}
}
// 将根节点设为彩色
rb_set_black(root);
}
/*
* 将结点插入到红黑树中
*
* 参数阐明：* root 红黑树的根结点
* node 插入的结点 // 对应《算法导论》中的 node
*/
template <class T>
void RBTree<T>::insert(RBTNode<T>* &root, RBTNode<T>* node)
{
RBTNode<T> *y = NULL;
RBTNode<T> *x = root;
// 1. 将红黑树当作一颗二叉查找树，将节点增加到二叉查找树中。while (x != NULL)
{
y = x;
if (node->key < x->key)
x = x->left;
else
x = x->right;
}
node->parent = y;
if (y!=NULL)
{if (node->key < y->key)
y->left = node;
else
y->right = node;
}
else
root = node;
// 2. 设置节点的色彩为红色
node->color = RED;
// 3. 将它从新修改为一颗二叉查找树
insertFixUp(root, node);
}
/*
* 将结点 (key 为节点键值) 插入到红黑树中
*
* 参数阐明：* tree 红黑树的根结点
* key 插入结点的键值
*/
template <class T>
void RBTree<T>::insert(T key)
{
RBTNode<T> *z=NULL;
// 如果新建结点失败，则返回。if ((z=new RBTNode<T>(key,BLACK,NULL,NULL,NULL)) == NULL)
return ;
insert(mRoot, z);
}
/*
* 红黑树删除修改函数
*
* 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；* 目标是将它从新塑造成一颗红黑树。*
* 参数阐明：* root 红黑树的根
* node 待修改的节点
*/
template <class T>
void RBTree<T>::removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent)
{
RBTNode<T> *other;
while ((!node || rb_is_black(node)) && node != root)
{if (parent->left == node)
{
other = parent->right;
if (rb_is_red(other))
{
// Case 1: x 的兄弟 w 是红色的
rb_set_black(other);
rb_set_red(parent);
leftRotate(root, parent);
other = parent->right;
}
if ((!other->left || rb_is_black(other->left)) &&
(!other->right || rb_is_black(other->right)))
{
// Case 2: x 的兄弟 w 是彩色，且 w 的俩个孩子也都是彩色的
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{if (!other->right || rb_is_black(other->right))
{
// Case 3: x 的兄弟 w 是彩色的，并且 w 的左孩子是红色，右孩子为彩色。rb_set_black(other->left);
rb_set_red(other);
rightRotate(root, other);
other = parent->right;
}
// Case 4: x 的兄弟 w 是彩色的；并且 w 的右孩子是红色的，左孩子任意色彩。rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->right);
leftRotate(root, parent);
node = root;
break;
}
}
else
{
other = parent->left;
if (rb_is_red(other))
{
// Case 1: x 的兄弟 w 是红色的
rb_set_black(other);
rb_set_red(parent);
rightRotate(root, parent);
other = parent->left;
}
if ((!other->left || rb_is_black(other->left)) &&
(!other->right || rb_is_black(other->right)))
{
// Case 2: x 的兄弟 w 是彩色，且 w 的俩个孩子也都是彩色的
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{if (!other->left || rb_is_black(other->left))
{
// Case 3: x 的兄弟 w 是彩色的，并且 w 的左孩子是红色，右孩子为彩色。rb_set_black(other->right);
rb_set_red(other);
leftRotate(root, other);
other = parent->left;
}
// Case 4: x 的兄弟 w 是彩色的；并且 w 的右孩子是红色的，左孩子任意色彩。rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->left);
rightRotate(root, parent);
node = root;
break;
}
}
}
if (node)
rb_set_black(node);
}
/*
* 删除结点(node)，并返回被删除的结点
*
* 参数阐明：* root 红黑树的根结点
* node 删除的结点
*/
template <class T>
void RBTree<T>::remove(RBTNode<T>* &root, RBTNode<T> *node)
{
RBTNode<T> *child, *parent;
RBTColor color;
// 被删除节点的 "左右孩子都不为空" 的状况。if ((node->left!=NULL) && (node->right!=NULL) )
{// 被删节点的后继节点。(称为 "取代节点")
// 用它来取代 "被删节点" 的地位，而后再将 "被删节点" 去掉。RBTNode<T> *replace = node;
// 获取后继节点
replace = replace->right;
while (replace->left != NULL)
replace = replace->left;
// "node 节点" 不是根节点(只有根节点不存在父节点)
if (rb_parent(node))
{if (rb_parent(node)->left == node)
rb_parent(node)->left = replace;
else
rb_parent(node)->right = replace;
}
else
// "node 节点" 是根节点，更新根节点。root = replace;
// child 是 "取代节点" 的右孩子，也是须要 "调整的节点"。// "取代节点" 必定不存在左孩子！因为它是一个后继节点。child = replace->right;
parent = rb_parent(replace);
// 保留 "取代节点" 的色彩
color = rb_color(replace);
// "被删除节点" 是 "它的后继节点的父节点"
if (parent == node)
{parent = replace;}
else
{
// child 不为空
if (child)
rb_set_parent(child, parent);
parent->left = child;
replace->right = node->right;
rb_set_parent(node->right, replace);
}
replace->parent = node->parent;
replace->color = node->color;
replace->left = node->left;
node->left->parent = replace;
if (color == BLACK)
removeFixUp(root, child, parent);
delete node;
return ;
}
if (node->left !=NULL)
child = node->left;
else
child = node->right;
parent = node->parent;
// 保留 "取代节点" 的色彩
color = node->color;
if (child)
child->parent = parent;
// "node 节点" 不是根节点
if (parent)
{if (parent->left == node)
parent->left = child;
else
parent->right = child;
}
else
root = child;
if (color == BLACK)
removeFixUp(root, child, parent);
delete node;
}
/*
* 删除红黑树中键值为 key 的节点
*
* 参数阐明：* tree 红黑树的根结点
*/
template <class T>
void RBTree<T>::remove(T key)
{
RBTNode<T> *node;
// 查找 key 对应的节点(node)，找到的话就删除该节点
if ((node = search(mRoot, key)) != NULL)
remove(mRoot, node);
}
/*
* 销毁红黑树
*/
template <class T>
void RBTree<T>::destroy(RBTNode<T>* &tree)
{if (tree==NULL)
return ;
if (tree->left != NULL)
return destroy(tree->left);
if (tree->right != NULL)
return destroy(tree->right);
delete tree;
tree=NULL;
}
template <class T>
void RBTree<T>::destroy()
{destroy(mRoot);
}
/*
* 打印 "二叉查找树"
*
* key -- 节点的键值
* direction -- 0，示意该节点是根节点;
* -1，示意该节点是它的父结点的左孩子;
* 1，示意该节点是它的父结点的右孩子。*/
template <class T>
void RBTree<T>::print(RBTNode<T>* tree, T key, int direction)
{if(tree != NULL)
{if(direction==0) // tree 是根节点
cout << setw(2) << tree->key << "(B) is root" << endl;
else // tree 是分支节点
cout << setw(2) << tree->key << (rb_is_red(tree)?"(R)":"(B)") << "is" << setw(2) << key << "'s" << setw(12) << (direction==1?"right child" : "left child") << endl;
print(tree->left, tree->key, -1);
print(tree->right,tree->key, 1);
}
}
template <class T>
void RBTree<T>::print()
{if (mRoot != NULL)
print(mRoot, mRoot->key, 0);
}
#endif//RBTree.cpp
/**
* C++ 语言: 二叉查找树
*
* @author skywang
* @date 2013/11/07
*/
#include <iostream>
#include "RBTree.h"
using namespace std;
int main()
{int a[]= {10, 40, 30, 60, 90, 70, 20, 50, 80};
int check_insert=0; // "插入" 动作的检测开关(0，敞开；1，关上)
int check_remove=0; // "删除" 动作的检测开关(0，敞开；1，关上)
int i;
int ilen = (sizeof(a)) / (sizeof(a[0])) ;
RBTree<int>* tree=new RBTree<int>();
cout << "== 原始数据:";
for(i=0; i<ilen; i++)
cout << a[i] <<" ";
cout << endl;
for(i=0; i<ilen; i++)
{tree->insert(a[i]);
// 设置 check_insert=1, 测试 "增加函数"
if(check_insert)
{cout << "== 增加节点:" << a[i] << endl;
cout << "== 树的详细信息:" << endl;
tree->print();
cout << endl;
}
}
cout << "== 前序遍历:";
tree->preOrder();
cout << "\n== 中序遍历:";
tree->inOrder();
cout << "\n== 后序遍历:";
tree->postOrder();
cout << endl;
cout << "== 最小值:" << tree->minimum() << endl;
cout << "== 最大值:" << tree->maximum() << endl;
cout << "== 树的详细信息:" << endl;
tree->print();
// 设置 check_remove=1, 测试 "删除函数"
if(check_remove)
{for(i=0; i<ilen; i++)
{tree->remove(a[i]);
cout << "== 删除节点:" << a[i] << endl;
cout << "== 树的详细信息:" << endl;
tree->print();
cout << endl;
}
}
// 销毁红黑树
tree->destroy();
return 0;
}线段树
线段树详解
https://www.cnblogs.com/xenny…
我本人在学这些数据结构以及算法的时候，网上的博客很多都是给出一个大抵思维，而后就间接给代码了，可能是我智商太低，思维跳跃没有那么大，没法间接代码实现，而且有些学完之后也没有失去深层次的了解和使用，还是停留在只会应用模板的根底上。所以我心愿我写的货色能让更多的人看明确，我会尽量写具体，也会写出我初学的时候哪些地方没有了解或者难以使用，又是怎么去纯熟的应用这些货色的。可能还是不能让所有的人都读明确，但我尽量做的更好。
一、什么是线段树？
- 线段树是怎么的树形构造?
线段树是一种二叉搜寻树，什么叫做二叉搜寻树，首先满足二叉树，每个结点度小于等于二，即每个结点最多有两颗子树，何为搜寻，咱们要晓得，线段树的每个结点都存储了一个区间，也能够了解成一个线段，而搜寻，就是在这些线段上进行搜寻操作失去你想要的答案。
- 线段树可能解决什么样的问题。
线段树的适用范围很广，能够在线保护批改以及查问区间上的最值，求和。更能够裁减到二维线段树（矩阵树）和三维线段树（空间树）。对于一维线段树来说，每次更新以及查问的工夫复杂度为 O(logN)。
- 线段树和其余 RMQ 算法的区别
罕用的解决 RMQ 问题有 ST 算法，二者预处理工夫都是 O(NlogN)，而且 ST 算法的单次查问操作是 O(1)，看起来比线段树好多了，但二者的区别在于线段树反对在线更新值，而 ST 算法不反对在线操作。
这里也存在一个误区，刚学线段树的时候就认为线段树和树状数组差不多，用来解决 RMQ 问题和求和问题，但其实线段树的性能远远不止这些，咱们要纯熟的了解线段这个概念能力更加深层次的了解线段树。
二、线段树的根本内容
当初请各位不要带着线段树只是为了解决区间问题的数据结构，事实上，是线段树多用于解决区间问题，并不是线段树只能解决区间问题，首先，咱们得先明确几件事件。
每个结点存什么，结点下标是什么，如何建树。
上面我以一个简略的区间最大值来论述下面的三个概念。
对于 A[1:6] = {1,8,6,4,3,5}来说，线段树如上所示，红色代表每个结点存储的区间，蓝色代表该区间最值。
能够发现，每个叶子结点的值就是数组的值，每个非叶子结点的度都为二，且左右两个孩子别离存储父亲一半的区间。每个父亲的存储的值也就是两个孩子存储的值的最大值。
下面的每条论断应该都容易看进去。那么结点到底是如何存储区间的呢，以及如何疾速找到非叶子结点的孩子以及非根节点的父亲呢，这里也就是了解线段树的重点以及难点所在，如同树状数组你了解了 lowbit 就能很快了解树状数组一样，线段树你只有了解了结点与结点之间的关系便能很快了解线段树的基本知识。
对于一个区间 [l,r] 来说，最重要的数据当然就是区间的左右端点 l 和 r，然而大部分的状况咱们并不会去存储这两个数值，而是通过递归的传参形式进行传递。这种形式用指针好实现，定义两个左右子树递归即可，然而指针示意过于繁琐，而且不不便各种操作，大部分的线段树都是应用数组进行示意，那这里怎么疾速应用下标找到左右子树呢。
对于上述线段树，咱们减少绿色数字为每个结点的下标
则每个结点下标如上所示，这里你可能会问，为什么最下一排的下标间接从 9 跳到了 12，情理也很简略，两头其实是有两个空间的呀！！尽管没有应用，然而他曾经开了两个空间，这也是为什么无优化的线段树建树须要 2 2k（2k-1 < n < 2k)空间，个别会开到 4 n 的空间避免 RE。
仔细观察每个父亲和孩子下标的关系，有发现什么分割吗？不难发现，每个左子树的下标都是偶数，右子树的下标都是奇数且为左子树下标 +1，而且不难发现以下法则
- l = fa*2（左子树下标为父亲下标的两倍）
- r = fa*2+1（右子树下标为父亲下标的两倍 +1）
具体证实也很简略，把线段树看成一个齐全二叉树（空结点也当作应用）对于任意一个结点 k 来说，它所在此二叉树的 log2（k）层，则此层共有 2log2(k)个结点，同样对于 k 的左子树那层来说有 2log2(k)+ 1 个结点，则结点 k 和左子树距离了 2 2log2(k)-k + 2(k-2log2(k))个结点，而后这就很简略就失去 k +22log2(k)-k + 2(k-2log2(k)) = 2* k 的关系了吧，右子树也就等于左子树结点 +1。
是不是感觉其实很简略，而且因为左子树都是偶数，所以咱们罕用位运算来寻找左右子树
- k<<1（结点 k 的左子树下标）
- k<<1|1（结点 k 的右子树下标）
整顿一下思路，当初曾经明确了数组如何存在线段树，结点间的关系，以及应用递归的形式建设线段树，那么具体如何建设线段树，咱们来看代码，代码中不分明的中央都有具体的正文阐明。
const int maxn = 100005;
int a[maxn],t[maxn<<2]; // a 为原来区间，t 为线段树
void Pushup(int k){ // 更新函数，这里是实现最大值，同理能够变成，最小值，区间和等
t[k] = max(t[k<<1],t[k<<1|1]);
}
// 递归形式建树 build(1,1,n);
void build(int k,int l,int r){ // k 为以后须要建设的结点，l 为以后须要建设区间的左端点，r 则为右端点
if(l == r) // 左端点等于右端点，即为叶子节点，间接赋值即可
t[k] = a[l];
else{int m = l + ((r-l)>>1); // m 则为两头点，左儿子的结点区间为[l,m], 右儿子的结点区间为[m+1,r]
build(k<<1,l,m); // 递归结构左儿子结点
build(k<<1|1,m+1,r); // 递归结构右儿子结点
Pushup(k); // 更新父节点
}
}当初再来看代码，是不是感觉清晰很多了，应用递归的办法建设线段树，的确清晰易懂，各位看到这里也请本人试着实现一下递归建树，若是哪里有卡点再来看一下代码找到哪里出了问题。那线段树有没有非递归的形式建树呢，答案是有，然而非递归的建树形式会使得线段树的查问等操作和递归建树形式齐全不一样，由简至难，前面咱们再说非递归形式的实现。
到当初你应该能够建设一颗线段树了，而且晓得每个结点存储的区间和值，如果上述操作还不能实现或是有哪里想不明确，倡议再翻回去看一看所讲的内容。不要急于看完，了解才更重要。
三、线段树的基本操作
基本操作有哪些，你应该也能想进去，在线的二叉搜寻树，所领有的操作当然有，更新和询问两种。
1. 点更新
如何实现点更新，咱们先不急看代码，还是对于下面那个线段树，倘若我把 a[3]+7，则更新后的线段树应该变成
更新了 a[3]后，则每个蕴含此值的结点都须要更新，那么有多少个结点须要更新呢？依据二叉树的性质，不难发现是 log(k)个结点，这也正是为什么每次更新的工夫复杂度为 O(logN)，那应该如何实现呢，咱们发现，无论你更新哪个叶子节点，最终都是会到根结点的，而把这个往上推的过程逆过去就是从根结点开始，找到左子树还是右子树蕴含须要更新的叶子节点，往下更新即可，所以咱们还是能够应用递归的办法实现线段树的点更新
// 递归形式更新 updata(p,v,1,n,1);
void updata(int p,int v,int l,int r,int k){ // p 为下标，v 为要加上的值，l，r 为结点区间，k 为结点下标
if(l == r) // 左端点等于右端点，即为叶子结点，间接加上 v 即可
a[k] += v,t[k] += v; // 原数组和线段树数组都失去更新
else{int m = l + ((r-l)>>1); // m 则为两头点，左儿子的结点区间为[l,m], 右儿子的结点区间为[m+1,r]
if(p <= m) // 如果须要更新的结点在左子树区间
updata(p,v,l,m,k<<1);
else // 如果须要更新的结点在右子树区间
updata(p,v,m+1,r,k<<1|1);
Pushup(k); // 更新父节点的值
}
}看完代码是不是很清晰，这里也倡议本人再次手动实现一遍了解递归的思路。
2. 区间查问
说完了单点更新必定就要来说区间查问了，咱们晓得线段树的每个结点存储的都是一段区间的信息，如果咱们刚好要查问这个区间，那么则间接返回这个结点的信息即可，比方对于下面线段树，如果我间接查问 [1,6] 这个区间的最值，那么间接返回根节点信息返回 13 即可，然而个别咱们不会凑巧刚好查问那些区间，比方当初我要查问 [2,5] 区间的最值，这时候该怎么办呢，咱们来看看哪些区间是 [2,5] 的真子集，
一共有 5 个区间，而且咱们能够发现 [4,5] 这个区间曾经蕴含了两个子树的信息，所以咱们须要查问的区间只有三个，别离是[2,2],[3,3],[4,5]，到这里你能通过更新的思路想进去查问的思路吗? 咱们还是从根节点开始往下递归，如果以后结点是要查问的区间的真子集，则返回这个结点的信息且不须要再往下递归了，这样从根节点往下递归，工夫复杂度也是 O(logN)。那么代码则为
// 递归形式区间查问 query(L,R,1,n,1);
int query(int L,int R,int l,int r,int k){//[L,R]即为要查问的区间，l，r 为结点区间，k 为结点下标
if(L <= l && r <= R) // 如果以后结点的区间真蕴含于要查问的区间内，则返回结点信息且不须要往下递归
return t[k];
else{
int res = -INF; // 返回值变量，依据具体线段树查问的什么而自定义
int mid = l + ((r-l)>>1); // m 则为两头点，左儿子的结点区间为[l,m], 右儿子的结点区间为[m+1,r]
if(L <= m) // 如果左子树和须要查问的区间交加非空
res = max(res, query(L,R,l,m,k<<1));
if(R > m) // 如果右子树和须要查问的区间交加非空，留神这里不是 else if，因为查问区间可能同时和左右区间都有交加
res = max(res, query(L,R,m+1,r,k<<1|1));
return res; // 返回以后结点失去的信息
}
}如果你能了解建树和更新的过程，那么这里的区间查问也不会太难了解。还是倡议再次手动实现。
3. 区间更新
树状数组中的区间更新咱们用了差分的思维，而线段树的区间更新绝对于树状数组就略微简单一点，这里咱们引进了一个新货色，Lazy_tag，字面意思就是懈怠标记的意思，实际上它的性能也就是偷懒 = =，因为对于一个区间 [L,R] 来说，咱们可能每次都更新区间中的没个值，那样的话更新的复杂度将会是 O(NlogN)，这太高了，所以引进了 Lazy_tag，这个标记个别用于解决线段树的区间更新。
线段树在进行区间更新的时候，为了进步更新的效率，所以每次更新只更新到更新区间齐全笼罩线段树结点区间为止，这样就会导致被更新结点的子孙结点的区间得不到须要更新的信息，所以在被更新结点上打上一个标记，称为 lazy-tag，等到下次访问这个结点的子结点时再将这个标记传递给子结点，所以也能够叫提早标记。
也就是说递归更新的过程，更新到结点区间为须要更新的区间的真子集不再往下更新，下次若是遇到须要用这上面的结点的信息，再去更新这些结点，所以这样的话使得区间更新的操作和区间查问相似，复杂度为 O(logN)。
void Pushdown(int k){ // 更新子树的 lazy 值，这里是 RMQ 的函数，要实现区间和等则须要批改函数内容
if(lazy[k]){ // 如果有 lazy 标记
lazy[k<<1] += lazy[k]; // 更新左子树的 lazy 值
lazy[k<<1|1] += lazy[k]; // 更新右子树的 lazy 值
t[k<<1] += lazy[k]; // 左子树的最值加上 lazy 值
t[k<<1|1] += lazy[k]; // 右子树的最值加上 lazy 值
lazy[k] = 0; //lazy 值归 0
}
}
// 递归更新区间 updata(L,R,v,1,n,1);
void updata(int L,int R,int v,int l,int r,int k){//[L,R]即为要更新的区间，l，r 为结点区间，k 为结点下标
if(L <= l && r <= R){ // 如果以后结点的区间真蕴含于要更新的区间内
lazy[k] += v; // 懈怠标记
t[k] += v; // 最大值加上 v 之后，此区间的最大值也必定是加 v
}
else{Pushdown(k); // 重难点，查问 lazy 标记，更新子树
int m = l + ((r-l)>>1);
if(L <= m) // 如果左子树和须要更新的区间交加非空
update(L,R,v,l,m,k<<1);
if(m < R) // 如果右子树和须要更新的区间交加非空
update(L,R,v,m+1,r,k<<1|1);
Pushup(k); // 更新父节点
}
}留神看 Pushdown 这个函数，也就是当须要查问某个结点的子树时，须要用到这个函数，函数性能就是更新子树的 lazy 值，能够了解为平时先把事件放着，等到哪天要查看的时候，就长期再去做，而且做也不是一次性做完，查看哪一部分它就只做这一部分。是不是感触到了什么是 Lazy_tag，实至名归 = =。
值得注意的是，应用了 Lazy_tag 后，咱们再进行区间查问也须要扭转。区间查问的代码则变为
// 递归形式区间查问 query(L,R,1,n,1);
int query(int L,int R,int l,int r,int k){//[L,R]即为要查问的区间，l，r 为结点区间，k 为结点下标
if(L <= l && r <= R) // 如果以后结点的区间真蕴含于要查问的区间内，则返回结点信息且不须要往下递归
return t[k];
else{Pushdown(k); /** 每次都须要更新子树的 Lazy 标记 */
int res = -INF; // 返回值变量，依据具体线段树查问的什么而自定义
int mid = l + ((r-l)>>1); // m 则为两头点，左儿子的结点区间为[l,m], 右儿子的结点区间为[m+1,r]
if(L <= m) // 如果左子树和须要查问的区间交加非空
res = max(res, query(L,R,l,m,k<<1));
if(R > m) // 如果右子树和须要查问的区间交加非空，留神这里不是 else if，因为查问区间可能同时和左右区间都有交加
res = max(res, query(L,R,m+1,r,k<<1|1));
return res; // 返回以后结点失去的信息
}
}其实变动也不大，就是多了一个长期更新子树的值的过程。
四、线段树的其余操作
如果你明确了上述线段树解决区间最值的所有操作，那么转变成求最小值以及区间和问题应该也能很快解决，请手动再实现一下查问区间最小值的线段树和查问区间和的线段树。
区间和线段树等代码不再给出，自行实现，若不能实现能够去网上搜寻模板比照本人为何不能实现。这里便不再节约篇幅讲述。
这里我便是想说一下线段树还能解决的问题以及一些具体问题解说。上述咱们只是再讲线段树解决裸区间问题，然而大部分问题不会是让你间接更新查问，而是否真正了解线段树便在于思维是否能从区间跳到线段。
区间只是一个线段的一小部分，还有一些非区间问题也能够演变成一段一段的线段，而后再通过线段树进行各种操作。上面针对几道例题解说一下线段树的其余具体用法。
上面三道题解说并非本人所写，而是摘取了另一篇线段树的博客，特此申明，原博客地址：https://blog.csdn.net/whereis…
1. 区间染色
给定一个长度为 n(n <= 100000)的木板，反对两种操作：
1、P a b c 将 [a, b] 区间段染色成 c；
2、Q a b 询问 [a, b] 区间内有多少种颜色；
保障染色的色彩数少于 30 种。
比照区间求和，不同点在于区间求和的更新是对区间和进行累加；而这类染色问题则是对区间的值进行替换（或者叫笼罩），有一个比拟非凡的条件是色彩数目小于 30。
咱们是不是要将 30 种颜色的有无与否都存在线段树的结点上呢？答案是必定的，然而这样一来每个结点都要存储 30 个 bool 值，空间太节约，而且在计算合并操作的时候有一步 30 个元素的遍历，大大降低效率。然而 30 个 bool 值正好能够压缩在一个 int32 中，利用二进制压缩能够用一个 32 位的整型完满的存储 30 种颜色的有无状况。
因为任何一个整数都能够分解成二进制整数，二进制整数的每一位要么是 0，要么是 1。二进制整数的第 i 位是 1 示意存在第 i 种颜色；反之不存在。
数据域须要存一个色彩品种的位或和 colorBit，一个色彩的 lazy 标记示意这个结点被齐全染成了 lazy，基本操作的几个函数和区间求和十分像，这里就不出示代码了。
和区间求和不同的是回溯统计的时候，对于两个子结点的数据域不再是加和，而是位或和。
2. 区间第 K 大
给定 n 个数，每次询问问 [l,r] 区间内的第 K 大数，这个问题有很多办法，然而用线段树应该如何解决呢。
利用了线段树划分区间的思维，线段树的每个结点存的不只是区间端点，而是这个区间内所有的数，并且是依照递增程序有序排列的，建树过程是一个归并排序的过程，从叶子结点自底向上进行归并，对于一个长度为 6 的数组[4, 3, 2, 1, 5, 6]，建设线段树如图所示。
从图中能够看出，线段树的任何一个结点存储了对应区间的数，并且进行有序排列，所以根结点存储的肯定是一个长度为数组总长的有序数组，叶子结点存储的递增序列为原数组元素。
每次询问，咱们将给定区间拆分成一个个线段树上的子区间，而后二分枚举答案 T，再利用二分查找统计这些子区间中大于等于 T 的数的个数，从而确定 T 是否是第 K 大的。
对于区间 K 大数的问题，还有很多数据结构都能解决，这里仅作简略介绍。
3. 矩阵面积并
对于给定的 n(n<=100000)个平行于 XY 轴的矩形，求他们的面积并。
这是一个二维的问题，如果我通知你这道题应用线段树解决，你该如何动手呢，首先线段树是一维的，所以咱们须要化二维为一维，所以咱们能够应用 x 的坐标或者 y 的坐标建设线段树，另一坐标用来进行枚举操作。
咱们用 x 的坐标来建树的化，那么咱们把矩阵平行于 x 轴的线段舍去，则变成了
每个矩形都剩下两条边，定义 x 坐标较小的为入边（值为 +1），较大为出边（值为 -1），而后用 x 的升序，记第 i 条线段的 x 坐标即为 X[i]
接下来将所有矩形端点的 y 坐标进行重映射(也能够叫离散化)，起因是坐标有可能很大而且不肯定是整数，将原坐标映射成小范畴的整数能够作为数组下标，更不便计算，映射能够将所有 y 坐标进行排序去重，而后二分查找确定映射后的值，离散化的具体步骤下文会具体解说。如图所示，蓝色数字示意的是离散后的坐标，即 1、2、3、4 别离对应原先的 5、10、23、25（需反对正查和反查）。假如离散后的 y 方向的坐标个数为 m，则 y 方向被宰割成 m - 1 个独立单元，下文称这些独立单元为“单位线段”，别离记为 <1-2>、<2-3>、<3-4>。
以 x 坐标递增的形式枚举每条垂直线段，y 方向用一个长度为 m - 1 的数组来保护“单位线段”的权值，如图所示，展现了每条线段按 x 递增形式插入之后每个“单位线段”的权值。
当枚举到第 i 条线段时，查看所有“单位线段”的权值，所有权值大于零的“单位线段”的理论长度之和 (离散化前的长度) 被称为“非法长度”，记为 L，那么(X[i] – X[i-1]) * L，就是第 i 条线段和第 i - 1 条线段之间的矩形面积和，计算完第 i 条垂直线段后将它插入，所谓 ” 插入 ” 就是利用该线段的权值更新该线段对应的“单位线段”的权值和（这里的更新就是累加）。
如图四 -4- 6 所示：红色、黄色、蓝色三个矩形别离是 3 对相邻线段间的矩形面积和，其中红色局部的 y 方向由 <1-2>、<2-3> 两个“单位线段”组成，黄色局部的 y 方向由 <1-2>、<2-3>、<3-4> 三个“单位线段”组成，蓝色局部的 y 方向由 <2-3>、<3-4> 两个“单位线段”组成。非凡的，在计算蓝色局部的时候，<1-2> 局部的权值因为第 3 条线段的插入 (第 3 条线段权值为 -1) 而变为零，所以不能计入“非法长度”。
以上所有相邻线段之间的面积和就是最初要求的矩形面积并。
优化天然就是用线段树了，之前提到了降维的思维，x 方向咱们持续采纳枚举，而 y 方向的“单位线段”则能够采纳线段树来保护，
而后通过一个扫描线来求扫描线笼罩的 y 的长度。线段的扫描依照 x 的大小从小到大扫描，求出以后扫描线笼罩的矩阵竖线的长度，而后乘以下条线段的跨度，则为这个区域矩阵笼罩的面积，具体对于扫描线的操作这里不再论述。这里只讲明确如何建树。
五、线段树的一些重难点以及技巧
1. 离散化
离散化罕用于二维状态在一维线段树建树，所谓离散化就是将有限的个体映射到无限个体中，进步算法效率，而且反对正查和反查（从开始遍历和从开端遍历），可用 Hash 等实现。
2.Lazy_tag
这个标记就是用于线段树的区间更新，下面曾经提到，便不再累赘，然而区间更新并不局限于应用 Lazy_tag，还有一种不应用 Lazy_tag 的区间更新办法，会在进步篇中讲到。
3. 空间优化
父节点 k，左儿子 k <<1，右儿子 k <<1|1，则须要 n <<2 的空间，但咱们晓得并不是所有的叶子节点都占用到了 2 n+1 —— 4 n 的范畴，造成了大量空间节约。这时候就要思考离散化，压缩空间。或者应用 dfs 序作为结点下标，父亲 k，左儿子 k +1，右儿子 k + 左儿子区间长度 *2，具体实现不再累赘，可自行通过批改左右儿子的下标推出。
4. 多维推广
例如矩阵树，空间树，这些便是线段树的拓展，比方要在两种不同的参数找到最适变量，例如对于一个人的身高和体重，找到肯定范畴内且年龄最小的人，就能够用到多维推广了。
5. 可长久化
主席树。当前讲 = =
6. 非递归模式
后面提到过这个概念，非递归模式的某些操作会快于递归模式，当前将会专门将非递归模式。
7. 子树膨胀
就是子树继承的逆过程，继承是为了失去父节点信息，而膨胀则是在回溯时候，如果两棵子树领有雷同数据的时候在将数据传递给父结点，子树的数据清空，这样下次在拜访的时候就能够缩小拜访的结点数。
六、相干例题
- codevs 1080（单点批改 + 区间查问）
- codevs 1081（区间批改 + 单点查问）
- codevs 1082（区间批改 + 区间查问）
- codevs 3981（区间最大子段和）
- Bzoj 3813（区间内某个值是否呈现过）
- Luogu P2894（区间间断一段空的长度）
- codevs 2000（区间最长回升子序列）
- codevs 3044（矩阵面积求并）
- Hdu 1698（区间染色 + 单次统计）
- Poj 2777（区间染色 + 批量统计）
- Hdu 4419（多色矩形面积并）
- Poj 2761（区间第 K 大）
- Hdu 2305（最值保护）
主席树（可长久化线段树）
题目背景
这是个十分经典的主席树入门题——动态区间第 kk 小。
数据曾经过增强，请应用主席树。同时请留神常数优化。
题目形容
如题，给定 nn 个整数形成的序列 aa，将对于指定的闭区间 l, r 查问其区间内的第 kk 小值。
输出格局
第一行蕴含两个整数，别离示意序列的长度 nn 和查问的个数 mm。
第二行蕴含 nn 个整数，第 ii 个整数示意序列的第 ii 个元素 a_iai。
接下来 mm 行每行蕴含三个整数 l, r, kl,r,k , 示意查问区间 l, r 内的第 kk 小值。
输入格局
对于每次询问，输入一行一个整数示意答案。
输入输出样例
Input1：5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1Input2：6405
15770
26287
25957
26287阐明 / 提醒
样例 1 解释
n=5n=5，数列长度为 55，数列从第一项开始顺次为{25957, 6405, 15770, 26287, 26465}{25957,6405,15770,26287,26465}。
- 第一次查问为 2, 2 区间内的第一小值，即为 64056405。
- 第二次查问为 3, 4 区间内的第一小值，即为 1577015770。
- 第三次查问为 4, 5 区间内的第一小值，即为 2628726287。
- 第四次查问为 1, 2 区间内的第二小值，即为 2595725957。
- 第五次查问为 4, 4 区间内的第一小值，即为 2628726287。
数据规模与约定
- 对于 20% 的数据，满足 1 <= n,m <= 10;
- 对于 50% 的数据，满足 1 <=n,m <= 10^3;
- 对于 80% 的数据，满足 1 <= n,m <= 10^5;
- 对于 100% 的数据，满足 1 <= n,m <= 2 * 10^5, 1 <=l <= r <= n, 1 <= k <= r-l + 1 , ai 的绝对值 <= 10^9
解决问题
暴力法
不言而喻，最暴力的方法就是区间排序而后输入排序后第 kk 个数。最坏状况的工夫复杂度是 O(nmlgn)O(nmlgn)，不超时才怪。
主席树
https://blog.csdn.net/riba253…
于是针对这个问题，新的数据结构诞生了，也就是主席树。
主席树本名可长久化线段树，也就是说，主席树是基于线段树倒退而来的一种数据结构。其前缀”可长久化”意在给线段树减少一些历史点来保护历史数据，使得咱们能在较短时间内查问历史数据，图示如下。
图中的橙色节点为历史节点，其左边多进去的节点是新节点（批改节点）。
上面咱们来讲怎么构建这个数据结构。
主席树对点的批改
不同于一般线段树的是主席树的左右子树节点编号并不可能用计算失去，所以咱们须要记录下来，然而对应的区间还是没问题的
// 节点 o 示意区间[l,r]，批改点为 p，批改值依据题意设定（此处咱们先不谈题目，只谈数据结构）int modify(int o, int l, int r, int p)
{
int oo = ++node_cnt;
lc[oo] = lc[o]; rc[oo] = rc[o]; sum[oo] = sum[o] + 1;// 新节点，这里是依据模板题来的
if(l == r)// 递归底层返回新节点编号，批改父节点的儿子指向
{//sum[oo] = t; 如果题目要求 sum 是加 t 的再这样弄，而后下面的 + 1 就去掉
return oo;
}
int mid = (l + r) >> 1;
if(p <= mid) lc[oo] = modify(lc[oo], l, mid);
else rc[oo] = modify(rc[oo], mid+1, r);
//sum[oo] = sum[lc[oo]] + sum[rc[oo]]; 在该题中，不须要这样做，然而很多状况下是要这样更新的
return oo;
}至于主席树的区间批改，其实也不难，然而复杂度有点高，简略点的题目个别只有点批改，有时候区间批改能够转化为点批改（比方 NOIP2012 借教室，有区间批改的解法也有点批改的解法）。
主席树的询问（历史区间和）
int ql, qr;// 查问区间[l,r]
int query(int o, int l, int r)// 节点 o 代表区间[l,r]
{int ans = 0, mid = ((l + r) >> 1);
if(!o) return 0;// 不存在的子树
if(ql <= l && r <= qr) return sum[o];// 区间蕴含返回区间值
// 都是线段树规范操作，只不过是左右子树多了一个记录而已
if(ql <= mid) ans += query(lc[o], l, mid);
if(qr > mid) ans += query(rc[o], mid+1, r);
return ans;
// 点操作就不用说了
}模板题解答
模板题 [1,r] 的状况
由题意晓得咱们必定要对区间进行排序，然而咱们的排序不是每次询问才排序，是初始化就排序离散化——针对数字较大但数据较小的状况（具体见办法）。排序离散化结束后，以离散化数组建主席树，设 ii 属于区间 1,n，对原数组的 1,i 区间的数做 统计（例如下图，区间中按离散化数组程序统计 11 的个数、22 的个数、33 的个数、44 的个数、88 的个数、99 的个数），有序地插入节点到离散化数组的主席树中，记录好原数组每个节点对应的线段树终点，针对样例有几个示意图。留神，这里的橙色节点是新节点，与之前呈现的那个图不一样。
- 1,1 的状况
- 1,4 的状况
状况以此类推。
咱们依照下面的做法构建的主席树是为了不便咱们查找第 kk 小值。因为咱们是以离散数组构建的主席树，那么从根节点登程，左子树局部的数必然不大于右子树局部的数。于是就能够将左儿子的节点个数 xx 与 kk 做比拟，若 k≤xk≤x，则第 kk 小值肯定在左子树外面，若 x≤kx≤k，则第 kk 小值肯定在右子树外面，而后递归往下走，放大范畴。值得注意的是，前者递归时，kk 间接传下去即可，后者递归时，须要将 kk 减去左子树的数的个数再传递这个 kk 值。
例如咱们查找 1,4 中第 22 小的值，图示如下，绿色节点为该值存在的区间地位。
须要留神的是，第二个绿色节点才是绿色根节点的左子树，因为 左子树示意的区间是靠前的那一半 。
办法总结如下：
- 将原始数组复制一份，而后排序好，而后去掉多余的数，行将数据离散化。举荐应用 C ++ 的 STL 中的
unique函数； - 以 离散化数组 为根底，建一个全 00 的线段树，称作根底主席树；
- 对原数据中每一个 1,i 区间统计，有序地插入新节点（题目中 ii 每减少 11 就会多一个数，仅需对主席树对应的节点减少 11 即可）；
-
对于查问 1,r 中第 kk 小值的操作，找到 1,r 对应的根节点，咱们依照线段树的办法操作即可（这个根节点及其子孙形成的必然是一颗线段树）。
模板问题的解决
当初咱们真正来解决区间询问 l,r 的问题。
构建主席树的办法是没有问题的，问题正在于区间询问怎么写。其实，解决方案就是将主席树 1,r 减去主席树 1,l−1 就行了。其实这个起因并不难想，首先看到主席树的底层，全副是对数的统计。当主席树 1,r 减去主席树 1,l−1 时，统计也跟着减了，也就是说，当初统计记录的是 l,r 区间。
而咱们不须要独自减，只须要边递归查问边减，具体见查问局部代码。
// 初始的 u 和 v 别离代表的是点 l - 1 和点 r，l 和 r 别离示意线段树点代表的区间，初始的 k 如题
int query(int u, int v, int l, int r, int k)
{int ans, mid = ((l + r) >> 1), x = sum[lc[v]] - sum[lc[u]];
// 因为主席树是区间统计好了的，只有减一下即可，无需递归到叶子再解决
if(l == r)// 找到指标地位
return l;
if(x >= k) ans = query(lc[u], lc[v], l, mid, k);
else ans = query(rc[u], rc[v], mid+1, r, k-x);// 右子树记得扭转 k 的值
return ans;
}模板问题的 Code
#include <cstdio>
#include <algorithm>
#define M 200010
using namespace std;
int node_cnt, n, m;
int sum[M<<5], rt[M], lc[M<<5], rc[M<<5];// 线段树相干
int a[M], b[M];// 原序列和离散序列
int p;// 批改点
void build(int &t, int l, int r)
{
t = ++node_cnt;
if(l == r)
return;
int mid = (l + r) >> 1;
build(lc[t], l, mid);
build(rc[t], mid+1, r);
}
int modify(int o, int l, int r)
{
int oo = ++node_cnt;
lc[oo] = lc[o]; rc[oo] = rc[o]; sum[oo] = sum[o] + 1;
if(l == r)
return oo;
int mid = (l + r) >> 1;
if(p <= mid) lc[oo] = modify(lc[oo], l, mid);
else rc[oo] = modify(rc[oo], mid+1, r);
return oo;
}
int query(int u, int v, int l, int r, int k)
{int ans, mid = ((l + r) >> 1), x = sum[lc[v]] - sum[lc[u]];
if(l == r)
return l;
if(x >= k) ans = query(lc[u], lc[v], l, mid, k);
else ans = query(rc[u], rc[v], mid+1, r, k-x);
return ans;
}
int main()
{
int l, r, k, q, ans;
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; i += 1)
scanf("%d", &a[i]), b[i] = a[i];
sort(b+1, b+n+1);
q = unique(b+1, b+n+1) - b - 1;
build(rt[0], 1, q);
for(register int i = 1; i <= n; i += 1)
{p = lower_bound(b+1, b+q+1, a[i])-b;// 能够视为查找最小下标的匹配值，外围算法是二分查找
rt[i] = modify(rt[i-1], 1, q);
}
while(m--)
{scanf("%d%d%d", &l, &r, &k);
ans = query(rt[l-1], rt[r], 1, q, k);
printf("%d\n", b[ans]);
}
return 0;
}复杂度剖析
题目一开始的离散化复杂度为 O(nlgn)O(nlgn)，构建根底主席树复杂度为 O(nlgn)O(nlgn)，统计并插入的复杂度是 O(nlgn+nlgn)=O(nlgn)O(nlgn+nlgn)=O(nlgn)，询问的复杂度是 O(mlgn)O(mlgn)。复杂度总和就是 O((m+n)lgn)O((m+n)lgn)。
前缀树和后缀树
前缀树（字典树）
https://blog.csdn.net/weixin_…
什么是 Trie 树
Trie 树，即前缀树，又称单词查找树，字典树，是一种树形构造，是一种哈希树的变种。典型利用是用于统计和排序大量的字符串（但不仅限于字符串），所以常常被搜索引擎零碎用于文本词频统计。
Trie 树的核心思想是空间换工夫，利用字符串的公共前缀来升高查问工夫的开销以达到提高效率的目标。它的长处是：最大限度地缩小无谓的字符串比拟，查问效率比哈希表高。
它有 3 个根本性质：
根节点不蕴含字符，除根节点外每一个节点都只蕴含一个字符。
从根节点到某一节点，门路上通过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点蕴含的字符都不雷同。
树的构建与查问
依据一个例子来形容 trie 树的构建：
题目：给定 100000 个长度不超过 10 的单词，判断每一个单词是否呈现过，如果呈现过，给出第一次呈现的地位。
思路：如果对每一个单词都遍历整个单词序列，那么工夫复杂度就是 O(n2)O(n^2)O(n
2
)，单词序列的长度是 100000，显然这样的工夫复杂度代价太高了。然而思考 100000 个单词必定有一些字符串的反复，trie 树，即前缀树来解决这个问题最失当不过了。一个前缀树的模式是什么样的呢？
假如有 abc，abd，bcd，efg，hii，那么咱们构建如下一个树结构用于示意这些单词：
然而结构一个前缀树就是为了使遍历那些有雷同的前缀的单词时更疾速，目前这个多叉树上从根节点到叶节点每一条门路都是一个单词，如果咱们减少了单词 b，abcd 两个单词呢，还是这样一条路走到黑，咱们无奈辨别字母短的单词是否曾经存储过，为了解决这个问题，咱们能够在节点上记录信息，比方如果达到该字母后单词结尾，咱们就在时候的节点上记录 end+1，这样就能够晓得有几个以该前缀结尾的单词，批改之后构造如下：
这是咱们能够很显著看进去如最右边一条门路上，有一个单词是 abc，一个单词是 abcd。依据新增加的信息，咱们能够晓得所有字符串中有多少个该字符串，如果当初有另外一个问题，我想晓得所有字符串中有多少个以该字符串作为前缀，那是不是得遍历该条门路前面的节点，将所有的 end 加起来。为了简略，咱们依然能够在节点中多存入一个信息，每个节点被划过了多少次，也就是在建设多叉树的时候就记录了以所有字符串中有多少个以某字符串作为前缀，划过的次数就是这个值。调整后构造如下：注：在 C ++ 实现局部，图中所有的 S 都加 1，单词自身也是以他本人作为前缀的。
回到最后的题目，这样的构造能够依据节点的信息失去一个单词时候呈现过（End>0），然而有一个要求咱们没有满足，那就是如果存在这个单词咱们如何返回这个单词在原来列表中的地位呢？依据后面介绍的多叉树结构的介绍，我想这个问题也很容易解决，节点中咱们再多存入一些信息就能够，对于非结尾字符 End=0，不须要存储其余的信息，对于结尾字符 End>0，此时再存入信息，标注该单词在 100000 个单词词表中的地位，构建查问多叉树的时候就能够间接返回这个地位信息了。
Trieste 树的利用
节选自此文：[海量数据处理面试题集锦与 Bit-map 详解]
(https://blog.csdn.net/v_july_…
除了本文引言处所述的问题能利用 Trie 树解决之外，Trie 树还能解决下述问题
3、有一个 1G 大小的一个文件，外面每一行是一个词，词的大小不超过 16 字节，内存限度大小是 1M。返回频数最高的 100 个词。
9、1000 万字符串，其中有些是反复的，须要把反复的全副去掉，保留没有反复的字符串。请怎么设计和实现？
10、一个文本文件，大概有一万行，每行一个词，要求统计出其中最频繁呈现的前 10 个词，请给出思维，给出工夫复杂度剖析。
13、寻找热门查问：搜索引擎会通过日志文件把用户每次检索应用的所有检索串都记录下来，每个查问串的长度为 1 -255 字节。假如目前有一千万个记录，这些查问串的反复读比拟高，尽管总数是 1 千万，然而如果去除反复和，不超过 3 百万个。一个查问串的反复度越高，阐明查问它的用户越多，也就越热门。请你统计最热门的 10 个查问串，要求应用的内存不能超过 1G。
(1) 请形容你解决这个问题的思路；
(2) 请给出次要的解决流程，算法，以及算法的复杂度。
C++ 实现
解决无关字符串的一些问题：
一个字符串类型的数组 arr1，另一个字符串类型的数组 arr2。
arr2 中有哪些字符串，是 arr1 中呈现的？请打印
arr2 中有哪些字符串，是作为 arr1 中某个字符串前缀呈现的？请打印
arr2 中有哪些字符串，是作为 arr1 中某个字符串前缀呈现的？请打印 arr2 中呈现次数最大的前缀。
#include <iostream>
#include <string>
#include <string.h>
using namespace std;
const int MaxBranchNum = 26;// 能够扩大
class TrieNode{
public:
string word;
int path; // 该字符被划过多少次，用以统计以该字符串作为前缀的字符串的个数
int End; // 以该字符结尾的字符串
TrieNode* nexts[MaxBranchNum];
TrieNode()
{
word = "";
path = 0;
End = 0;
memset(nexts,NULL,sizeof(TrieNode*) * MaxBranchNum);
}
};
class TrieTree{
private:
TrieNode *root;
public:
TrieTree();
~TrieTree();
// 插入字符串 str
void insert(string str);
// 查问字符串 str 是否呈现过，并返回作为前缀几次
int search(string str);
// 删除字符串 str
void Delete(string str);
void destory(TrieNode* root);
// 打印树中的所有节点
void printAll();
// 打印以 str 作为前缀的单词
void printPre(string str);
// 依照字典程序输入以 root 为根的所有单词
void Print(TrieNode* root);
// 返回以 str 为前缀的单词的个数
int prefixNumbers(string str);
};
TrieTree::TrieTree()
{root = new TrieNode();
}
TrieTree::~TrieTree()
{destory(root);
}
void TrieTree::destory(TrieNode* root)
{if(root == nullptr)
return ;
for(int i=0;i<MaxBranchNum;i++)
{destory(root->nexts[i]);
}
delete root;
root = nullptr;
}
void TrieTree::insert(string str)
{if(str == "")
return ;
char buf[str.size()];
strcpy(buf, str.c_str());
TrieNode* node = root;
int index = 0;
for(int i=0; i<strlen(buf); i++)
{index = buf[i] - 'a';
if(node->nexts[index] == nullptr)
{node->nexts[index] = new TrieNode();}
node = node->nexts[index];
node->path++;// 有一条门路划过这个节点
}
node->End++;
node->word = str;
}
int TrieTree::search(string str)
{if(str == "")
return 0;
char buf[str.size()];
strcpy(buf, str.c_str());
TrieNode* node = root;
int index = 0;
for(int i=0;i<strlen(buf);i++)
{index = buf[i] - 'a';
if(node->nexts[index] == nullptr)
{return 0;}
node = node->nexts[index];
}
if(node != nullptr)
{return node->End;}else
{return 0;}
}
void TrieTree::Delete(string str)
{if(str == "")
return ;
char buf[str.size()];
strcpy(buf, str.c_str());
TrieNode* node = root;
TrieNode* tmp;
int index = 0;
for(int i = 0 ; i<str.size();i++)
{index = buf[i] - 'a';
tmp = node->nexts[index];
if(--node->nexts[index]->path == 0)
{delete node->nexts[index];
}
node = tmp;
}
node->End--;
}
int TrieTree::prefixNumbers(string str)
{if(str == "")
return 0;
char buf[str.size()];
strcpy(buf, str.c_str());
TrieNode* node = root;
int index = 0;
for(int i=0;i<strlen(buf);i++)
{index = buf[i] - 'a';
if(node->nexts[index] == nullptr)
{return 0;}
node = node->nexts[index];
}
return node->path;
}
void TrieTree::printPre(string str)
{if(str == "")
return ;
char buf[str.size()];
strcpy(buf, str.c_str());
TrieNode* node = root;
int index = 0;
for(int i=0;i<strlen(buf);i++)
{index = buf[i] - 'a';
if(node->nexts[index] == nullptr)
{return ;}
node = node->nexts[index];
}
Print(node);
}
void TrieTree::Print(TrieNode* node)
{if(node == nullptr)
return ;
if(node->word != "")
{cout<<node->word<<" "<<node->path<<endl;}
for(int i = 0;i<MaxBranchNum;i++)
{Print(node->nexts[i]);
}
}
void TrieTree::printAll()
{Print(root);
}
int main()
{
cout << "Hello world!" << endl;
TrieTree trie;
string str = "li";
cout<<trie.search(str)<<endl;
trie.insert(str);
cout<<trie.search(str)<<endl;
trie.Delete(str);
cout<<trie.search(str)<<endl;
trie.insert(str);
cout<<trie.search(str)<<endl;
trie.insert(str);
cout<<trie.search(str)<<endl;
trie.Delete("li");
cout<<trie.search(str)<<endl;
trie.Delete("li");
cout<<trie.search(str)<<endl;
trie.insert("lia");
trie.insert("lic");
trie.insert("liab");
trie.insert("liad");
trie.Delete("lia");
cout<<trie.search("lia")<<endl;
cout<<trie.prefixNumbers("lia")<<endl;
return 0;
}
后缀树
https://blog.csdn.net/v_JULY_v/article/details/6897097?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159434584019195265900582%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=159434584019195265900582&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v1~rank_blog_v1-1-6897097.pc_v1_rank_blog_v1&utm_term=%E5%90%8E%E7%BC%80%E6%A0%91
定义
后缀树（Suffix tree）是一种数据结构，能疾速解决很多对于字符串的问题。后缀树的概念最早由 Weiner 于 1973 年提出，既而由 McCreight 在 1976 年和 Ukkonen 在 1992 年和 1995 年加以改进欠缺。
后缀，顾名思义，甚至艰深点来说，就是所谓后缀就是前面尾巴的意思。比如说给定一长度为 n 的字符串 S =S1S2..Si..Sn，和整数 i，1 <= i <= n，子串 SiSi+1…Sn 便都是字符串 S 的后缀。
以字符串 S =XMADAMYX 为例，它的长度为 8，所以 S[1..8], S[2..8], … , S[8..8]都算 S 的后缀，咱们个别还把空字串也算成后缀。这样，咱们一共有如下后缀。对于后缀 S[i..n]，咱们说这项后缀起始于 i。
S[1..8], XMADAMYX，也就是字符串自身，起始地位为 1
S[2..8], MADAMYX，起始地位为 2
S[3..8], ADAMYX，起始地位为 3
S[4..8], DAMYX，起始地位为 4
S[5..8], AMYX，起始地位为 5
S[6..8], MYX，起始地位为 6
S[7..8], YX，起始地位为 7
S[8..8], X，起始地位为 8
空字串，记为 $。而后缀树，就是蕴含一则字符串所有后缀的压缩 Trie。把下面的后缀退出 Trie 后，咱们失去上面的构造：
仔细观察上图，咱们能够看到不少值得压缩的中央。比方蓝框标注的分支都是独苗，没有必要用独自的节点同边示意。如果咱们容许任意一条边里蕴含多个字 母，就能够把这种没有分叉的门路压缩到一条边。另外每条边曾经蕴含了足够的后缀信息，咱们就不必再给节点标注字符串信息了。咱们只须要在叶节点上标注上每项后缀的起始地位。于是咱们失去下图：
这样的构造失落了某些后缀。比方后缀 X 在上图中隐没了，因为它正好是字符串 XMADAMYX 的前缀。为了防止这种状况，咱们也规定每项后缀不能是其它后缀的前缀。要解决这个问题其实挺简略，在待处理的子串后加一个空字串就行了。例如咱们解决 XMADAMYX 前，先把 XMADAMYX 变为 XMADAMYX$，于是就失去 suffix tree– 后缀树了，如下图所示：
后缀树与回文问题的关联
最低共有先人，LCA（Lowest Common Ancestor)，也就是任意两节点（多个也行）最长的共有前缀。比方下图中，节点 7 同节点 1 的独特先人是节点 5 与节点 10，但最低独特先人是 5。查找 LCA 的算法是 O(1)的复杂度，当然，代价是须要对后缀树做复杂度为 O(n)的预处理。
.png](/img/bVbJknm)
狭义后缀树(Generalized Suffix Tree)。传统的后缀树解决一坨单词的所有后缀。狭义后缀树存储任意多个单词的所有后缀。例如下图是单词 XMADAMYX 与 XYMADAMX 的狭义后缀 树。留神咱们须要辨别不同单词的后缀，所以叶节点用不同的特殊符号与后缀地位配对。
最长回文问题
有了下面的概念，本文引言中提出的查找最长回文问题就绝对简略了。咱们来回顾下引言中提出的回文问题的具体形容：找出给定字符串里的最长回文。例如输出 XMADAMYX，则输入 MADAM。
思维的突破点在于考查回文的半径，而不是回文自身。所谓半径，就是回文对折后的字串。比方回文 MADAM 的半径为 MAD，半径长度为 3，半径的核心是字母 D。显然，最长回文必有最长半径，且两条半径相等。还是以 MADAM 为例，以 D 为核心往左，咱们失去半径 DAM；以 D 为核心向右，咱们失去半径 DAM。二者必定相等。因为 MADAM 曾经是单词 XMADAMYX 里的最长回文，咱们能够必定从 D 往左数的字串 DAMX 与从 D 往右数的子串 DAMYX 共享最长前缀 DAM。而这，正是解决回文问题的要害。当初咱们有后缀树，怎么把从 D 向左数的字串 DAMX 变成后缀 呢？到这个境地，答案应该显著：把单词 XMADAMYX 翻转（XMADAMYX=>XYMADAMX，DAMX 就变成后缀了）就行了。于是咱们把寻找回文的问题转换成了寻找两坨后缀的 LCA 的问题。当然，咱们还须要晓得 到底查问那些后缀间的 LCA。很简略，给定字符串 S，如果最长回文的核心在 i，那从地位 i 向右数的后缀刚好是 S(i)，而向左数的字符串刚好是翻转 S 后失去的字符串 S‘的后缀 S'(n-i+1)。这里的 n 是字符串 S 的长度。
可能下面的论述还不够直观，我再细细阐明下：
1、首先，还记得本第二局部结尾对于后缀树的定义么：“先说说后缀的定义，顾名思义，甚至艰深点来说，就是所谓后缀就是前面尾巴的意思。比如说给定一长度为 n 的字符串 S =S1S2..Si..Sn，和整数 i，1 <= i <= n，子串 SiSi+1…Sn 便都是字符串 S 的后缀。”
以字符串 S =XMADAMYX 为例，它的长度为 8，所以 S[1..8], S[2..8], … , S[8..8]都算 S 的后缀，咱们个别还把空字串也算成后缀。这样，咱们一共有如下后缀。对于后缀 S[i..n]，咱们说这项后缀起始于 i。
S[1..8], XMADAMYX，也就是字符串自身，起始地位为 1
S[2..8], MADAMYX，起始地位为 2
S[3..8], ADAMYX，起始地位为 3
S[4..8], DAMYX，起始地位为 4
S[5..8], AMYX，起始地位为 5
S[6..8], MYX，起始地位为 6
S[7..8], YX，起始地位为 7
S[8..8], X，起始地位为 8
空字串，记为 $。2、对单词 XMADAMYX 而言，回文核心为 D，那么 D 向右的后缀 DAMYX 假如是 S(i)（当 N =8，i 从 1 开始计数，i= 4 时，便是 S(4..8)）; 而对于翻转后的单词 XYMADAMX 而言，回文核心 D 向右对应的后缀为 DAMX，也就是 S'(N-i+1)(（N=8，i=4，便是 S‘（5..8））。此刻曾经能够得出，它们共享最长前缀，即 LCA（DAMYX，DAMX）=DAM。有了这套直观解释，算法天然跃然纸上：
预处理后缀树，使得查问 LCA 的复杂度为 O(1)。这步的开销是 O(N)，N 是单词 S 的长度；
对单词的每一地位 i(也就是从 0 到 N -1)，获取 LCA(S(i), S‘(N-i+1)) 以及 LCA(S(i+1), S’(n-i+1))。查找两次的起因是咱们须要思考奇数回文和偶数回文的状况。这步要考查每坨 i，所以复杂度是 O(N)；
找到最大的 LCA，咱们也就失去了回文的核心 i 以及回文的半径长度，天然也就失去了最长回文。总的复杂度 O(n)。
用上图做例子，i 为 4 时，LCA(4$, 5#)为 DAM，正好是最长半径。当然，这只是直观的叙述。下面大抵形容了后缀树的基本思路。要想写出实用代码，至多还得晓得上面的常识：创立后缀树的 O(n)算法。此算法有很多种，无论 Peter Weiner 的 73 年年度最佳算法，还是 Edward McCreight1976 的改良算法，还是 1995 年 E. Ukkonen 大幅简化的算法（本文第 4 局部将重点论述这种办法），还是 Juha Kärkkäinen 和 Peter Sanders2003 年进一步简化的线性算法，都是 O（n）的工夫复杂度。至于理论中具体抉择哪一种算法，可依理论状况而定。
实现后缀树用的数据结构。比方罕用的子结点加兄弟节点列表，Directed 优化后缀树空间的方法。比方不存储子串，而存储读取子串必须的地位。以及 Directed Acyclic Word Graph，常缩写为黑哥哥们挂在嘴边的 DAWG。
后缀树的利用
后缀树的用处，总结起来大略有如下几种
1. 查找字符串 o 是否在字符串 S 中。
计划：用 S 结构后缀树，按在 trie 中搜寻字串的办法搜寻 o 即可。
原理：若 o 在 S 中，则 o 必然是 S 的某个后缀的前缀。
例如 S: leconte，查找 o: con 是否在 S 中, 则 o(con)必然是 S(leconte)的后缀之一 conte 的前缀. 有了这个前提，采纳 trie 搜寻的办法就不难理解了。
2. 指定字符串 T 在字符串 S 中的反复次数。
计划：用 S +’{Ctrl+5}’ 结构后缀树，搜寻 T 节点下的叶节点数目即为反复次数
原理：如果 T 在 S 中反复了两次，则 S 应有两个后缀以 T 为前缀，反复次数就天然统计进去了。
3. 字符串 S 中的最长反复子串
计划：原理同 2，具体做法就是找到最深的非叶节点。
这个深是指从 root 所经验过的字符个数，最深非叶节点所经验的字符串起来就是最长反复子串。
为什么要非叶节点呢? 因为既然是要反复，当然叶节点个数要 >=2。
4. 两个字符串 S1，S2 的最长公共局部
计划：将 S1#S2{Ctrl+5}作为字符串压入后缀树，找到最深的非叶节点，且该节点的叶节点既有 #也有 $(无#)。
【留神 && 解释】{Ctrl+5}是 dollar 符号的意思，打进去这个符号会有显示谬误，奈何电脑卡炸，已无心解决 …. 真应该分成高低。
后缀树的结构
借助后缀树的个性, 咱们能够做出一个相当无效的算法. 首先一个重要的个性是: 一朝为叶, 终生为叶. 一个叶节点自诞生当前绝不会有子孙. 更重要的是, 每当咱们往树上退出一个新的前缀, 每一条通往叶节点的边都会缩短一个字符(新前缀的最初一个字符). 这使得解决通往叶节点的边变得异样简略, 咱们齐全能够在创立叶节点的时候就把以后字符到文本末的所有字符一股脑塞进去. 是的, 咱们不须要晓得前面的字符是啥, 但咱们晓得它们最终都要被加进去. 因而, 一个叶节点诞生的时候, 也正是它能够被咱们忘记的时候. 你可能会放心通往叶节点的边被宰割了怎么办, 那也不要紧, 宰割之后只是终点变了, 尾部该怎么着还是怎么着.
如此一来, 咱们只须要关怀显式节点和隐式节点上的更新.
还要提到一个节约工夫的办法. 当咱们遍历所有后缀时, 如果某个后缀的某个儿子跟待加字符 (新前缀最初一个字符) 雷同, 那么咱们以后前缀的所有更新就能够进行了. 如果你了解了后缀树的实质, 你会晓得一旦待加字符跟某个后缀的某个儿子雷同, 那么更短的后缀必然也有这个儿子. 咱们无妨把首个这样的节点定义为完结节点. 比完结节点长的后缀必然是叶节点, 这一点很好解释, 要么原本就是叶节点, 要么就是新创建的节点(新创建的必然是叶节点). 这意味着, 每一个前缀更新完之后, 以后的完结节点将成为下一轮更新的激活节点.
伪代码：
Update(新前缀)
{
以后后缀 = 激活节点
待加字符 = 新前缀最初一个字符done = false;while (!done) {
if (以后后缀在显式节点完结)
{if (以后节点后没有以待加字符开始的边) 在以后节点后创立一个新的叶节点 else done = true;} else {
if (以后隐式节点的下一个字符不是待加字符) { 从隐式节点后宰割此边 在宰割处创立一个新的叶节点 } else done = true; if (以后后缀是空后缀) done = true; else 以后后缀 = 下一个更短的后缀 }激活节点 = 以后后缀
}
后缀指针
下面的伪代码看上去很完满, 但它覆盖了一个问题. 留神到第 21 行,“下一个更短的后缀”, 如果板滞地沿着树枝去搜寻咱们想要的后缀, 那这种算法就不是线性的了. 要解决此问题, 咱们得附加一种指针: 后缀指针. 后缀指针存在于每个完结在非叶节点的后缀上, 它指向“下一个更短的后缀”. 即, 如果一个后缀示意文本的第 0 到第 N 个字符, 那么它的后缀指针指向的节点示意文本的第 1 到第 N 个字符.
图 8 是文本 ABABABC 的后缀树. 第一个后缀指针在示意 ABAB 的节点上. ABAB 的后缀指针指向示意 BAB 的节点. 同样地, BAB 也有它的后缀指针, 指向 AB. 如此这般.
加上后缀指针 (虚线) 的 ABABABC 的后缀树
介绍一下如何创立后缀指针. 后缀指针的创立是跟后缀树的更新同步的. 随着咱们从激活节点挪动到完结节点, 我把每个新的叶节点的父亲的门路保留下来. 每当创立一条新边, 我同时也在上一个叶节点的父亲那儿创立一个后缀指针来指向以后新边开始的节点. (显然, 咱们不能在第一条新边上做这样的操作, 但除此之外都能够这么做.)
有了后缀指针, 就能够不便地一个后缀跳到另一个后缀. 这个关键性的附加品使得算法的工夫下限胜利降为 O(N)。
无关字符串的一个总结
AC 自动机
https://blog.csdn.net/hgqqtql…
https://blog.csdn.net/liu9402…
简介
AC 自动机：Aho-Corasickautomation，该算法在 1975 年产生于贝尔实验室，是驰名的多模匹配算法之一。一个常见的例子就是给出 n 个单词，再给出一段蕴含 m 个字符的文章，让你找出有多少个单词在文章里呈现过。要搞懂 AC 自动机，先得有模式树（字典树）Trie 和 KMP 模式匹配算法的基础知识。AC 自动机算法分为 3 步：结构一棵 Trie 树，结构失败指针和模式匹配过程。
AC 自动机 (Aho-Corasick automaton) 是用来解决多模式匹配问题的。
根本可认为是 TrieTree+KMP。其中 KMP 是一种单模式匹配算法。
AC 自动机的结构要点是失败指针的设置，用于匹配失败时跳转到另一节点持续匹配。同时在匹配的过程中也用来检索其余“同尾”的模式。
结构过程
应用 Aho-Corasick 算法须要三步：
建设模式串的 Trie
给 Trie 增加失败门路
依据 AC 自动机，搜寻待处理的文本
咱们以上面这个例子来介绍 AC 自动机的运作过程
这里以 hdu 2222 KeywordsSearch 这一道题最为例子进行解说，其中测试数据如下：
给定 5 个单词：say she shr he her，而后给定一个字符串 yasherhs。问一共有多少单词在这个字符串中呈现过。
确定数据结构
struct Node
{
int cnt;// 是否为该单词的最初一个结点
Node *fail;// 失败指针
Node *next[26];//Trie 中每个结点的各个节点
}*queue[500005];// 队列，不便用 BFS 结构失败指针
char s[1000005];// 主字符串
char keyword[55];// 须要查找的单词
int head,tail;
Node *root;// 头结点
第一步构建 Trie 树
依据输出的 keyword 一 一 构建在 Trie 树中
void Build_trie(char *keyword)// 构建 Trie 树
{
Node *p,*q;
int i,v;
int len=strlen(keyword);
for(i=0,p=root;i<len;i++)
{v=keyword[i]-'a';
if(p->next[v]==NULL)
{q=(struct Node *)malloc(sizeof(Node));
Init(q);
p->next[v]=q;// 结点链接
}
p=p->next[v];// 指针挪动到下一个结点
}
p->cnt++;// 单词最初一个结点 cnt++，代表一个单词
}
失败指针的设置
用 BFS。
对于每个节点，咱们能够这样解决：设这个节点上的字母为 C，沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也有字母为 C 的节点。而后把以后节点的失败指针指向那个字目也为 C 的儿子。如果始终走到了 root 都没找到，那就把失败指针指向 root。
最开始，咱们把 root 退出队列(root 的失败指针显然指向本人)，这当前咱们每解决一个点，就把它的所有儿子退出队列，直到全副设置结束。
要点 1：root 的孩子的那一层比拟非凡，若依照上述算法，它们的失败指针会指向本人，这会在匹配的过程中导致死循环。显然 root 的子节点的失败指针应指向 root，咱们应答这一层独自解决。
要点 2：沿着父节点的失败指针走到 root 之后并不是立刻将子节点的失败指针设置为 root，而是在 root 的子节点中找寻字母为 C 的节点，将它设置为失败指针。若没有才设置为 root。这样不会失落模式只有一个字母的状况。
构建失败指针是 AC 自动机的关键所在，能够说，若没有失败指针，所谓的 AC 自动机只不过是 Trie 树而已。
失败指针原理：
构建失败指针，使以后字符失配时跳转到另一段从 root 开始每一个字符都与以后已匹配字符段某一个后缀完全相同且长度最大的地位持续匹配，如同 KMP 算法一样，AC 自动机在匹配时如果以后字符串匹配失败，那么利用失配指针进行跳转。由此可知如果跳转，跳转后的串的前缀必为跳转前的模式串的后缀，并且跳转的新地位的深度（匹配字符个数）肯定小于跳之前的节点（跳转后匹配字符数不可能大于跳转前，否则无奈保障跳转后的序列的前缀与跳转前的序列的后缀匹配）。所以能够利用 BFS 在 Trie 上进行失败指针求解。
失败指针利用：
如果以后指针在某一字符 s[m+1]处失配，即 (p->next[s[m+1]]==NULL)，则阐明没有单词 s[1…m+1] 存在，此时，如果以后指针的失配指针指向 root，则阐明以后序列的任何后缀不是是某个单词的前缀，如果指针的失配指针不指向 root，则阐明以后序列 s[i…m]是某一单词的前缀，于是跳转到以后指针的失配指针，以 s[i…m]为前缀持续匹配 s[m+1]。
对于曾经失去的序列 s[1…m]，因为 s[i…m]可能是某单词的后缀，s[1…j]可能是某单词的前缀，所以 s[1…m]中可能会呈现单词，然而以后指针的地位是确定的，不能挪动，咱们就须要 temp 长期指针，令 temp= 以后指针，而后顺次测试 s[1…m],s[i…m]是否是单词。
简略来说，失败指针的作用就是将主串某一位之前的所有能够与模式串匹配的单词疾速在 Trie 树中找出。
第二步 构建失败指针
在结构完 Tire 树之后，接下去的工作就是结构失败指针。结构失败指针的过程概括起来就一句话：设这个节点上的字母为 C，沿着它父亲节点的失败指针走，直到走到一个节点，它的子结点中也有字母为 C 的节点。而后把以后节点的失败指针指向那个字母也为 C 的儿子。如果始终走到了 root 都没找到，那就把失败指针指向 root。具体操作起来只须要：先把 root 退出队列 (root 的失败指针指向本人或者 NULL)，这当前咱们每解决一个点，就把它的所有儿子退出队列。
察看结构失败指针的流程：对照图来看，首先 root 的 fail 指针指向 NULL，而后 root 入队，进入循环。从队列中弹出 root，root 节点与 s,h 节点相连，因为它们是第一层的字符，必定没有比它层数更小的独特前后缀，所以把这 2 个节点的失败指针指向 root，并且先后进入队列，失败指针的指向对应图中的 (1)，(2) 两条虚线；从队列中先弹出 h(左边那个)，h 所连的只有 e 结点，所以接下来扫描指针指向 e 节点的父节点 h 节点的 fail 指针指向的节点，也就是 root，root->next[‘e’]==NULL, 并且 root->fail==NULL, 阐明匹配序列为空，则把节点 e 的 fail 指针指向 root, 对应图中的 (3), 而后节点 e 进入队列；从队列中弹出 s，s 节点与 a,h(右边那个) 相连，先遍历到 a 节点，扫描指针指向 a 节点的父节点 s 节点的 fail 指针指向的节点，也就是 root，root->next[‘a’]==NULL, 并且 root->fail==NULL, 阐明匹配序列为空, 则把节点 a 的 fail 指针指向 root, 对应图中的(4), 而后节点 a 进入队列。接着遍历到 h 节点，扫描指针指向 h 节点的父节点 s 节点的 fail 指针指向的节点，也就是 root，root->next[‘h’]!=NULL, 所以把节点 h 的 fail 指针指向左边那个 h, 对应图中的(5), 而后节点 h 进入队列 … 由此类推，最终失配指针如图所示
void Build_AC_automation(Node *root)
{
head=0,tail=0;// 队列头、尾指针
queue[head++]=root;// 先将 root 入队
while(head!=tail)
{
Node *p=NULL;
Node *temp=queue[tail++];// 弹出队头结点
for(int i=0;i<26;i++)
{if(temp->next[i]!=NULL)// 找到理论存在的字符结点
{//temp->next[i] 为该结点，temp 为其父结点
if(temp==root)// 若是第一层中的字符结点，则把该结点的失败指针指向 root
temp->next[i]->fail=root;
else
{// 顺次回溯该节点的父节点的失败指针直到某节点的 next[i]与该节点雷同，// 则把该节点的失败指针指向该 next[i]节点；// 若回溯到 root 都没有找到，则该节点的失败指针指向 root
p=temp->fail;// 将该结点的父结点的失败指针给 p
while(p!=NULL)
{if(p->next[i]!=NULL)
{temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
// 让该结点的失败指针也指向 root
if(p==NULL)
temp->next[i]->fail=root;
}
queue[head++]=temp->next[i];// 每解决一个结点，都让该结点的所有孩子顺次入队
}
}
}
}
显然咱们在构建失败指针的时候都是从以后节点的父节点的失败指针登程，因为 Trie 树将所有单词中雷同前缀压缩在了一起，所以所有失败指针都不可能平级跳转（达到另一个与本人深度雷同的节点），因为如果平级跳转，很显然跳转所达到的那个节点必定不是以后匹配到的字符串的后缀的一部分，否则那两个节点会合为一个，所以跳转只能达到比以后深度小的节点，又因为是由以后节点父节点开始的跳转，所以这样就能够保障从 root 到所跳转到地位的那一段字符串长度小于以后匹配到的字符串长度。另一方面，咱们能够类比 KMP 求 NEXT 数组时求最大匹配数量的思维，那种思维在 AC 自动机中的体现就是当构建失败指针时一直地回到之前的跳转地位，而后判断跳转地位的下一个字符是否蕴含以后字符，如果是就将失败指针与那个跳转地位连贯，如果跳转地位指向 NULL 就阐明以后匹配的字符在以后深度之前没有呈现过，无奈与任何跳转地位匹配，而若是找到了第一个跳转地位的下一个字符蕴含以后字符的的跳转地位，则必然取到了最大的长度，这是因为其余的以后正在匹配的字符必然在第一个跳转地位的下一个字符蕴含以后字符的的跳转地位深度之上，而那样的跳转地位就算能够，也不会是最大的（最初一个字符的深度比以后找到的第一个可行的跳转地位的最初一个字符的深度小，串必然更短一些）。
匹配过程
最初，咱们便能够在 AC 自动机上查找模式串中呈现过哪些单词了。匹配过程分两种状况：(1)以后字符匹配，示意从以后节点沿着树边有一条门路能够达到指标字符，此时只需沿该门路走向下一个节点持续匹配即可，指标字符串指针移向下个字符持续匹配；(2)以后字符不匹配，则去以后节点失败指针所指向的字符持续匹配，匹配过程随着指针指向 root 完结。反复这 2 个过程中的任意一个，直到模式串走到结尾为止。
对例子来说：其中模式串为 yasherhs。对于 i =0,1。Trie 中没有对应的门路，故不做任何操作；i=2,3,4 时，指针 p 走到左下节点 e。因为节点 e 的 count 信息为 1，所以 cnt+1，并且讲节点 e 的 count 值设置为 -1，示意改单词曾经呈现过了，避免反复计数，最初 temp 指向 e 节点的失败指针所指向的节点持续查找，以此类推，最初 temp 指向 root，退出 while 循环，这个过程中 count 减少了 2。示意找到了 2 个单词 she 和 he。当 i = 5 时，程序进入第 5 行，p 指向其失败指针的节点，也就是左边那个 e 节点，随后在第 6 行指向 r 节点，r 节点的 count 值为 1，从而 count+1，循环直到 temp 指向 root 为止。最初 i =6,7 时，找不到任何匹配，匹配过程完结。
一开始，Trie 中有一个指针 t1 指向 root，待匹配串中有一个指针 t2 指向串头。
接下来的操作和 KMP 很类似：
若：t2 指向的字母，是 Trie 树中，t1 指向的节点的儿子，那么
①t2+1,t1 改为那个儿子的编号
②如果 t1 所在的点能够顺着失败指针走到一个绿色点（指 TrieTree 中单词结尾字母对应的节点），那么以那个绿点结尾的单词就算呈现过了。
否则：t1 顺这以后节点的失败指针向上找，直到 t2 是 t1 的一个儿子，或者 t1 指向根。如果 t1 路过了一个绿色的点，那么以这个点结尾的单词就算呈现过了。
int query(Node *root)
{ // i 为主串指针，p 为模式串指针
int i,v,count=0;
Node *p=root;
int len=strlen(s);
for(i=0;i<len;i++)
{v=s[i]-'a';
// 由失败指针回溯查找，判断 s[i]是否存在于 Trie 树中
while(p->next[v]==NULL && p!=root)
p=p->fail;
p=p->next[v];// 找到后 p 指针指向该结点
if(p==NULL)// 若指针返回为空，则没有找到与之匹配的字符
p=root;
Node *temp=p;// 匹配该结点后，沿其失败指针回溯，判断其它结点是否匹配
while(temp!=root)// 匹配完结管制
{if(temp->cnt>=0)// 判断该结点是否被拜访
{
count+=temp->cnt;// 因为 cnt 初始化为 0，所以只有 cnt>0 时才统计了单词的个数
temp->cnt=-1;// 标记已拜访过
}
else// 结点已拜访，退出循环
break;
temp=temp->fail;// 回溯 失败指针 持续寻找下一个满足条件的结点
}
}
return count;
}
C++ 实现
//TrieTreeNode.h
#pragma once
#include<iostream>
using namespace std;
template<class T>
class TrieTreeNode
{
public:
TrieTreeNode(int MaxBranch)// 用于结构根节点
{
MaxBranchNum = MaxBranch;
ChildNodes = new TrieTreeNode<T>*[MaxBranchNum];
for (int i = 0; i < MaxBranchNum; i++)
ChildNodes[i] = NULL;
word = NULL;
wordlen = 0;
FailedPointer = NULL;
Freq = 0;
ID = -1;
}
public:
int MaxBranchNum;// 最大分支数；char* word;// 单词字符串的指针
int wordlen;
TrieTreeNode<T> **ChildNodes;
int Freq;// 词频统计
int ID;// 构建 TrieTree 树时的插入程序，可用来记录字符串第一次呈现的地位
TrieTreeNode<T> *FailedPointer;
};//TrieTree.h
#pragma once
#include<iostream>
#include"TrieTreeNode.h"
#include<queue>
using namespace std;
template<class T>
class TrieTree
{
//Insert 时为节点代表的单词 word 分配内存，Delete 时只批改 Freq 而不删除 word，Search 时以 Freq 的数值作为判断根据，而不是依据 word 是否为 NULL
public:
TrieTree(const int size);
~TrieTree(){ Destroy(root); };
void Insert(const T* str);// 插入单词 str
void Insert(const T* str, const int num);// 插入单词 str，带有编号信息
int Search(const T* str);// 查找单词 str，返回呈现次数
bool Delete(const T* str);// 删除单词 str
void PrintALL();// 打印 trie 树中所有节点对应的单词
void PrintPre(const T* str);// 打印以 str 为前缀的单词
void SetFailedPointer();// 设置匹配生效时的跳转指针
int MatchKMP(char* str);// 返回 str 中呈现在该 TrieTree 中的单词个数
private:
void Print(const TrieTreeNode<T>* p);
void Destroy(TrieTreeNode<T>* p);// 由析构函数调用，开释以 p 为根节点的树的空间
private:
TrieTreeNode<T>* root;
int MaxBranchNum;// 最大分支数
};
template<class T>
void TrieTree<T>::Destroy(TrieTreeNode<T>* p)
{if (!p)
return;
for (int i = 0; i < MaxBranchNum; i++)
Destroy(p->ChildNodes[i]);
if (!p->word)
{delete[] p->word;// 只是开释了 char 数组 word 的空间，指针 word 自身的空间未开释，由后续的 delete p 开释
p->word = NULL;
}
delete p;// 开释节点空间
p = NULL;// 节点指针置为空
// 以上的置 NULL 的两句无太大意义，然而：编程习惯
}
template<class T>
bool TrieTree<T>::Delete(const T* str)
{
TrieTreeNode<T>* p = root;
if (!str)
return false;
for (int i = 0; str[i]; i++)
{int index = str[i] - 'a';
if (p->ChildNodes[index])
p = p->ChildNodes[index];
else return false;
}
p->Freq = 0;
p->ID = -1;
return true;
}
template<class T>
void TrieTree<T>::PrintPre(const T* str)
{
TrieTreeNode<T>* p = root;
if (!str)
return;
for (int i = 0; str[i]; i++)
{int index = str[i] - 'a';
if (p->ChildNodes[index])
p = p->ChildNodes[index];
else return;
}
cout << "以" << str << "为前缀的单词有:" << endl;
Print(p);
}
template<class T>
int TrieTree<T>::Search(const T* str)
{
TrieTreeNode<T>* p = root;
if (!str)
return -1;
for (int i = 0; str[i]; i++)
{int index = str[i] - 'a';
if (p->ChildNodes[index])
p = p->ChildNodes[index];
else return 0;
}
return p->Freq;
}
template<class T>
TrieTree<T>::TrieTree(const int size)
{
MaxBranchNum = size;
root = new TrieTreeNode<T>(MaxBranchNum);// 根节点不贮存字符
root->FailedPointer = root;// 设置失配指针
}
template<class T>
void TrieTree<T>::Insert(const T* str)
{
TrieTreeNode<T>* p = root;
int i;
for (i = 0; str[i]; i++)
{if (str[i]<'a' || str[i]>'z')
{
cout << "格局谬误！" << endl;
return;
}
int index = str[i] - 'a';// 下溯的分支编号
if (!p->ChildNodes[index])
p->ChildNodes[index] = new TrieTreeNode<T>(MaxBranchNum);
p = p->ChildNodes[index];
}
if (!p->word)// 该词以前没有呈现过
{p->word = new char[strlen(str) + 1];
strcpy_s(p->word, strlen(str) + 1, str);
p->wordlen = i;// 设置单词长度
}
p->Freq++;
}
template<class T>
void TrieTree<T>::Insert(const T* str, const int num)
{
TrieTreeNode<T>* p = root;
int i;
for (i = 0; str[i]; i++)
{if (str[i]<'a' || str[i]>'z')
{
cout << "格局谬误！" << endl;
return;
}
int index = str[i] - 'a';// 下溯的分支编号
if (!p->ChildNodes[index])
p->ChildNodes[index] = new TrieTreeNode<T>(MaxBranchNum);
p = p->ChildNodes[index];
}
if (!p->word)// 该词以前没有呈现过
{p->word = new char[strlen(str) + 1];
strcpy_s(p->word, strlen(str) + 1, str);
p->wordlen = i;
}
p->Freq++;
if (num < p->ID || p->ID == -1)// 取最小的 num 作为以后节点代表的单词的 ID
p->ID = num;
}
template<class T>
void TrieTree<T>::PrintALL()
{Print(root);
}
template<class T>
void TrieTree<T>::Print(const TrieTreeNode<T>* p)
{if (p == NULL)
return;
if (p->Freq > 0)
{
cout << "单词:" << p->word << "频数:" << p->Freq;
if (p->ID >= 0)
cout << "ID:" << p->ID;
cout << endl;
}
for (int i = 0; i < MaxBranchNum; i++)
{if (p->ChildNodes[i])
{Print(p->ChildNodes[i]);
}
}
}
template<class T>
int TrieTree<T>::MatchKMP(char* str)
{
int count = 0;//str 中呈现的 TrieTree 中的单词个数
char* p = str;//str 中指针
TrieTreeNode<T>* node = root;//TrieTree 的节点指针
while (*p)
{if (node->ChildNodes[*p - 'a'])// 以后字符匹配胜利
{TrieTreeNode<T>* temp = node->ChildNodes[*p - 'a']->FailedPointer;
while (temp != root)// 在匹配的状况下，依然沿 FailedPointer 搜寻，可检索出所有模式。{if (temp->Freq > 0)
{
count++;
//cout << "temp->wordlen:" << temp->wordlen << endl;
cout << (int)(p - str) - temp->wordlen + 1 << " " << temp->word << endl;// 打印已匹配的模式的信息
}
temp = temp->FailedPointer;
}
node = node->ChildNodes[*p - 'a'];
p++;
if (node->Freq > 0)
{
count++;
//cout << "node->wordlen:" << node->wordlen << endl;
cout << (int)(p - str) - node->wordlen << " " << node->word << endl;// 打印已匹配的模式的信息
}
}
else// 失配，跳转
{if (node == root)
p++;
else
node = node->FailedPointer;
}
}
return count;
}
template<class T>
void TrieTree<T>::SetFailedPointer()
{
queue<TrieTreeNode<T>*> q;
q.push(root);
while (!q.empty())
{TrieTreeNode<T>* father = q.front();// 父节点
q.pop();
for (int i = 0; i < MaxBranchNum; i++)// 对每一个子节点设置 FailedPointer
{if (father->ChildNodes[i])
{TrieTreeNode<T>* child = father->ChildNodes[i];
q.push(child);
TrieTreeNode<T>* candidate = father->FailedPointer;// 从 father->FailedPointer 开始游走的指针
while (true)
{if (father == root)
{
candidate = root;
break;
}
if (candidate->ChildNodes[i])// 有与 child 代表的字母雷同的子节点
{candidate = candidate->ChildNodes[i];
break;
}
else
{if (candidate == root)
break;
candidate = candidate->FailedPointer;// 以上两句程序不能替换，因为在 root 仍能够做一次匹配
}
}
child->FailedPointer = candidate;
}
}
}
}//main.cpp
#pragma once
#include<iostream>
#include<fstream>
#include"TrieTree.h"
using namespace std;
void test(TrieTree<char>* t)
{char* charbuffer = new char[50];
char* cb = charbuffer;
fstream fin("d:\\words.txt");
if (!fin){
cout << "File open error!\n";
return;
}
char c;
int num = 0;
while ((c = fin.get()) != EOF)
{if (c >= '0'&&c <= '9')
num = num * 10 + c - '0';
if (c >= 'a'&&c <= 'z')
*cb++ = c;
if (c == '\n')
{
*cb = NULL;
t->Insert(charbuffer, num);
cb = charbuffer;
num = 0;
}
}
fin.close();}
void main()
{TrieTree<char>* t = new TrieTree<char>(26);
char* c1 = "she";
char* c2 = "shee";
char* c3 = "he";
char* c4 = "e";
char* s = "shee";// 要匹配的串
t->Insert(c1);
t->Insert(c2);
t->Insert(c3);
t->Insert(c4);
//test(t);
t->SetFailedPointer();
t->PrintALL();
cout << endl << "匹配后果为:" << endl;
int result = t->MatchKMP(s);
cout << "共匹配" << result << "处模式串" << endl;
system("pause");
}堆
简介
堆实际上是一个齐全二叉树，在实现的时候采纳数组来实现。
根节点的值比所有节点的值都大，称为最大堆；
根节点的值比所有节点的值都小，称为最小堆；
堆的插入和删除
/************************************************************************/
/* 堆的实现 */
/************************************************************************/
#include<vector>
namespace stl
{
template<typename T>
class Heap
{
public:
/************************************************************************/
/* 构造函数 */
Heap(int capacity = 100)
:size(0) // 堆中蕴含数据个数
{H.resize(capacity);
}
~Heap()
{ }
bool isEmpty()
{return size == 0;}
void makeEmpty()
{
size = 0;
for (auto it = H.begin(); it != H.end(); it++)
{H.erase(it);
}
}
/************************************************************************/
/* 插入函数 */
void insert(const T & x)
{
// 如果 vector 中曾经存满了，从新分为大小，数组首地址不存数据
if (size == H.size() -1)
{H.resize(2*size);
}
//size 大小加一
for (int current = ++size; current > 1 && H[current/2] > x; current /= 2)
{H[current] = H[current/2];
}
// 找到空位将 x 插入
H[current] = x;
}
/* 删除函数 */
T deleteMin()
{if (isEmpty())
{throw();
}
int current, child;
T returnVal = H[1];
T lastElement = H[size--]; // 将最初一个值保留下来，删除一个元素所以自减运算
for (current = 1; 2 * current > size; current = child)
{
child = 2 * current;
// 避免拜访越界
if (child != size && H[2 * current] > H[2 * current + 1])
{++child;}
// 比拟子较小的儿子与最初一个值的大小，如果儿子较小用儿子上滤，否则跳出循环
if (H[child] < lastElement)
{H[current] = H[child];
}
else
{break;}
}
H[current] = lastElement;
return returnVal;
}
private:
std::vector<T> H;
int size;
};
}堆排序
https://blog.csdn.net/pursue_…
将堆的顶部，与最初一个元素替换。此时除了最初一个元素外，剩下元素所组成的树曾经不是 堆了。（因为此时顶部的元素可能比拟小）。所以，要将剩下的元素通过 adjust 函数调整成 堆。
而后持续将残余元素中的最初一个元素 与 新堆的顶部替换
#include <iostream>
using namespace std;
void adjust_heap(int* a, int node, int size)
{
int left = 2*node + 1;
int right = 2*node + 2;
int max = node;
if(left < size && a[left] > a[max])
max = left;
if(right < size && a[right] > a[max])
max = right;
if(max != node)
{swap( a[max], a[node]);
adjust_heap(a, max, size);
}
}
void heap_sort(int* a, int len)
{for(int i = len/2 -1; i >= 0; --i)
adjust_heap(a, i, len);
for(int i = len - 1; i >= 0; i--)
{swap(a[0], a[i]); // 将以后最大的搁置到数组开端
adjust_heap(a, 0 , i); // 将未实现排序的局部持续进行堆排序
}
}
int main()
{int a[10] = {3, 2, 7, 4, 2, -999, -21, 99, 0, 9};
int len= sizeof(a) / sizeof(int);
for(int i = 0; i < len; ++i)
cout << a[i] << ' ';
cout << endl;
heap_sort(a, len);
for(int i = 0; i < len; ++i)
cout << a[i] << ' ';
cout << endl;
return 0;
}然而堆排序中的几个函数，还是能够通过优化来晋升 工夫复杂度的。比方 adjust（）函数的优化
如果在用 adjust 在调整最大堆时，替换须要以下操作：
temp = a[node];
a[node] = a[max];
a[max] = temp;
须要操作三次，100000 次 的替换须要操作 300000 次。太过于耗时。所以咱们能够做相似于插入排序的优化。
if(节点的某一个儿子 > 节点自身)
用 temp 把儿子存起来，并把节点赋值给儿子；用 temp 上浮一层到节点的地位，继续执行判断，这样一层层不停的上浮。直到不符合条件
if( temp < 同一层的兄弟节点 || temp < 父亲节点）把 temp 赋值给以后层的元素；这样省去了每次的替换，100000 的操作只须要操作 100000 次。大大提高了效率
优先队列
简介
优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先失去服务；优先级雷同的元素依照其在优先队列中的程序失去服务。优先队列往往用堆来实现。
出于性能思考，优先队列用堆来实现，具备 O(log n)工夫复杂度的插入元素性能，O(n)的初始化结构的工夫复杂度。如果应用自均衡二叉查找树，插入与删除的工夫复杂度为 O(log n)，结构二叉树的工夫复杂度为 O(n log n)。从计算复杂度的角度，优先级队列等价于排序算法。
用堆来满足先进先出，依照优先级排序，而后输入
剖析：
1. 一棵齐全二叉树，所以能够用一个数组示意而不须要用指针。然而用数组就要当时预计堆的大小，所以用一个 Capacity 示意最大值。
2. 因为放弃堆序性质，最小元就是在根上，删除后还得做一些调整来放弃齐全二叉树的构造（理论就是删除最初一个元素，而后把它插入到队列中）。
3. 若以后节点下标为 i，则 i2 和 i2+ 1 就是它的左右孩子，咱们在 data[0]处放了一个 MIN_INT。
4. 入队：首先 size++，如果 data[size]插入不毁坏构造，完结。否则，一直用父亲的值赋给以后节点，直到适合的地位。工夫复杂度 O(logN)。
5. 出队：首先根节点置空，记录 size 点（last）的值而后 size–，last 能放入以后空穴就完结，否则，一直用儿子中最小的值赋给以后节点。工夫复杂度 O(logN)。（正文：入队和出队的调整是一个逆向对称的过程）
6. 队首：间接返回根节点的值，为最小值，O(1)。
Code1
#include <iostream>
using namespace std;
class PriorityQueue
{
private:
int* pArray;
int m_length;
public:
PriorityQueue(int N) {
// 为后续根节点间接从 1 开始作筹备
pArray = new int[N + 1];
m_length = 0;
}
int delMax() {
// 大根堆第一个元素为最大
int max = pArray[1];
// 将第一个元素和最初一个元素替换, 并使长度减一，即删除最大的元素
swap(pArray[1], pArray[m_length--]);
// 避免对象游离
pArray[m_length + 1] = NULL;
// 下沉复原堆的有序性
sink(1);
// 返回最大的节点值
return max;
}
void insert(int v) {// 将值 v 插入到 pArray[1]地位处，所以这里用的前置 ++
pArray[++m_length] = v;
// 新退出的元素上浮
swim(m_length);
}
// 判断是否为空
bool isEmpty() {return m_length == 0;}
int size() {return m_length;}
// 向上浮
void swim(int k) {
// 判断最上层的叶子节点值如果大于其父节点则进入循环上浮
while (k > 1 && pArray[k] > pArray[k / 2]) {
// 替换父节点和子节点
swap(pArray[k / 2], pArray[k]);
// k 数值减小持续向上浮
k /= 2;
}
}
// 向下沉
void sink(int k) {while (2 * k <= m_length)
{
// 因为堆的性质父节点为 k 则其左子树为 2 * k 即 j
int j = 2 * k;
// 这里先比拟左子树和右子树的大小，将最大的那个键记录下来再和父节点比拟
if (j < m_length && (pArray[j] < pArray[j + 1])) j++;
// 和父节点比拟如果父节点比最大的子节点还要大，则间接退出循环
if (pArray[k] > pArray[j]) break;
// 如果父节点比子节点小则替换
swap(pArray[k], pArray[j]);
// k 值变大持续下沉
k = j;
}
}
};
int main() {PriorityQueue pq(5);
pq.insert(2);
pq.insert(11);
pq.insert(6);
pq.insert(1);
pq.insert(15);
cout << pq.delMax() << endl;
cout << pq.delMax() << endl;
cout << pq.delMax() << endl;
cout << pq.delMax() << endl;
cout << pq.delMax() << endl;
return 0;
}
Code2
#ifndef PRIORITYQUEUE_H
#define PRIORITYQUEUE_H
template<class T>
class PriorityQueue
{
private:
int Capacity = 100; // 队列容量
int size; // 队列大小
T* data; // 队列变量
public:
PriorityQueue();
~PriorityQueue();
int Size();
bool Full(); // 判满
bool Empty(); // 判空
void Push(T key); // 入队
void Pop(); // 出队
void Clear(); // 清空
T Top(); // 队首};
template<class T>
PriorityQueue<T>::PriorityQueue()
{data = (T*) malloc((Capacity + 1)*sizeof(T));
if(!data)
{perror("Allocate dynamic memory");
return;
}
size = 0;
}
template<class T>
PriorityQueue<T>::~PriorityQueue()
{while(!Empty())
{Pop();
}
}
template<class T>
// 判空
bool PriorityQueue<T>::Empty()
{if(size > 0)
{return false;}
return true;
}
template<class T>
// 清空
void PriorityQueue<T>::Clear()
{while(!Empty())
{Pop();
}
}
template<class T>
// 判满
bool PriorityQueue<T>::Full()
{if(size == Capacity)
{return true;}
return false;
}
template<class T>
// 大小
int PriorityQueue<T>::Size()
{return size;}
template<class T>
// 入队
void PriorityQueue<T>::Push(T key)
{
// 空队则间接入队
if(Empty())
{data[++size] = key;
return;
}
int i;
if(Full())
{perror("Priority queue is full\n");
return;
}
for(i = ++size; data[i/2] > key; i /= 2)
{data[i] = data[i/2];
}
data[i] = key;
}
template<class T>
// 队首
T PriorityQueue<T>::Top()
{if(Empty())
{perror("Priority queue is full\n");
return data[0];
}
return data[1];
}
template<class T>
// 出队, 取完队首元素后，才执行出队操作，即去除堆顶元素，将开端元素避免堆顶，并做 sink 调整
void PriorityQueue<T>::Pop()
{
int i, child;
T min, last;
if(Empty())
{perror("Empty queue\n");
return;
}
// min = data[1];
last = data[size--];
for(i = 1; i * 2 <= size; i = child)
{
child = i * 2;
if(child != size && data[child + 1] < data[child])
{child++;}
if(last > data[child])
{data[i] = data[child];
} else
{break;}
}
data[i] = last;
}
#endif // PRIORITYQUEUE_H
//.cpp
#include <iostream>
#include <queue>
#include "priorityqueue.h"
using namespace std;
const int MAXN = 1000;
// 事件
struct Event
{
int arrive; // 达到工夫
int service; // 服务工夫
Event(){};
Event(int a, int s)
{
arrive = a;
service = s;
}
} cus[MAXN];
int operator > (const Event& a, const Event& b)
{return a.arrive > b.arrive;}
int operator < (const Event& a, const Event& b)
{return a.arrive < b.arrive;}
int main()
{Event minCustomer(INT_MIN, 0);
PriorityQueue<Event> request; // 顾客
int n, time;
while (cin >> n)
{for (int i = 0; i < n; ++i)
{cin >> cus[i].arrive >> cus[i].service;
request.Push(cus[i]); // 顾客入队
}
time = 0; // 服务工夫
while (!request.Empty())
{Event current = request.Top();
request.Pop();
// 计算最初的工夫节点
time = max(current.arrive + current.service, time + current.service);
}
cout << "time costs =" << time << endl;
}
return 0;
}
参考大神博客
https://blog.csdn.net/pursue_…
https://blog.csdn.net/hgqqtql…
https://blog.csdn.net/liu9402…
https://blog.csdn.net/weixin_…
https://www.cnblogs.com/xenny…
https://www.cnblogs.com/sgatb…
https://blog.csdn.net/qq_2594…
https://blog.csdn.net/z_ryan/…
https://www.jianshu.com/p/fc1…
https://www.cnblogs.com/wangw…
https://blog.csdn.net/happyja…
https://www.cnblogs.com/smile…
https://blog.csdn.net/happyja…
https://blog.csdn.net/weixin_…
https://www.cnblogs.com/skywa…
https://blog.csdn.net/v_JULY_v/article/details/6897097?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159434584019195265900582%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=159434584019195265900582&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v1~rank_blog_v1-1-6897097.pc_v1_rank_blog_v1&utm_term=%E5%90%8E%E7%BC%80%E6%A0%91
