数据结构

ZEROKO142020-12-232025-01-23

数据结构学习

数据结构

数据结构是计算机存储、组织数据的方式。是相互之间存在一种或多种特定关系的数据元素集合

[[算法]]是特定问题求解步骤的描述，在计算机中表现为指令的有限序列，算法是独立存在的一种解决问题的方法和思想。

对于算法而言，语言并不重要，重要的是思想。

[[算法]]和数据结构区别

算法是为了解决实际问题而设计的。
数据结构是算法需要处理的问题载体。
数据结构与算法相辅相成。

[[算法]]具有五个基本的特性：输入、输出、有穷性、确定性和可行性

输入输出：算法具有零个或多个输入、至少有一个或多个输出。
有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
确定性：算法的每一步骤都有确定的含义，不会出现二义性。
可行性：算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。

数据结构分类

逻辑结构

集合结构

集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。各个数据元素是平等的。他们共同属于同一个集合，数据结构中的集合关系类似于数学中的集合。如图：

线性结构

线性结构中的数据元素之间是一对一的关系。

一对一：第一个元素没有前驱，最后一个元素没有后续，其他元素都有一个前驱一个后继

如图：

树形结构

树形结构中是数据元素之间存在一种一对多的层次关系，如图：

图形结构

图形结构的数据元素多对多的关系，如图：

物理结构

物理结构：是指数据的逻辑结构在计算机中的存储形式，共分为两种：顺序存储和链式存储。

顺序存储

是把数据元素存放在地址连续的存储单元里，其数据的逻辑关系和物理关系是一致的，如图：

链式存储结构

是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关数据的位置。如图：

线性表

线性结构是一种最简单且常用的数据结构。线性结构的基本特点是节点之间满足线性关系。

动态数组、链表、栈、队列都属于线性结构。

线性表是零个或者多个数据元素的有限序列，数据元素之间是有顺序的，数据元素个数是有限的，数据元素的类型必须相同

动态数组

下图中的链表指的就是动态数组

优点：

无需为线性表中的逻辑关系增加额外的空间。
可以快速的获取表中合法位置的元素。

缺点：

插入和删除操作需要移动大量元素。

动态数组案例：

dynamicArray.h头文件

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\动态数组案例\DYNAMICARRAY\dynamicArray.h 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 05 17：06 
* @文件描述： 动态数组头文件
****************************************************** ************************/  


#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//未使用void*重命名隐藏DynamicArray指针的索引，并且未将如下结构体置于源文件中，防止生成库时用户直接在头文件中看到
typedef struct _DynamicArray
{
	void **ArrayAddr;//动态数组首地址
	int m_capacity;//动态数组当前容量
	int m_size;//动态数组当前占用大小
}DynamicArray;


//动态数组初始化
DynamicArray* init_DynamicArray(int capacity);

//动态数组遍历
void foreach_DynamicArray(DynamicArray* dynamicArray,void(*myPrintf)(void*));


//动态数组末尾添加
void append_DynamicArray(DynamicArray* dynamicArray,void* data);


//动态数组插入
void insert_DynamicArray(DynamicArray* dynamicArray, int pos, void* data);


//动态数组修改
void change_DynamicArray(DynamicArray* dynamicArray, int pos, void* data);


//动态数组项删除
void removeByPos_DynamicArray(DynamicArray* dynamicArray,int pos);


//动态数组清空
void clear_DynamicArray(DynamicArray* dynamicArray);


//动态数组销毁
void destroy_DynamicArray(DynamicArray** dynamicArray);

dynamicArray.c源文件

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\动态数组案例\DYNAMICARRAY\dynamicArray.c 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 05 17：06 
* @文件描述： 动态数组源文件
****************************************************** ************************/  
#include "dynamicArray.h"

DynamicArray* init_DynamicArray(int capacity)
{
	if (capacity<=0)
	{
		return NULL;
	}
	DynamicArray* dynamicArray = malloc(sizeof(DynamicArray));
	if (!dynamicArray)
	{
		return NULL;
	}
	dynamicArray->ArrayAddr = malloc(sizeof(void*)*capacity);
	if (!dynamicArray->ArrayAddr)
	{
		free(dynamicArray);
		return NULL;
	}
	dynamicArray->m_capacity = capacity;
	dynamicArray->m_size = 0;
	return dynamicArray;
}

void foreach_DynamicArray(DynamicArray* dynamicArray, void(*myPrintf)(void*))
{
	if (!dynamicArray||!myPrintf)
	{
		return;
	}
	printf("容量：%d  占用大小：%d\r\n",dynamicArray->m_capacity,dynamicArray->m_size);
	for (size_t i = 0; i < dynamicArray->m_size; i++)
	{
		myPrintf(dynamicArray->ArrayAddr[i]);
	}
}


void insert_DynamicArray(DynamicArray* dynamicArray, int pos, void* data)
{
	if (!dynamicArray||!data)
	{
		return;
	}
	//无效位置，则尾插
	if (pos<0||pos>dynamicArray->m_size)
	{
		pos = dynamicArray->m_size;
	}
	//空间不够则拓展空间
	if (dynamicArray->m_size==dynamicArray->m_capacity)
	{
		dynamicArray->ArrayAddr = realloc(dynamicArray->ArrayAddr, dynamicArray->m_capacity *sizeof(void*)*2);
		dynamicArray->m_capacity*=2;
	}
	//后面元素往后移动
	for (int i = dynamicArray->m_size-1; i >=pos; i--)
	{
		dynamicArray->ArrayAddr[i + 1] = dynamicArray->ArrayAddr[i];
	}
	//插入新元素
	dynamicArray->ArrayAddr[pos] = data;
	dynamicArray->m_size++;
	
	
}


void change_DynamicArray(DynamicArray* dynamicArray, int pos, void* data)
{
	if (!dynamicArray || !data)
	{
		return;
	}
	//无效位置
	if (pos<0 || pos>=dynamicArray->m_size)
	{
		return;
	}
	dynamicArray->ArrayAddr[pos] = data;
}

void clear_DynamicArray(DynamicArray* dynamicArray)
{
	if (!dynamicArray )
	{
		return;
	}
	memset(dynamicArray->ArrayAddr, 0,sizeof(void*)*dynamicArray->m_size);
	dynamicArray->m_size = 0;
}



void destroy_DynamicArray(DynamicArray** dynamicArray)
{
	if (!(*dynamicArray))
	{
		return;
	}
	if ((*dynamicArray)->ArrayAddr!=NULL)
	{
		free((*dynamicArray)->ArrayAddr);
		(*dynamicArray)->ArrayAddr = NULL;
	}
	free(*dynamicArray);
	*dynamicArray = NULL;
	
}


void removeByPos_DynamicArray(DynamicArray* dynamicArray, int pos)
{
	if (!dynamicArray)
	{
		return;
	}
	if (pos < 0 || pos >= dynamicArray->m_size)
	{
		return;
	}
	for (int i = 0; i < dynamicArray->m_size-1; i++)
	{
		if (i>=pos)
		{
			dynamicArray->ArrayAddr[i] = dynamicArray->ArrayAddr[i + 1];
		}
	}
	dynamicArray->ArrayAddr[dynamicArray->m_size - 1] = NULL;
	dynamicArray->m_size--;
}

链表

数组缺陷：

静态空间，一旦分配内存就不可以动态扩展，如果分配过多，造成资源浪费，空间操作不精确
插入删除效率低

链表的构成

链表由节点构成

节点由数据域（维护数据）和指针域（维护上一个或下一个节点）组成

带头节点指针pHeader，和尾节点指针pTail

但大多数链表都只带头节点，如下图

不带链表头节点如下图：

头节点不固定，根据实际需要变换头节点(如在原来头节点前插入新节点，然后，新节点重新作为链表的头节点)。

优势：带头节点永远固定了头节点和尾节点的位置，方便头部和尾部的操作

链表的分类一：

静态链表（在栈上分配内存）

//链表节点的结构体
typedef struct _LinkNode
{
	int num;//数据域
	struct LinkNode* next;//指针域
}LinkNode;

void main()
{
    //创建节点
    LinkNode node1={10,NULL};
    LinkNode node2={20,NULL};
    LinkNode node3={30,NULL};
    //建立关系
    node1.next=&node2;
    node2.next=&node3;
    //遍历链表
    LinkNode* pCurrent=&node1;
    while(pCurrent!=NULL)
    {
        //此处可遍历数据
        printf("%d\r\n",pCurrent.num);
        pCurrent=pCurrent->next;
	}  
}

动态链表（在堆上分配内存）

//链表节点的结构体
typedef struct _LinkNode
{
	int num;//数据域
	struct LinkNode* next;//指针域
}LinkNode;

void main()
{
    //创建节点
    LinkNode* node1=malloc(sizeof(LinkNode));
    LinkNode* node2=malloc(sizeof(LinkNode));
    LinkNode* node3=malloc(sizeof(LinkNode));
    node1->num=100;
    node2->num=200;
    node3->num=300;
    //建立关系
    node1->next=node2;
    node2->next=node3;
    node3->next=NULL;
    //遍历链表
    LinkNode* pCurrent=node1;
    while(pCurrent!=NULL)
    {
        //此处可遍历数据
        printf("%d\r\n",pCurrent->num);
        pCurrent=pCurrent->next;
	}  
    //释放空间
    free(node1);
    free(node2);
    free(node3);
    node1=null;
    node2=null;
    node3=null;
}

链表的分类二

单向链表

双向链表

单向循环链表

双向循环链表

链表案例：

linkList.h头文件

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\链表案例\LINKNODETEST\linkList.h 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 06 15：38 
* @文件描述： 链表头文件，链表一切空间申请释放均已处理
****************************************************** ************************/  

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


//此处由于C语言中没有C++类似的保护内部数据防止直接访问的机制，因此用void*的方式可以防止使用我们代码的用户访问到内部成员（就是点不出来），而我们自己使用的时候再自己进行强转使用。
typedef void* LinkList;


//初始化链表
LinkList* init_LinkList();


//遍历链表
void foreach_LinkList(LinkList* linklist, void(*myPrintf)(void*));


//添加节点
void append_LinkList(LinkList* linklist, void* data);


//插入链表
void insert_LinkList(LinkList* linklist, int pos, void* data);


//删除节点
void delete_LinkList(LinkList* linklist, int pos);


//反转链表
void reverse_LinkList(LinkList* linklist);


//清空链表 
void clear_LinkList(LinkList* linklist);


//销毁链表
void destroy_LinkList(LinkList** linklist);


//返回长度
int getLength_LinkList(LinkList* linklist);

linkList.cpp源文件

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\链表案例\LINKNODETEST\linkList.cpp 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 06 15：38 
* @文件描述： 链表源文件，链表一切空间申请释放均已处理
****************************************************** ************************/  
#include "linkList.h"

//重点：该结构体放在源文件中的目的是当把这个文件生成库文件时，可以避免用户直接在头文件中直接看到该结构的真实情况
//节点结构体，用于组织成链表
typedef struct _LinkNode
{
	void* data;
	struct _LinkNode* next;
}LinkNode;

//链表结构体，用于维护链表整体的必要数据
typedef struct __LinkList
{
	LinkNode* pHeader;//链表头节点
	int m_size;//链表长度
}_LinkList;

LinkList* init_LinkList()
{
	LinkList* linklist = (LinkList*)malloc(sizeof(LinkList));
	LinkNode* pHeader = (LinkNode*)malloc(sizeof(LinkNode));
	if (!pHeader)
	{
		return NULL;
	}
	pHeader->data = NULL;//无用数据
	pHeader->next = NULL;
	((_LinkList*)linklist)->m_size = 0;
	((_LinkList*)linklist)->pHeader = pHeader;
	return linklist;
}

void foreach_LinkList(LinkList* _linklist, void(*myPrintf)(void*))
{
	_LinkList* linklist = _linklist;
	//参数校验
	if (!linklist || !linklist->pHeader||!myPrintf)
	{
		return;
	}
	printf("-------------------------------------------------\r\n");
	//遍历操作
	LinkNode* pCurrent = linklist->pHeader->next;
	while (pCurrent)
	{
		myPrintf(pCurrent->data);
		pCurrent = pCurrent->next;
	}
	printf("链表数量为%d\r\n", linklist->m_size);
	printf("-------------------------------------------------\r\n");
	printf("\r\n");
	
}

void append_LinkList(LinkList* _linklist, void* data)
{
	_LinkList* linklist = _linklist;
	//参数校验
	if (!linklist || !linklist->pHeader ||  !data)
	{
		return;
	}
	//申请空间并拷贝添加节点内存
	LinkNode* pAppend = (LinkNode*)malloc(sizeof(LinkNode));
	if (!pAppend)
	{
		return;
	}
	pAppend->data = data;
	//添加操作
	LinkNode* pCurrent = linklist->pHeader;
	while (pCurrent->next)
	{
		pCurrent = pCurrent->next;
	}
	pCurrent->next = pAppend;
	pAppend->next = NULL;
	linklist->m_size++;
}

void insert_LinkList(LinkList* _linklist, int pos, void* data)
{
	_LinkList* linklist = _linklist;
	//参数校验
	if ( !linklist||!linklist->pHeader || !data ||!linklist)
	{
		return;
	}
	if (pos < 0||pos> linklist->m_size)//无效位置,强制做尾插
	{
		pos = linklist->m_size;
	}
	//找到插入位置
	LinkNode* pCurrent = linklist->pHeader;
	int curPos = 0;
	while (pCurrent->next)
	{
		if (pos == curPos)
		{
			break;
		}
		pCurrent = pCurrent->next;
		curPos++;
	}

	//申请空间并拷贝插入节点内存
	LinkNode* pInsert = (LinkNode*)malloc(sizeof(LinkNode));
	if (!pInsert)
	{
		return;
	}
	pInsert->data = data;

	//插入操作
	pInsert->next = pCurrent->next;
	pCurrent->next = pInsert;
	linklist->m_size++;
}

void delete_LinkList(LinkList* _linklist, int pos)
{
	_LinkList* linklist = _linklist;
	if (!linklist || !linklist->pHeader)
	{
		return;
	}
	if (pos < 0 || pos>= linklist->m_size)
	{
		return;
	}
	//找到位置
	LinkNode* pCurrent = linklist->pHeader;
	int curPos = 0;
	while (pCurrent->next)
	{
		if (pos == curPos)
		{
			break;
		}
		pCurrent = pCurrent->next;
		curPos++;
	}
	//删除操作票
	if (!pCurrent->next)
	{
		return;
	}
	LinkNode* pNext = pCurrent->next->next;//临时储存后面链表
	free(pCurrent->next);
	pCurrent->next = pNext;
	linklist->m_size--;
}

void reverse_LinkList(LinkList* _linklist)
{
	_LinkList* linklist = _linklist;
	if (!linklist || !linklist->pHeader&&!linklist->pHeader->next)//排除链表没有或者只有一个的情况
	{
		return;
	}
	LinkNode* pCurrent = linklist->pHeader->next;
	LinkNode* pCurrentNext = pCurrent->next;
	LinkNode* pCurrentNextNext = NULL;
	while (pCurrentNext)//链表还有两个节点以上的时候
	{
		if (pCurrentNext->next)//链表还有第三个节点的时候，记录第三个节点,否则记录为NULL
		{
			pCurrentNextNext = pCurrentNext->next;
		}
		else
		{
			pCurrentNextNext = NULL;
		}
		//对前两个节点进行翻转操作
		pCurrentNext->next = pCurrent;
		//两指针后移一段
		pCurrent = pCurrentNext;
		pCurrentNext = pCurrentNextNext;
	}
	//跳出循环后pCurrent为尾节点指针,现将头节点指向的节点的next置空，然后头节点指针指向尾节点
	linklist->pHeader->next->next = NULL;
	linklist->pHeader->next = pCurrent;
}

void clear_LinkList(LinkList* _linklist)
{
	_LinkList* linklist = _linklist;
	if (!linklist || !linklist->pHeader)
	{
		return;
	}
	LinkNode* tmpCurrent = NULL;
	while (linklist->pHeader->next)
	{
		tmpCurrent = linklist->pHeader->next->next;
		free(linklist->pHeader->next);
		linklist->pHeader->next = tmpCurrent;
		tmpCurrent = NULL;
	}
	linklist->m_size=0;
}

void destroy_LinkList(LinkList** _linklist)
{
	_LinkList** linklist = _linklist;
	if (!*linklist || !(*linklist)->pHeader)
	{
		return;
	}
	LinkNode* tmpCurrent = NULL;
	LinkNode* pCurrent = (*linklist)->pHeader;
	while (pCurrent)
	{
		tmpCurrent = pCurrent->next;
		free(pCurrent);
		pCurrent = tmpCurrent;
	}
	(*linklist)->pHeader = NULL;
	if (!*linklist)
	{
		free(*linklist);
		*linklist = NULL;
	}
}

int getLength_LinkList(LinkList* _linklist)
{
	_LinkList* linklist = _linklist;
	if (!linklist|| !linklist->pHeader)
	{
		return 0;
	}
	return linklist->m_size;
}

跳表

详解参考

参考Leetcode1206题

跳表（Skiplist，全称跳跃表）是用于有序元素序列快速搜索查找的一个数据结构，跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，实现也比红黑树简单很多

增删改查时间复杂度为O(log n)

Redis中的有序集合 sorted set 就是用跳表实现的

跳表最核心的一个原理: 利用随机化规避倾斜数据

跳表和二分查找法的对比

二分查找法针对的是有序数据，二分查找强依赖顺序表结构，简单来讲就是数组
数据量太小不适合二分查找。如果数据量太小，完全没有必要用二分查找，进行逐个遍历就足够了
数据量太大也不适合二分查找，二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求也比较苛刻

跳表和红黑树的对比

1.对于插入，删除，查找以及输出有序序列这几个操作，红黑树也可以完成，时间复杂度与用跳表实现是相同的。但是，对于按照区间查找数据这个操作（比如 [20,300]）,红黑树的效率没有跳表高，跳表可以做到 O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序向后遍历输出，直到遇到值大于区间终点的节点为止。

2.跳表更加灵活，它可以通过改变节点的抽取间隔，灵活地平衡空间复杂度和时间复杂度

3.相比红黑树，跳表更容易实现，代码更简单。

跳表的实现

参考资料

需要实现

实现一种结构,支持如下操作,要求单次调用的时间复杂度O(logn)

增加x,重复加入算多个词频
删除x,如果有多个,只删掉一个
查询x的排名，×的排名为，比x小的数的个数+1
查询数据中排名为x的数
查询x的前驱，x的前驱为，小于x的数中最大的数，不存在返回整数最小值
查询x的后继，×的后继为，大于x的数中最小的数，不存在返回整数最大值

结构

组织结构类似平衡树

跳表的节点结构,类似链表节点结构,但可能包含多层指针

每个节点拥有多少层指针,类似骰子扔大小,扔出小就增加层数，一旦扔出大就确定层数，总层数有限制

总层数的限制取决于有多少个元素要加入,比如说100万个元素需要加入,那么2的20次方最接近100万,即假设链表包含n个节点,每两个节点抽出一个节点作为上一级索引的节点，如果把原始链表这一层也算进去,那么整个跳表的高度约为$\mathrm{log_2^n}$

建立索引后的总的索引点的空间复杂度：
$$
n/2+n/4+n/8+\cdots+2=n-2
$$
如果每三个节点抽一个节点到上一级,则空间复杂度为:
$$
n / 3+n / 9+n / 27+\cdots+9+3+1=n / 2
$$

跳表的索引动态更新

作为一种动态数据结构，为了避免性能下降，我们需要在数据插入，删除的过程中，动态地更新跳表的索引结构。 就像红黑树，二叉平衡树是通过左右旋来保持左右子树的大小平衡，而跳表是借助随机函数来更新索引结构

一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：

注意,在新增的过程中,查找的时候,找到值的过程中记录经过的节点路径,在新增的时候按照50%概率确定是否往上一层(通过回溯节点路径)继续新增,如果50%概率没命中就直接结束,不再往上插.

巧妙的通过概率来决策是否往上层插数据

代码

class Skiplist
{
public:
    struct Node
    {
        // 向右向下指针
        Node *right;
        Node *down;
        int val;
        Node(Node *right, Node *down, int val)
            : right(right), down(down), val(val) {}
    };

    Skiplist()
    {
        // 初始化头节点,头节点指向的是最上层的起始节点
        head = new Node(nullptr, nullptr, -1);
        pathList.resize(MAX_LEVEL);
    }

    bool search(int target)
    {
        Node *cur = head;
        while (cur)
        {
            // 左右查找目标区间
            while (cur->right && cur->right->val < target)
            {
                cur = cur->right;
            }
            // 找到当前层最接近的左区间,开始下探
            if (!cur->right || target < cur->right->val)
            {
                // 小于的情况继续下探
                cur = cur->down;
            }
            else
            {
                // 等于的情况直接返回
                return true;
            }
        }
        return false;
    }

    void add(int num)
    {
        // 从上至下记录搜索路径
        pathList.clear();
        Node *cur = head;
        while (cur)
        {
            // 在当前层中找到最后一个小于 num 的节点 cur
            while (cur->right && cur->right->val < num)
            {
                cur = cur->right;
            }
            pathList.push_back(cur);
            cur = cur->down;
        }
        // 沿着路径回溯,确定是否需要插入节点
        //  insertUp控制是否继续在当前层插入新节点
        bool insertUp = true;
        // downNode 是一个指向下层节点的指针，初始值为 nullptr。在插入过程中，downNode 会指向当前层插入的节点，以便在更高层插入时使用。
        Node *downNode = nullptr;
        while (insertUp && pathList.size() > 0)
        {
            Node *insert = pathList.back();
            pathList.pop_back();
            insert->right = new Node(insert->right, downNode, num);
            downNode = insert->right;
            // 下面是核心代码,50%概率决定了是否继续向上层插入节点
            insertUp = (rand() & 1) == 0;
        }
        // 创建新层
        if (insertUp)
            head = new Node(new Node(NULL, downNode, num), head, -1);
    }

    bool erase(int num)
    {
        Node *cur = head;
        bool seen = false;
        while (cur)
        {
            // 在当前层中找到最后一个小于 num 的节点 cur
            while (cur->right && cur->right->val < num)
            {
                cur = cur->right;
            }
            // 无效点太大,则到下一层去
            if (!cur->right || cur->right->val > num)
            {
                cur = cur->down;
            }
            else
            {
                // 搜索到目标节点,进行删除操作,结果记录为true
                // 继续往下层搜索,删除一组目标结点
                seen = true;
                Node *toDelete = cur->right; // 保存需要释放的节点
                cur->right = cur->right->right;
                delete toDelete; // 释放内存
                cur = cur->down;
            }
        }
        return seen;
    }

private:
    Node *head;
    // 查找时临时使用的变量,一个记录路径的容器（如 std::vector），用于存储每一层中最后一个小于 num 的节点,是一个存储了插入路径的栈
    // 这个路径记录是为了后续的插入或删除操作做准备。在插入或删除时，需要从底层向上回溯，更新每一层的链表结构。
    vector<Node *> pathList;
    // 预先分配后，提升性能
    const static int MAX_LEVEL = 32;
};

树状数组

参考视频

所有层的第偶数个数字都是没有用的,去掉也不影响使用

在更新和查询操作中，lowbit 用于确定更新的范围(也就是图中矩形方框的宽度),从序号开始读取

lowbit

在计算机科学中，”lowbit”（低位）通常指的是一个整数的二进制表示中最低有效位（Least Significant Bit，LSB）为 1 的部分。具体来说，对于一个正整数 ( x )，可以通过以下方式计算其 “lowbit”：
$$
\text{lowbit}(x) = x & (-x)
$$
这个公式的原理是利用了补码的特性。在补码中，负数的表示是通过对其绝对值取反并加一来得到的。因此， ( -x ) 的二进制表示中，最低有效位为 1 的部分在与原数 ( x ) 进行按位与运算时会保留下来，而其他高位则会被清零。

与前缀和数组的区别

对比维度	前缀和数组	树状数组 (Fenwick Tree)
基本概念	一维数组，存储原数组从起始位置到当前下标的前缀和。	基于二进制索引的树状结构，支持动态维护前缀和。
构建时间复杂度	$O(n)$ (直接累加计算)	$O(n \log n)$ (逐个插入元素) 或 $O(n)$ (特殊优化构造)
区间和查询	$O(1)$ (直接通过前缀和相减)	$O(\log n)$ (需两次前缀查询相减)
单点更新时间复杂度	$O(n)$ (修改某个元素后需更新后续所有前缀和)	$O(\log n)$ (通过二进制索引逐层更新)
空间复杂度	$O(n)$	$O(n)$
适用场景	静态数据（无频繁修改）、频繁查询区间和。	动态数据（频繁修改和查询并存），如实时更新和统计问题。
扩展功能	仅支持区间和查询，功能单一。	支持多种操作：前缀和、单点更新、区间加、结合差分支持区间更新/区间查询等。
动态数据支持	不支持（每次更新需重建或线性更新，效率低）。	支持（高效动态维护）。
实现复杂度	简单，直接累加即可。	中等，需理解二进制索引和 lowbit 操作。
维度扩展	可扩展为二维前缀和（预处理后 $O(1)$ 查询子矩阵和）。	可扩展为多维树状数组（实现复杂度较高，但时间仍为 $O(\log^{k} n)$）。

受限线性表

栈(Stack)

Ø 概念：

首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过****它是一种特殊的线性表****而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

它的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。（先入后出）

栈顶：top

栈的作用

就近匹配

当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性

括号匹配检测案例如下：

//从第一个字符开始扫描
//--当遇见普通字符时忽略，
//--当遇见左括号时压入栈中
//--当遇见右括号时从栈中弹出栈顶符号，并进行匹配
//----匹配成功：继续读入下一个字符
//----匹配失败：立即停止，并报错
//结束：
//成功: 所有字符扫描完毕，且栈为空
//失败：匹配失败或所有字符扫描完毕但栈非空

void 利用栈判断字符串括号是否匹配_printfError(char* originStr,char* myErrorStr,char* p)
{
	printf("%s\r\n", myErrorStr);
	printf("--------------------[ErrorPos]-------------------\r\n");
	printf("%s\r\n",originStr);
	for (int i = 0; i < p-originStr; i++)
	{
		printf(" ");
	}
	printf("|\r\n");
	printf("-------------------------------------------------\r\n");
}


int 利用栈判断字符串括号是否匹配(char* str,char left,char right)
{
	if (left==right)
	{
		return 0;
	}
	if (!str)
	{
		return 0;
	}
	char* p = str;
	SeqStack stack = init_SeqStack();

	while (*p !=0)
	{
		if (*p== left)
		{
			push_SeqStack(stack, p);
		}
		if (*p== right)
		{
			if (size_SeqStack(stack)>0)
			{
				pop_SeqStack(stack);
			}
			else
			{
				利用栈判断字符串括号是否匹配_printfError(str,"多余右括号无匹配!",p);
				return 0;
			}
		}

		p++;
	}
	if (size_SeqStack(stack)==0)
	{
		return 1;//匹配
	}
	while (size_SeqStack(stack)>0)
	{
		利用栈判断字符串括号是否匹配_printfError(str, "多余左括号无匹配!", top_SeqStack(stack));
		pop_SeqStack(stack);
	}
	return 0;//不匹配
}

中缀表达式转后缀表达式计算

功能：为了解决运算符优先度问题

后缀表达式（由波兰科学家在20世纪50年代提出）

将运算符放在数字后面，符合计算机运算

我们习惯的数学表达式叫做中缀表达式，符合人类思考习惯

//中缀表达式=>后缀表达式
//符合人类思考习惯=>符合计算机运算
//如下：
5 + 4 => 5 4 +  
1 + 2 * 3 => 1 2 3 * +  
8 +( 3 – 1 ) * 5 => 8 3 1 – 5 * +

中缀转后缀算法案例:

//遍历中缀表达式中的数字和符号：
//--对于数字：直接输出
//--对于符号：
//----左括号：进栈  
//----运算符号：与栈顶符号进行优先级比较
//------若栈顶符号优先级低：此符号进栈  
//--------（默认栈顶若是左括号，左括号优先级最低）
//------若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
//----右括号：将栈顶符号弹出并输出，直到匹配左括号,将左括号和右括号同时舍弃
//遍历结束：将栈中的所有符号弹出并输出

后缀计算出结果算法案例:

//遍历后缀表达式中的数字和符号
//--对于数字：进栈
//--对于符号：
//----从栈中弹出右操作数
//----从栈中弹出左操作数
//----根据符号进行运算
//----将运算结果压入栈中
//遍历结束：栈中的唯一数字为计算结果

自己想出来的用双栈进行公式优先级计算的方法

double 双浮点四则运算(double firstNum, double secondNum, char operator)
{
	switch (operator)
	{
	case '+':
		return firstNum + secondNum;
		break;
	case '-':
		return firstNum - secondNum;
		break;
	case '*':
		return firstNum * secondNum;
		break;
	case '/':
		return firstNum / secondNum;
		break;
	}
}

//只允许一个小数点，否则结果无意义,结果为精确到小数后6位
double 字符数组转小数(char* numStr)
{
	if (!numStr)
	{
		return 0;
	}
	int spotPos = -1;
	int i;
	for (i = 0; numStr[i] != '\0'; i++)
	{
		if (numStr[i] == '.')
		{
			spotPos = i;
		}
	}
	double answer = 0;
	if (spotPos != -1)//有小数点
	{
		int numWeight = spotPos - 1;
		for (int j = 0; numStr[j] != '\0'; j++)
		{
			if (numStr[j] == '.')
			{
				continue;
			}
			int tmp = numStr[j] - '0';
			answer += pow(10, numWeight)*tmp;


			numWeight--;
		}
	}
	else
	{
		int numWeight = i - 1;
		for (int j = 0; numStr[j] != '\0'; j++)
		{
			int tmp = numStr[j] - '0';
			answer += pow(10, numWeight)*tmp;
			numWeight--;
		}
	}
		return answer;
}

//对两个栈中单符号进行运算后将返回运算结果
double 双栈单符号运算(SeqStack numStack,SeqStack operatorStack)
{
	char topCh = *(char*)top_SeqStack(operatorStack);
	pop_SeqStack(operatorStack);
	double secondNum = *(double*)top_SeqStack(numStack);
	pop_SeqStack(numStack);
	double firstNum=0;
	if (top_SeqStack(numStack) != NULL)
	{
		firstNum = *(double*)top_SeqStack(numStack);
		pop_SeqStack(numStack);
	}
	return 双浮点四则运算(firstNum, secondNum, topCh);
}


//运算过程中允许使用的最大double类型空间使用个数
#define MAXALLOW 999

//若为符号  右括号，就近匹配左括号，将中间运算做完，将结果入数字栈
//第一个要解决的是多位数字问题
double 双栈公式计算法(char* formulas)
{
	if (!formulas)
	{
		return;
	}
	if (!利用栈判断字符串括号是否匹配(formulas, '(', ')'))//符号匹配校验
	{
		return;
	}
	
	int dIndex = 0;
	double dArray[MAXALLOW] = { 0 };
	SeqStack numStack = init_SeqStack();
	SeqStack operatorStack = init_SeqStack();
	dynamicChArray chArray = init_dynamicChArray(5);
	for (int i = 0; formulas[i] != '\0'; i++)
	{
		//////////////////////////////////////////////////////////////////////////此处思考解决多位数字
		if ((formulas[i] <= '9'&&formulas[i] >= '0')||(formulas[i] =='.'))//若为单个数字或者小数点，入数字字符动态数组(此处未规避非单小数点风险)
		{
			append_dynamicChArray(chArray, formulas[i]);
		}
		else//若为符号入栈
		{
			if (size_dynamicChArray(chArray)>0)//当遇到任意符号时将累积下来的数字字符转成小数入数字栈
			{
				if (dIndex < MAXALLOW)
				{
					dArray[dIndex] = 字符数组转小数(pChar_dynamicChArray(chArray));
					push_SeqStack(numStack, &dArray[dIndex]);
					clear_dynamicChArray(chArray);
					dIndex++;
				}
				else//溢出错误
					return;
			}
			//处理括号
			char tmpCh;
			char* top = top_SeqStack(operatorStack);
			//处理四则运算优先级
			//按照优先级，当栈顶是*，/而准备入栈的是+—的时候，直接运算*，/后再入栈
			if (top && (*top == '*' || *top == '/') && (formulas[i] == '+' || formulas[i] == '-'))
			{
				//结果的浮点数入数字栈
				dArray[dIndex] = 双栈单符号运算(numStack, operatorStack);
				push_SeqStack(numStack, &dArray[dIndex]);
				dIndex++;
				push_SeqStack(operatorStack, &formulas[i]);
			}
			else if (formulas[i] == ')')//遇到右括号，循环进行配对括号中所有计算
			{
				
				while ((tmpCh = *(char*)top_SeqStack(operatorStack)) != '(')//将符号栈中除了左括号之外的所有符号运算完
				{
					if (size_SeqStack(numStack) < 2)//并未具体针对（1）这样的给出解决方案
					{
						return;
					}
					dArray[dIndex] = 双栈单符号运算(numStack,operatorStack);
					push_SeqStack(numStack, &dArray[dIndex]);
					dIndex++;
				}
				pop_SeqStack(operatorStack);//弹出多余左括号
			}
			else 
				push_SeqStack(operatorStack, &formulas[i]);




		}

	}
	if (size_dynamicChArray(chArray) > 0)//当遇到任意符号时将累积下来的数字字符转成小数入数字栈(此处重复是为了避免数字封尾，最后的数字无法入数字栈)
	{
		if (dIndex < MAXALLOW)
		{
			dArray[dIndex] = 字符数组转小数(pChar_dynamicChArray(chArray));
			push_SeqStack(numStack, &dArray[dIndex]);
			clear_dynamicChArray(chArray);
			dIndex++;
		}
		else//溢出错误
			return;
	}



	//括号，*，/已经已全部剔除完毕情况的运算
	while (size_SeqStack(operatorStack) > 0)//符号栈非空
	{
		dArray[dIndex] = 双栈单符号运算(numStack,operatorStack);
		push_SeqStack(numStack, &dArray[dIndex]);
		dIndex++;
	}
	double answer = *(double*)top_SeqStack(numStack);
	//空间释放
	destroy_SeqStack(&numStack);
	destroy_SeqStack(&operatorStack);
	destroy_dynamicChArray(&chArray);
	return answer;
}

栈主要是两种

栈的顺序存储（数组）

栈的顺序存储案例

SeqStack.h顺序栈头文件

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\SEQSTACK\SeqStack.h 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 18 15：47 
* @文件描述： 顺序栈头文件
****************************************************** ************************/  
#pragma once


#define MAX_STACK_LENGHT 100



typedef void* SeqStack;


//初始化栈
SeqStack init_SeqStack();

//入栈
void push_SeqStack(SeqStack _stack,void* data);

//出栈
void pop_SeqStack(SeqStack _stack);

//返回栈顶
void* top_SeqStack(SeqStack _stack);

//返回栈大小
int size_SeqStack(SeqStack _stack);

//判断栈是否为空
int isEmpty_SeqStack(SeqStack _stack);

//销毁栈
void destroy_SeqStack(SeqStack* _stack);

SeqStack.c顺序栈源文件

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\SEQSTACK\SeqStack.c 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 18 15：46 
* @文件描述： 顺序栈源文件
****************************************************** ************************/  
#include "SeqStack.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//该结构体放在源文件中的目的是当把这个文件生成库文件时，可以避免用户直接在头文件中直接看到该结构的真实情况
typedef struct __SeqStack
{
	void* data[MAX_STACK_LENGHT];
	int m_Size;
}_SeqStack;


SeqStack init_SeqStack()
{
	_SeqStack* stack = (_SeqStack*)malloc(sizeof(_SeqStack));
	if (!stack)
	{
		return;
	}
	stack->m_Size = 0;
	memset(stack->data, NULL, MAX_STACK_LENGHT*sizeof(void*));
	return stack;

}


void push_SeqStack(SeqStack _stack, void* data)
{
	_SeqStack* stack = _stack;
	if (!stack||!data)
	{
		return;
	}
	if (stack->m_Size==MAX_STACK_LENGHT)//超出容量
	{
		return;
	}
	stack->data[stack->m_Size++] = data;
}


void pop_SeqStack(SeqStack _stack)
{
	_SeqStack* stack = _stack;
	if (!stack )
	{
		return;
	}
	stack->data[stack->m_Size--] = NULL;
}


void* top_SeqStack(SeqStack _stack)
{
	_SeqStack* stack = _stack;
	if (!stack )//无栈
	{
		return NULL;
	}
	if (stack->m_Size==0)//空栈
	{
		return NULL;
	}
	return stack->data[stack->m_Size - 1];
}


int size_SeqStack(SeqStack _stack)
{
	_SeqStack* stack = _stack;
	if (!stack)
	{
		return -1;
	}
	return stack->m_Size;
}



int isEmpty_SeqStack(SeqStack _stack)
{
	_SeqStack* stack = _stack;
	if (!stack)
	{
		return -1;
	}
	if (stack->m_Size==0)
	{
		return 1;
	}
	return 0;
}



void destroy_SeqStack(SeqStack* _stack)
{
	if (*_stack)
	{
		_SeqStack** stack = _stack;
		free(*stack);
		*stack = NULL;
	}
}

栈的链式存储（链表）

栈的链式存储案例

头节点做栈顶，利于压栈出栈的操作

LinkListStack.h链栈头文件

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\SEQSTACK\LinklistStack.h 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 20 14：24 
* @文件描述： 栈链头文件
****************************************************** ************************/  
#pragma once

typedef void* LStack;

//初始化栈
LStack init_LStack();

//入栈
void push_LStack(LStack _stack, void* data);

//出栈
void pop_LStack(LStack _stack);

//返回栈顶
void* top_LStack(LStack _stack);

//返回栈大小
int size_LStack(LStack _stack);

//判断栈是否为空
int isEmpty_LStack(LStack _stack);

//销毁栈
void destroy_LStack(LStack* _stack);

LinkListStack.c链栈源文件

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\SEQSTACK\LinklistStack.c 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 20 14：24 
* @文件描述： 栈链源文件
****************************************************** ************************/  
#include "LinklistStack.h"
#include <stdio.h>

typedef struct _LStackNode
{
	struct _LStackNode* next;
}LStackNode;


typedef struct __LStack
{
	LStackNode* pHeader;
	int m_size;
}_LStack;


LStack init_LStack()
{
	_LStack* stack = malloc(sizeof(_LStack));
	if (!stack)
	{
		return;
	}
	stack->pHeader = NULL;
	stack->m_size = 0;
	return stack;
}


void push_LStack(LStack _stack, void* data)
{
	_LStack* stack =_stack;
	LStackNode* pPush = data;
	if (!stack||!pPush)
	{
		return;
	}
	//入栈操作--链表头插
	pPush->next = stack->pHeader;
	stack->pHeader = pPush;
	stack->m_size++;
}

void pop_LStack(LStack _stack)
{
	_LStack* stack = _stack;
	if (!stack)
	{
		return;
	}
	//出栈操作--链表头删
	stack->pHeader = stack->pHeader->next;
	stack->m_size--;
}

void* top_LStack(LStack _stack)
{
	_LStack* stack = _stack;
	if (!stack)
	{
		return;
	}
	return stack->pHeader;
}


int size_LStack(LStack _stack)
{
	_LStack* stack = _stack;
	if (!stack)
	{
		return;
	}
	return stack->m_size;
}

int isEmpty_LStack(LStack _stack)
{
	_LStack* stack = _stack;
	if (!stack)
	{
		return -1;
	}
	if (stack->m_size)
	{
		return 0;
	}
	return 1;


}


void destroy_LStack(LStack* _stack)
{
	_LStack** stack = _stack;
	if (*stack)
	{
		free(*stack);
		*stack = NULL;
	}

}

单调栈

栈里面的元素是递增或递减的就是单调栈

单调栈适合于求当前元素左或右第一个比当前元素大或小的元素

单调栈动画演示

以单调递增栈为例:只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈。那么，这样就保证了，栈中保留的都是比当前入栈元素大的值，并且从栈顶到栈底的元素值是单调递增的。

队列(Queue)(发音和Q一样)

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队头元素：front 队尾元素：back 队列和栈一样不提供遍历功能

队列的顺序存储案例(基于动态数组)

顺序队列的头文件seqQueue.h

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\队列案例\QUEUE\seqQueue.h 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 27 12：56 
* @文件描述： 顺序队列的头文件（引用了动态数组文件）
****************************************************** ************************/  
#pragma once

#define  INIT_CAPACITY 1024

typedef void* seqQueue;

//初始化顺序队列
seqQueue init_seqQueue();

//入队
void push_seqQueue(seqQueue queue,void* data);

//出队
void pop_seqQueue(seqQueue queue);

//队头
void* front_seqQueue(seqQueue queue);

//队尾
void* back_seqQueue(seqQueue queue);

//队内项数
int size_seqQueue(seqQueue queue);

//清空队列
void clear_seqQueue(seqQueue queue);

//是否空
int isEmpty_seqQueue(seqQueue queue);

//销毁队列
void destroy_seqQueue(seqQueue* queue);

//调试显示
void debugShow_seqQueue(seqQueue queue, void(*myPrintf)(void*));

顺序队列的源文件seqQueue.c

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\队列案例\QUEUE\seqQueue.c 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 27 12：56 
* @文件描述： 顺序队列的源文件（引用了动态数组文件）
****************************************************** ************************/  
#include "dynamicArray.h"
#include "seqQueue.h"

seqQueue init_seqQueue()
{
	DynamicArray* array = init_DynamicArray(INIT_CAPACITY);
	return array;
}


void push_seqQueue(seqQueue queue, void* data)
{
	if (!queue||!data)
	{
		return;
	}
	DynamicArray* array = queue;
	insert_DynamicArray(queue, array->m_size, data);
}


void pop_seqQueue(seqQueue queue)
{
	if (!queue)
	{
		return;
	}
	DynamicArray* array = queue;
	if (array->m_size<=0)
	{
		return;
	}
	removeByPos_DynamicArray(queue, 0);
}

void* front_seqQueue(seqQueue queue)
{
	if (!queue)
	{
		return NULL;
	}
	DynamicArray* array = queue;
	return array->ArrayAddr[0];
}

void* back_seqQueue(seqQueue queue)
{
	if (!queue)
	{
		return NULL;
	}
	DynamicArray* array = queue;
	return array->ArrayAddr[array->m_size-1];
}


int size_seqQueue(seqQueue queue)
{
	if (!queue)
	{
		return -1;
	}
	DynamicArray* array = queue;
	return array->m_size;
}

void clear_seqQueue(seqQueue queue)
{
	if (!queue)
	{
		return;
	}
	clear_DynamicArray(queue);
}

int isEmpty_seqQueue(seqQueue queue)
{
	if (!queue)
	{
		return -1;
	}
	DynamicArray* array = queue;
	if (array->m_size==0)
	{
		return 1;
	}

	return 0;
}



void destroy_seqQueue(seqQueue* queue)
{
	if (!(*queue))
	{
		return;
	}
	destroy_DynamicArray(queue);
}

void debugShow_seqQueue(seqQueue queue, void(*myShow)(void*))
{
	if (!queue||!myShow)
	{
		return;
	}
	printf("-------------------------------------------------\r\n");
	printf("队头\r\n");
	foreach_DynamicArray(queue, myShow);
	printf("队尾\r\n");
	printf("-------------------------------------------------\r\n");
	
}

队列的链式存储案例

链队列的头文件LinkQueue.h

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\队列案例\QUEUE\LinkQueue.h 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 27 20：40 
* @文件描述：	链表队列头文件
****************************************************** ************************/  
#pragma once

typedef void* linkQueue;

//初始化
linkQueue init_linkQueue();

//入队列
void push_linkQueue(linkQueue _queue,void* data);

//出队列
void pop_linkQueue(linkQueue _queue);

//队头元素
void* front_linkQueue(linkQueue _queue);

//队尾元素
void* back_linkQueue(linkQueue _queue);

//队中项个数
int size_linkQueue(linkQueue _queue);

//是否空
int isEmpty_linkQueue(linkQueue _queue);

//清空队列
void clear_linkQueue(linkQueue _queue);

//销毁队列
void destroy_linkQueue(linkQueue* _queue);

链队列的源文件LinkQueue.c

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\队列案例\QUEUE\LinkQueue.c 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 11 / 27 20：40 
* @文件描述： 链表队列源文件
****************************************************** ************************/  
#pragma once
#include "LinkQueue.h"
#include <stdlib.h>

typedef struct _QueueNode
{
	struct  QueueNode* next;
}QueueNode;

typedef struct __LinkQueue
{
	QueueNode* pHeader;//指向头元素
	QueueNode* pTail;//指向尾元素
	int m_size;
}_LinkQueue;


linkQueue init_linkQueue()
{
	_LinkQueue* queue = malloc(sizeof(_LinkQueue));
	if (!queue)
	{
		return NULL;
	}
	queue->m_size = 0;
	queue->pHeader = NULL;
	queue->pTail = NULL;
	return queue;
}

void push_linkQueue(linkQueue _queue, void* data)
{
	_LinkQueue* queue = _queue;
	QueueNode* node = data;
	if (!queue||!data)
	{
		return;
	}
	node->next = NULL;
	if (queue->m_size==0)//初始化
	{
		queue->pTail = node;
		queue->pHeader = node;
	}
	else
	{
		queue->pTail->next = node;
		queue->pTail = node;
	}
	queue->m_size++;
}


void pop_linkQueue(linkQueue _queue)
{
	_LinkQueue* queue = _queue;
	if (!queue)
	{
		return;
	}
	if (queue->m_size<=0)
	{
		return;
	}
	queue->pHeader = queue->pHeader->next;
	queue->m_size--;
	if (queue->m_size == 0)//唯一一个节点被删除的时候，尾节点重新变为空
	{
		queue->pTail = NULL;
	}
}

void* front_linkQueue(linkQueue _queue)
{
	_LinkQueue* queue = _queue;
	if (!queue)
	{
		return;
	}
	return queue->pHeader;
}


void* back_linkQueue(linkQueue _queue)
{
	_LinkQueue* queue = _queue;
	if (!queue)
	{
		return;
	}
	return queue->pTail;
}

int size_linkQueue(linkQueue _queue)
{
	_LinkQueue* queue = _queue;
	if (!queue)
	{
		return -1;
	}
	return queue->m_size;
}

int isEmpty_linkQueue(linkQueue _queue)
{
	_LinkQueue* queue = _queue;
	if (!queue)
	{
		return -1;
	}
	if (queue->m_size==0)
	{
		return 1;
	}
	return 0;
}

void clear_linkQueue(linkQueue _queue)
{
	_LinkQueue* queue = _queue;
	if (!queue)
	{
		return;
	}
	queue->pHeader = NULL;
	queue->pTail = NULL;
	queue->m_size = 0;
}

void destroy_linkQueue(linkQueue* _queue)
{
	_LinkQueue** queue = _queue;
	if (*queue)
	{
		free(*queue);
		*queue = NULL;
	}
}

debugShow_linkQueue(linkQueue _queue, void(*myShow)(void*))
{
	_LinkQueue* queue = _queue;
	if (!queue)
	{
		return;
	}
	printf("-------------------------------------------------\r\n");
	
	printf("队头\r\n");
	QueueNode* pCurrent = queue->pHeader;
	for (int i = 0; i < queue->m_size; i++)
	{
		myShow(pCurrent);
		pCurrent = pCurrent->next;
	}
	printf("队尾\r\n");
	printf("-------------------------------------------------\r\n");
}

树和二叉树

树的定义：由一个或多个(n≥0)节点组成的有限集合T，有且仅有一个节点称为根（root），当n>1时，其余的节点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。

树的结构特点：

非线性结构，有一个直接前驱，但可能有多个直接后继（1:n）
树的定义具有递归性，树中还有树。
树可以为空，即节点个数为0。
根 —— 即根节点(没有前驱)
叶子 —— 即终端节点(没有后继)
森林 —— 指m棵不相交的树的集合(例如删除A后的子树个数)
有序树 —— 节点各子树从左至右有序，不能互换（左为第一）
无序树 —— 节点各子树可互换位置。
双亲 —— 即上层的那个节点(直接前驱) parent
孩子 —— 即下层节点的子树 (直接后继) child
兄弟 —— 同一双亲下的同层节点（孩子之间互称兄弟）sibling
堂兄弟 —— 即双亲位于同一层的节点（但并非同一双亲）cousin
祖先 —— 即从根到该节点所经分支的所有节点
子孙 —— 即该节点下层子树中的任一节点
节点 —— 即树的数据元素
节点的度 —— 节点挂接的子树数（有几个直接后继就是几度）
节点的层次 —— 从根到该节点的层数（根节点算第一层）
终端节点 —— 即度为0的节点，即叶子
分支节点 —— 除树根以外的节点（也称为内部节点）
树的度 —— 所有节点度中的最大值（Max{各节点的度}）
树的深度(或高度) —— 指所有节点中最大的层数（Max{各节点的层次}）

上图中的节点数＝ 13，树的度＝ 3，树的深度＝ 4

树的表示法

图形表示法

事物之间的逻辑关系可以通过图的形式很直观的表示出来，如下图：

广义表表示法

根作为由子树森林组成的表的名字写在表的左边。

用广义表表示法表示上图：

1	中国（河北（保定，石家庄），广东（广州，东莞），山东（青岛，济南））

左孩子右兄弟表示法

左孩子右兄弟表示法可以将一颗多叉树转化为一颗二叉树：

左孩子右兄弟表示法节点的结构

节点有两个指针域，其中一个指针指向子节点，另一个指针指向其兄弟节点。

二叉树概念

二叉树的发展: 链表->二叉树->查找(搜索)二叉树->平衡二叉树->红黑树

目的(针对上面): 为了便于增删数据但效率低->复杂结构使二分成为可能->加上顺序:增加查找效率->规避退化为链表的情况,保证查找效率稳定(增删操作繁琐)->增删操作和查找效率的综合考量

二叉树基本概念

定义：n（n≥0）个节点的有限集合，由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

逻辑结构：一对二（1：2）

基本特征:

每个节点最多只有两棵子树（不存在度大于2的节点）；
左子树和右子树次序不能颠倒（有序树）。

**基本形态:**（最右边表示连根节点都没有的也算树）

二叉树性质

性质1: 在二叉树的第i层上至多有2i-1个节点（i>0）
性质2: 深度为k的二叉树至多有2k-1个节点（k>0）
性质3: 对于任何一棵二叉树，若度为2的节点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）
n 性质4: 具有n个节点的完全二叉树的深度必为log₂n+1(log₂n取整)(如 log2 (15) 点击 15 log / 2 log =)
性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的节点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

使用性质5可以使用完全二叉树实现树的顺序存储。

如果不是完全二叉树咋整???

缺点：①浪费空间；②插入、删除不便

概念解释

满二叉树

一棵深度为k 且有2k -1个节点的二叉树。

特点：每层都“充满”了节点

完全二叉树

除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。

理解：k-1层与满二叉树完全相同，第k层节点尽力靠左

二叉树的表示

二叉链表示法

存储结构：

节点数据类型定义：

typedef struct BiTNode
{
	int		data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

三叉链表表示法

存储结构：

节点数据类型定义：

//三叉链表
typedef struct TriTNode 
{
	int data;
	//左右孩子指针
	struct TriTNode *lchild, *rchild;
	struct TriTNode *parent;
}TriTNode, *TriTree;

二叉树的遍历

Ø 遍历定义

指按某条搜索路线遍访每个节点且不重复（又称周游）。

Ø 遍历用途

它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

Ø 遍历方法

DLR — 先(根)序遍历，即先根再左再右
LDR — 中(根)序遍历，即先左再根再右(此遍历方式正是按照顺序排序遍历)
LRD — 后(根)序遍历，即先左再右再根

注：“先、中、后”的意思是指访问的节点D是先于子树出现还是后于子树出现。

从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问节点的时机不同。

从虚线的出发点到终点的路径上，每个节点经过3次。

第1次经过时访问＝先序遍历
第2次经过时访问＝中序遍历
第3次经过时访问＝后序遍历

代码中的先序中序后序的区别

void RecursionShow_BinaryTree(TreeNode& root)
{
	if (!root)
	{
		return;
	}
	//cout<<root.data<<endl;//先序遍历
	RecursionShow_BinaryTree(root->lchild);
  //cout<<root.data<<endl;//中序遍历
	RecursionShow_BinaryTree(root->rchild);
  //cout<<root.data<<endl;//后序遍历
}

打印代码放在哪里,决定了先序还是中序还是后序遍历

实现二叉树(递归遍历)

BTree.h头文件

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\二叉树案例\BTREE\BTree.h 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 12 / 04 20：46 
* @文件描述： 二叉树头文件
****************************************************** ************************/  
#pragma once
typedef struct _BTreeNode
{
	void* data;
	struct _BTreeNode *lchild, *rchild;
}BTreeNode,*PBTreeNode;

typedef struct __BTree
{
	PBTreeNode root;
	int m_size;
}_BTree,*PBTree;

//自定义的myCompare函数,返回1表示myInsertData<TreeData
//返回0表示myInsertData==TreeData
//返回-1表示myInsertData>TreeData

typedef void* BTree;

typedef void* TreeNode;

//初始化二叉树
BTree init_BinaryTree();

//顺序插入(myCompare)
void insert_BinaryTree(BTree _tree,void* data, int(*myCompare)(void* myInsertData, void* TreeData));

//层序遍历
void show_BinaryTree(PBTreeNode root, void(*myShow)(void*));

//以下均为递归版对应功能的封装////////////////////////////////////////////
//内部采用递归实现
void insert_BinaryTree2(BTree tree,void* data,int(*myCompare)(void* myInsertData,void* TreeData));

//先序遍历
void firstShow_BinaryTree(BTree _tree, void(*myShow)(void*));

//计算树的叶子节点个数
int calculateLeafNum_BinaryTree(BTree _tree);

//计算树的层数
int GetHeight_BinaryTree(BTree _tree);

//二叉树拷贝
BTree Copy_BinaryTree(BTree _tree);

//释放二叉树
void Release_BinaryTree(BTree* _tree);

//////////////////////////////////////////////////////////////////////////

//递归版先序遍历二叉树
void firstRecursionShow_BinaryTree(TreeNode root, void(*myShow)(void*));

//递归版中序遍历二叉树
void middleRecursionShow_BinaryTree(TreeNode root, void(*myShow)(void*));

//递归版后序遍历二叉树
void lastRecursionShow_BinaryTree(TreeNode root, void(*myShow)(void*));

//递归版计算树的叶子节点个数
void RecursionCalculateLeafNum_BinaryTree(TreeNode root, int* num);

//递归查找元素,返回节点
PBTreeNode findNode(PBTreeNode root,void* data,int(*myCompare)(void* myInsertData,void* TreeData));

//递归版计算树的层数
int RecursionGetHeight_BinaryTree(TreeNode root);

//递归版二叉树拷贝
TreeNode RecursionCopy_BinaryTree(TreeNode root);

//递归版释放二叉树
void RecursionRelease_BinaryTree(TreeNode* root);

BTree.c源文件

/***************************************************** ************************* 
* @版权所有（c）2020，Peng，保留所有权利。 
* @文件路径:    C:\USERS\ADMINISTRATOR\DESKTOP\C语言学习案例（内含数据结构）\二叉树案例\BTREE\BTree.c 
* @版本：1.0版 
* @作者：Peng 
* @创建时间：2020 / 12 / 04 20：47 
* @文件描述： 二叉树源文件
****************************************************** ************************/  
#include "BTree.h"
#include <stdio.h>
#include <stdlib.h>

BTree init_BinaryTree()
{
	PBTree tree = malloc(sizeof(_BTree));
	if (!tree)
	{
		return NULL;
	}
	tree->m_size = 0;
	tree->root = NULL;
	return tree;
}


void insert_BinaryTree(BTree _tree,void* data,int(*myCompare)(void* myInsertData,void* TreeData))
{
	if (!_tree ||!data)
	{
		return;
	}
	PBTree tree = _tree;
	if (!tree->root)//空树
	{
		tree->root = malloc(sizeof(BTreeNode));
		if (!tree->root)
		{
			return;
		}
		tree->root->data = data;
		tree->root->lchild = NULL;
		tree->root->rchild = NULL;
		tree->m_size++;
	}
	else
	{
		PBTreeNode Pcurrent = tree->root;
		while (Pcurrent!=NULL)
		{
			if (myCompare(data,Pcurrent->data)==1)//1表示插入左边
			{
				if (Pcurrent->lchild == NULL)//执行插入操作
				{
					Pcurrent->lchild = malloc(sizeof(BTreeNode));//未做成功校验
					Pcurrent->lchild->data = data;
					Pcurrent->lchild->lchild = NULL;
					Pcurrent->lchild->rchild = NULL;
					tree->m_size++;
					return;
				}
				Pcurrent = Pcurrent->lchild;
			}
			else
			{
				if (Pcurrent->rchild == NULL)//执行插入操作
				{
					Pcurrent->rchild = malloc(sizeof(BTreeNode));//未做成功校验
					Pcurrent->rchild->data = data;
					Pcurrent->rchild->lchild = NULL;
					Pcurrent->rchild->rchild = NULL;
					tree->m_size++;
					return;
				}
				Pcurrent = Pcurrent->rchild;
			}
		}
	}
}

//层序遍历
void show_BinaryTree(PBTreeNode root, void(*myShow)(void*))
{
    if(!root)
        return;
    vector<vector<PBTreeNode> > levelVec;//用于临时存放每层的节点
    PBTreeNode curNode = root;
    vector<PBTreeNode> tmpVec;
    tmpVec.push_back(root);
    levelVec.push_back(tmpVec);
    for(int i=0;i<levelVec.size();i++)
    {
        tmpVec.clear();
        while(levelVec[i].size()>0)
        {
            curNode = levelVec[i].front();
            levelVec[i].erase(levelVec[i].begin());
            myShow(curNode->data);
            if(curNode->lchild)tmpVec.push_back(curNode->lchild);
            if(curNode->rchild)tmpVec.push_back(curNode->rchild);
        }
        if(tmpVec.size()>0)
            levelVec.push_back(tmpVec);
        std::cout<<std::endl;
    }
    
}

void firstShow_BinaryTree(BTree _tree, void(*myShow)(void*))
{
	if (!_tree||!myShow)
	{
		return;
	}
	PBTree tree = _tree;
	firstRecursionShow_BinaryTree(tree->root, myShow);
}


//递归插入
void insert_BinaryTree_digui(PBTreeNode* rootAdd,void* data,int(*myCompare)(void* myInsertData,void* TreeData))
{
    if (!data)
	{
		return;
	}
	if(!*(rootAdd))
    {
         *rootAdd = (PBTreeNode)malloc(sizeof(_BTreeNode));
         (*rootAdd)->data = data;
         (*rootAdd)->lchild = NULL;
         (*rootAdd)->rchild = NULL;
         return;
    }
    if(myCompare(data,(*rootAdd)->data)==1)//1表示插入左边
    {
        insert_BinaryTree_digui(&(*rootAdd)->lchild,data,myCompare);
    }
    else{
        insert_BinaryTree_digui(&(*rootAdd)->rchild,data,myCompare);
    }
	
}

//内部采用递归实现
void insert_BinaryTree2(BTree tree,void* data,int(*myCompare)(void* myInsertData,void* TreeData))
{
    if (!tree ||!data)
	{
		return;
	}
	PBTree pTree = (PBTree)tree;
    insert_BinaryTree_digui(&pTree->root,data,myCompare);
    pTree->m_size++;
}


int calculateLeafNum_BinaryTree(BTree _tree)
{
	if (!_tree )
	{
		return 0;
	}
	PBTree tree = _tree;
	int num = 0;
	RecursionCalculateLeafNum_BinaryTree(tree->root, &num);
	return num;
}

int GetHeight_BinaryTree(BTree _tree)
{
	if (!_tree)
	{
		return 0;
	}
	PBTree tree = _tree;
	int result = RecursionGetHeight_BinaryTree(tree->root);
}

BTree Copy_BinaryTree(BTree _tree)
{
	if (!_tree)
	{
		return NULL;
	}
	PBTree tree = _tree;
	PBTree newTree = malloc(sizeof(_BTree));
	if (!newTree)
	{
		return NULL;
	}
	newTree->m_size = tree->m_size;
	newTree->root = RecursionCopy_BinaryTree(tree->root);
	return newTree;
}


void Release_BinaryTree(BTree* _tree)
{
	if (!*_tree)
	{
		return;
	}
	PBTree tree = *_tree;
	if (tree->root)
	{
		RecursionRelease_BinaryTree(&tree->root);
	}
	if (tree)
	{
		free(tree);
		*_tree = NULL;
	}
}


void firstRecursionShow_BinaryTree(TreeNode root,void(*myShow)(void*))
{
	if (!root || !myShow)
	{
		return;
	}
	PBTreeNode tree = root;
	myShow(tree->data);
	firstRecursionShow_BinaryTree(tree->lchild, myShow);
	firstRecursionShow_BinaryTree(tree->rchild, myShow);
}

void middleRecursionShow_BinaryTree(TreeNode root, void(*myShow)(void*))
{
	if (!root || !myShow)
	{
		return;
	}
	PBTreeNode tree = root;
	middleRecursionShow_BinaryTree(tree->lchild, myShow);
	myShow(tree->data);
	middleRecursionShow_BinaryTree(tree->rchild, myShow);
}

void lastRecursionShow_BinaryTree(TreeNode root, void(*myShow)(void*))
{
	if (!root||!myShow)
	{
		return;
	}
	PBTreeNode tree = root;
	lastRecursionShow_BinaryTree(tree->lchild, myShow);
	lastRecursionShow_BinaryTree(tree->rchild, myShow);
	myShow(tree->data);
}


void RecursionCalculateLeafNum_BinaryTree(TreeNode root,int* num)
{
	if (!root||!num)
	{
		return;
	}
	PBTreeNode tree = root;
	if (!tree->lchild&&!tree->rchild)
	{
		(*num)++;
	}
	RecursionCalculateLeafNum_BinaryTree(tree->lchild, num);
	RecursionCalculateLeafNum_BinaryTree(tree->rchild, num);
}


int RecursionGetHeight_BinaryTree(TreeNode root)
{
	if (!root)
	{
		return 0;
	}
	PBTreeNode tree = root;
	int left = RecursionGetHeight_BinaryTree(tree->lchild);
	int right = RecursionGetHeight_BinaryTree(tree->rchild);
	return left > right ? left + 1 : right + 1;
}

TreeNode RecursionCopy_BinaryTree(TreeNode root)
{
	if (!root)
	{
		return NULL;
	}
	PBTreeNode oldTree = root;
	PBTree leftTree= RecursionCopy_BinaryTree(oldTree->lchild);
	PBTree rightTree = RecursionCopy_BinaryTree(oldTree->rchild);
	PBTreeNode newNode = malloc(sizeof(BTreeNode));
	newNode->data = oldTree->data;
	newNode->lchild = leftTree;
	newNode->rchild = rightTree;
	return newNode;
}

void RecursionRelease_BinaryTree(TreeNode* root)
{
	if (!(*root))
	{
		return;
	}
	PBTreeNode tree = *root;
	RecursionRelease_BinaryTree(&tree->lchild);
	RecursionRelease_BinaryTree(&tree->rchild);
	//最后释放根节点
	free(*root);
	*root = NULL;
}

//查找元素,返回节点
PBTreeNode findNode(PBTreeNode root,void* data,int(*myCompare)(void* myInsertData,void* TreeData))
{
    if (!root || !data)
	{
		return NULL;
	}
    if(myCompare(data,root->data)==1)//小于
        return findNode(root->lchild,data,myCompare);
    else if(myCompare(data,root->data)==-1)
        return findNode(root->rchild,data,myCompare);
    else
        return root;
}

递归遍历的复杂度:

时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

其他遍历方法

栈回溯迭代遍历

递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同，具体实现可以看下面的代码。

栈回溯流程如下

先序遍历(最直观)

创建一个空栈，并将根节点入栈。

当栈不为空时，执行以下步骤：

弹出栈顶节点，访问该节点。

如果该节点有右子节点，将右子节点入栈。

如果该节点有左子节点，将左子节点入栈。

重复步骤2，直到栈为空。

中序遍历(要变化一下)

创建一个空栈。

当栈不为空时或者当前节点不为空的时候，执行以下步骤：

将当前节点以及他的左子节点依次入栈，直到节点为空。

弹出栈顶节点，访问该节点。

将当前节点指向右子节点。

重复步骤2，直到栈为空且当前节点为空。

后序遍历(最复杂)

创建两个栈：stack和output,并将根节点入栈stack。

当栈stack不为空时，执行以下步骤：

弹出栈顶节点，将节点值插入栈output的顶部。

如果该节点有左子节点，将左子节点入栈stack。

如果该节点有右子节点，将右子节点入栈stack。

重复步骤3，直到栈stack为空。

弹出栈output中的元素，即为后序遍历的结果。

中序遍历

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {//按左子节点依次放入stk
                stk.push(root);
                root = root->left;
            }
            root = stk.top();//回溯stk
            stk.pop();
            res.push_back(root->val);//输出结果
            root = root->right;//往右子节点前进
        }
        return res;
    }

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

Morris遍历

相比栈回溯迭代法要更省空间，但费时间

利用上了叶子节点的空指针记录线索

【建议精准空降到07:00】

精准空降到07:00|720x360

Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 xxx）：

morris遍历的实现原则

记作当前节点为cur。

如果cur无左孩子，cur向右移动（cur=cur.right）
如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
1. 如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
2. 如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）

实现以上的原则，即实现了morris遍历。

morris遍历的实质:建立一种机制，对于没有左子树的节点只到达一次，对于有左子树的节点会到达两次

先序遍历:到达每个节点的时候先打印节点信息

中序遍历:对于没有左子树的节点第一次到达就打印(在morris序中也只会访问一次),对于有左子树的节点第二次到达才打印(在morris序中会访问两次)

后序遍历:只在对于有左子树的节点的第二次访问时机时,打印其左树右边界.遍历完后再逆序打印整棵树的右边界

morris先序/中序遍历

vector<int> traversal(TreeNode* root) {
        vector<int> res;
        TreeNode *predecessor = nullptr;

        while (root != nullptr) {
            if (root->left != nullptr) {//有左节点的节点就是morris序可以访问两次的节点
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root->left;
                while (predecessor->right != nullptr && predecessor->right != root) {
                    predecessor = predecessor->right;
                }
                
                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor->right == nullptr) {//第一次访问
                  	//res.push_back(root->val);  // 先序遍历需要!!!
                    predecessor->right = root;
                    root = root->left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {//第二次访问
                    res.push_back(root->val);//中序遍历需要!!!
                    predecessor->right = nullptr;
                    root = root->right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {//morris序只能访问一次的节点
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树的节点个数。Morris 遍历中每个节点会被访问一到两次，因此最大时间复杂度为 O(2n)=O(n)。
空间复杂度：O(1)。

morris后序遍历

只在对于有左子树的节点的第二次访问时机时,打印其左树右边界.遍历完后再逆序打印整棵树的右边界

后序遍历教程|720x360

//从from开始,只关心right指针,并且认为right指针就是单链表的next指针,单链表逆序
    TreeNode* reverseRightEdge(TreeNode* from)
    {
        TreeNode* pre=NULL;
        TreeNode* next=NULL;
        while(from != NULL)
        {
            next = from->right;
            from->right=pre;
            pre=from;
            from=next;
        }
        return pre;
    }

    //返回以head为头的树的逆序右边界(右边界=一路右节点)
    vector<int> rightEdge(TreeNode* head)
    {   
        vector<int> res;
        TreeNode* tail = reverseRightEdge(head);//单链逆序,记录原本的尾节点,现在作为链表起点
        TreeNode* cur = tail;
        while(cur!=NULL)
        {
            res.push_back(cur->val);
            cur=cur->right;
        }
        head = reverseRightEdge(tail);//单链表逆序回来
        return res;
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode *predecessor = nullptr;

        while (root != nullptr) {
            if (root->left != nullptr) {//morris序可以访问两次的节点
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root->left;
                while (predecessor->right != nullptr && predecessor->right != root) {
                    predecessor = predecessor->right;
                }
                
                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor->right == nullptr) {//第一次访问
                  	//res.push_back(root->val);  // 先序遍历需要!!!
                    predecessor->right = root;
                    root = root->left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {//第二次访问
                    //res.push_back(root->val);//中序遍历需要!!!
                    //下面这段后序需要=====================
                    vector<int> tmpVec = rightEdge(root->left);
                    //拼接vector
                    for (int i = 0; i < tmpVec.size(); i++)
                    {
                        res.push_back(tmpVec[i]);
                    }
                    //======================================
                    predecessor->right = nullptr;
                    root = root->right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {//morris序只能访问一次的节点
                //res.push_back(root->val);  前序遍历和中序遍历需要
                root = root->right;
                // 下面这段后序需要=====================
                vector<int> tmpVec = rightEdge(root);
                // 拼接vector
                for (int i = 0; i < tmpVec.size(); i++)
                {
                    res.push_back(tmpVec[i]);
                }
                //======================================
            }
        }
        return res;
    }

分解问题的思路遍历二叉树

平衡二叉树

平衡二叉树(AVL)：任意节点左、右子树高度差(平衡因子 )不超过1

最先发明的自平衡二叉查找树

平衡与否的区别

上图图(b)中是二叉树最糟糕的情况,刚好退化成链表
$$
h(层数)=n
\
\
ASL(平均查找长度)=\frac{n+1}{2}
$$
上图图(a)中为平衡二叉树
$$
h(层数) = \lfloor log_2n \rfloor +1
\
\
ASL(平均查找长度) = \lfloor log_2n \rfloor +1
$$

可见,平衡二叉树的查找效率要远比非平衡二叉树要稳定.

如何自平衡

插入阶段

查找节点位置 -> 插入节点 -> 回溯检查调整实现自平衡

插入二叉树可以抽象出来四种情况,分别是 LL,RR,LR,RL

插入视频讲解|720x360

123123213

LL：插入一个新节点到根节点的左子树（Left）的左子树（Left），导致根节点的平衡因子由1变为2
RR：插入一个新节点到根节点的右子树（Right）的右子树（Right），导致根节点的平衡因子由-1变为-2
LR：插入一个新节点到根节点的左子树（Left）的右子树（Right），导致根节点的平衡因子由1变为2
RL：插入一个新节点到根节点的右子树（Right）的左子树（Left），导致根节点的平衡因子由-1变为-2

LL(右旋)
RR(左旋)
RL(先k3右旋,后k1左旋)
LR(先k1左旋,后k2右旋)

//计算平衡因子
int getBalanceFactor(PBTreeNode pTree)
{
    if(!pTree)return NULL;
    return getHeight(pTree->lchild)-getHeight(pTree->rchild);
}


//插入时对节点的平衡因子balanceFactor维持平衡的函数
PBTreeNode rebuild(PBTreeNode pTree)
{
    if(!pTree)return NULL;
    if(getBalanceFactor(pTree)>1)//LL/lR形
    {
        if(pTree->lchild->rchild!=NULL)//LR形
            pTree->lchild = leftRotate(pTree->lchild);
        return rightRotate(pTree);//返回新头部
    }
    else if(getBalanceFactor(pTree)<-1)//RR/RL形
    {
        if(pTree->rchild->lchild!=NULL)//RL形
            pTree->rchild = rightRotate(pTree->rchild);
        return leftRotate(pTree);//返回新头部
    }
    return pTree;
}

左旋

将根节点的右孩子作为新根节点。
将新根节点的左孩子作为原根节点的右孩子。
将原根节点作为新根节点的左孩子。

//左旋操作    针对RR
PBTreeNode leftRotate(PBTreeNode pTree)
{
    if(!pTree)return NULL;
    PBTreeNode newRoot = pTree->rchild;
    pTree->rchild = newRoot->lchild;
    newRoot->lchild = pTree;
    return newRoot;//返回新头部
}

右旋

将根节点的左孩子作为新根节点。
将新根节点的右孩子作为原根节点的左孩子。
将原根节点作为新根节点的右孩子。

//右旋操作   针对LL
PBTreeNode rightRotate(PBTreeNode pTree)
{
    if(!pTree)return NULL;
    PBTreeNode newRoot = pTree->lchild;
    pTree->lchild = newRoot->rchild;
    newRoot->rchild = pTree;
    return newRoot;//返回新头部
}

删除阶段

删除视频讲解|720x360

查找节点 -> 删除节点 -> 回溯检查调整实现自平衡

删除的节点有三种情况:节点为

叶子节点->直接删除
一个子树的节点->又分左右两种情况->删除节点,直接将子树放至删除节点位置
两个子树的节点->将后驱节点(中序遍历的后一个节点)带的数据保存至待删除节点,删除后驱节点

//纯粹的删除传入的node节点,返回新头部节点
PBTreeNode deleteNode(PBTreeNode node)
{
    if(!node)return NULL;
    if (node->lchild==NULL&&node->rchild==NULL)//叶子节点
    {
        free(node);
        return NULL;
    }
    else if(node->lchild!=NULL&&node->rchild!=NULL)//双子树的节点
    {
        PBTreeNode nextNode=node->rchild;//寻找后驱节点
        PBTreeNode nextNodeParentNode=node;//寻找后驱节点的父节点
        int direction =0;//表示nextNodeParentNode节点与nextNode子节点的左右方向
        while (nextNode->lchild!=NULL)
        {
            nextNodeParentNode = nextNode;
            nextNode = nextNode->lchild;
            direction=1;
        }
        node->data = nextNode->data;
        if(direction)
            nextNodeParentNode->lchild=deleteNode(nextNode);
        else
            nextNodeParentNode->rchild=deleteNode(nextNode);
        return node;
    }
    else{//单子树的节点
        PBTreeNode newHead = node->lchild==NULL?node->rchild:node->lchild;
        free(node);
        return newHead;
    }
}

完整代码

此处附一个将有序序列变为平衡二叉树的代码及讲解

typedef struct _BTreeNode
{
	void* data;
	struct _BTreeNode *lchild, *rchild;
}BTreeNode,*PBTreeNode;

typedef struct __BTree
{
	PBTreeNode root;
	int m_size;
}_BTree,*PBTree;

typedef void* BTree;//作为函数返回值,可以承载NULL的返回而无需声明格式转换
typedef void* TreeNode;

//自定义的myCompare函数,返回1表示myInsertData<TreeData
//返回0表示myInsertData==TreeData
//返回-1表示myInsertData>TreeData

//初始化二叉树
BTree init_BinaryTree()
{
    PBTree tree = (PBTree)malloc(sizeof(_BTree));
	if (!tree)
	{
		return NULL;
	}
	tree->m_size = 0;
	tree->root = NULL;
	return tree;
}

void insert_BinaryTree(BTree _tree,void* data,int(*myCompare)(void* myInsertData,void* TreeData))
{
	if (!_tree ||!data)
	{
		return;
	}
	PBTree tree = (PBTree)_tree;
	if (!tree->root)//空树
	{
		tree->root = (PBTreeNode)malloc(sizeof(BTreeNode));
		if (!tree->root)
		{
			return;
		}
		tree->root->data = data;
		tree->root->lchild = NULL;
		tree->root->rchild = NULL;
		tree->m_size++;
	}
	else
	{
		PBTreeNode Pcurrent = tree->root;
		while (Pcurrent!=NULL)
		{
			if (myCompare(data,Pcurrent->data)==1)//1表示插入左边
			{
				if (Pcurrent->lchild == NULL)//执行插入操作
				{
					Pcurrent->lchild = (PBTreeNode)malloc(sizeof(BTreeNode));//未做成功校验
					Pcurrent->lchild->data = data;
					Pcurrent->lchild->lchild = NULL;
					Pcurrent->lchild->rchild = NULL;
					tree->m_size++;
					return;
				}
				Pcurrent = Pcurrent->lchild;
			}
			else//相等或大于根节点默认插右边
			{
				if (Pcurrent->rchild == NULL)//执行插入操作
				{
					Pcurrent->rchild = (PBTreeNode)malloc(sizeof(BTreeNode));//未做成功校验
					Pcurrent->rchild->data = data;
					Pcurrent->rchild->lchild = NULL;
					Pcurrent->rchild->rchild = NULL;
					tree->m_size++;
					return;
				}
				Pcurrent = Pcurrent->rchild;
			}
		}
	}
}

//获取节点的高度
int getHeight(PBTreeNode pTree)
{
    if(!pTree)return 0;
    return max(getHeight(pTree->lchild),getHeight(pTree->rchild))+1;
}

//右旋操作   针对LL
static PBTreeNode rightRotate(PBTreeNode pTree)
{
    if(!pTree)return NULL;
    PBTreeNode newRoot = pTree->lchild;
    pTree->lchild = newRoot->rchild;
    newRoot->rchild = pTree;
    return newRoot;//返回新头部
}

//左旋操作    针对RR
static PBTreeNode leftRotate(PBTreeNode pTree)
{
    if(!pTree)return NULL;
    PBTreeNode newRoot = pTree->rchild;
    pTree->rchild = newRoot->lchild;
    newRoot->lchild = pTree;
    return newRoot;//返回新头部
}

//计算平衡因子
int getBalanceFactor(PBTreeNode pTree)
{
    if(!pTree)return NULL;
    return getHeight(pTree->lchild)-getHeight(pTree->rchild);
}

//插入时对节点的平衡因子balanceFactor维持平衡的函数
PBTreeNode rebuild(PBTreeNode pTree)
{
    if(!pTree)return NULL;
    if(getBalanceFactor(pTree)>1)//LL/lR形
    {
        std::cout<<"L触发旋转"<<std::endl;
        if(pTree->lchild->rchild!=NULL)//LR形
            pTree->lchild = leftRotate(pTree->lchild);
        return rightRotate(pTree);//返回新头部
    }
    else if(getBalanceFactor(pTree)<-1)//RR/RL形
    {
        std::cout<<"R触发旋转"<<std::endl;
        if(pTree->rchild->lchild!=NULL)//RL形
            pTree->rchild = rightRotate(pTree->rchild);
        return leftRotate(pTree);//返回新头部
    }
    return pTree;
}

//删除时对节点的平衡因子维持平衡的函数
PBTreeNode rebuildForDelete(PBTreeNode pTree)
{
    if(!pTree)return NULL;
    if(getBalanceFactor(pTree)>1)//LL/lR形
    {
        if(getBalanceFactor(pTree->lchild)==-1)//LR形
            pTree->lchild = leftRotate(pTree->lchild);
        return rightRotate(pTree);//返回新头部
    }
    else if(getBalanceFactor(pTree)<-1)//RR/RL形
    {
        if(getBalanceFactor(pTree->rchild)==1)//RL形
            pTree->rchild = rightRotate(pTree->rchild);
        return leftRotate(pTree);//返回新头部
    }
    return pTree;
}

//递归插入,含自平衡
static void insert_BinaryTree_digui(PBTreeNode* rootAdd,void* data,int(*myCompare)(void* myInsertData,void* TreeData))
{
    if (!data)
	{
		return;
	}
	if(!*(rootAdd))
    {
         *rootAdd = (PBTreeNode)malloc(sizeof(struct _BTreeNode));
         (*rootAdd)->data = data;
         (*rootAdd)->lchild = NULL;
         (*rootAdd)->rchild = NULL;
         return;
    }
    if(myCompare(data,(*rootAdd)->data)==1)//1表示插入左边
    {
        insert_BinaryTree_digui(&(*rootAdd)->lchild,data,myCompare);
    }
    else{//相等或大于根节点默认插右边
        insert_BinaryTree_digui(&(*rootAdd)->rchild,data,myCompare);
    }
    *rootAdd =  rebuild(*rootAdd);//自平衡的关键!!!!!!!!!!!!!!!!!!
}

//纯粹的删除传入的node节点,返回新头部节点
static PBTreeNode deleteNode(PBTreeNode node)
{
    if(!node)return NULL;
    if (node->lchild==NULL&&node->rchild==NULL)//叶子节点
    {
        free(node);
        return NULL;
    }
    else if(node->lchild!=NULL&&node->rchild!=NULL)//双子树的节点
    {
        PBTreeNode nextNode=node->rchild;//寻找后驱节点
        PBTreeNode nextNodeParentNode=node;//寻找后驱节点的父节点
        int direction =0;//表示nextNodeParentNode节点与nextNode子节点的左右方向
        while (nextNode->lchild!=NULL)
        {
            nextNodeParentNode = nextNode;
            nextNode = nextNode->lchild;
            direction=1;
        }
        node->data = nextNode->data;
        if(direction)
            nextNodeParentNode->lchild=deleteNode(nextNode);
        else
            nextNodeParentNode->rchild=deleteNode(nextNode);
        return node;
    }
    else{//单子树的节点
        PBTreeNode newHead = node->lchild==NULL?node->rchild:node->lchild;
        free(node);
        return newHead;
    }
}

//递归删除,含自平衡(0表示删除成功,-1表示未删除成功,非0表示要接到传入的root的父节点上)
//使用时directory固定传-1,_parentNode传父节点,如果root是根节点就传树指针
static PBTreeNode delete_BinaryTree_digui(PBTreeNode root,void* _parentNode,void* data,int(*myCompare)(void* myInsertData,void* TreeData),int directory=-1)
{
    if(!root||!data) 
    {
        return (PBTreeNode)-1;//没找到或传参错误
    }
    void* ret;
    PBTreeNode parentNode = (PBTreeNode)_parentNode;
    if(myCompare(data,root->data)==1)//小于
    {
        ret = delete_BinaryTree_digui(root->lchild,root,data,myCompare,1);
    }
    else if(myCompare(data,root->data)==-1)//大于
    {
        ret = delete_BinaryTree_digui(root->rchild,root,data,myCompare,0);
    }
    else//相等表示找到元素
    {
        if(directory == -1)
        {
            PBTree tree = (PBTree)parentNode;
            tree->root = deleteNode(root);
        }
        else if (directory)
        {
            parentNode->lchild = deleteNode(root);
        }
        else
        {
            parentNode->rchild = deleteNode(root);
        }
        ret = NULL;    
    }
    //自平衡回溯
     if(directory == -1)
    {
        PBTree tree = (PBTree)parentNode;
        tree->root = rebuildForDelete(tree->root);
    }
    else if(directory)
    {
         parentNode->lchild = rebuildForDelete(parentNode->lchild);
    }
    else{
        parentNode->rchild = rebuildForDelete(parentNode->rchild);
    }
    return (PBTreeNode)ret;
}

//内部采用递归方式
static void delete_BinaryTree2(PBTree tree,void* data,int(*myCompare)(void* myInsertData,void* TreeData))
{
    if(!tree||!data)return;
    PBTreeNode newHead = delete_BinaryTree_digui(tree->root,tree,data,myCompare);
    if(newHead != (PBTreeNode)-1)
        tree->m_size--;
}

struct nodeInfo
{
    PBTreeNode node;
    int directory;//node的下一个节点的左右:0表示左,1表示右
};

//删除节点,非递归,通过一个vector容器记录经过的节点进行自平衡
void delete_BinaryTree(BTree _tree,void* data,int(*myCompare)(void* myInsertData,void* TreeData))
{
    if (!_tree ||!data)return;
    vector<nodeInfo> nodes;//用于记录查找经过的节点用于调整
	PBTree tree = (PBTree)_tree;
    PBTreeNode target = tree->root;
    PBTreeNode targetParent = NULL;
    int direction = 0;//0表示左,1表示右
    while (target!= NULL)
    {
        int compResult = myCompare(data, target->data);
        if (compResult == 1)
        {
            nodeInfo tmpNodeInfo = {target,1};
            nodes.push_back(tmpNodeInfo);
            targetParent = target;
            target = target->lchild;
            direction = 0;
        }
        else if (compResult == -1)
        {
            nodeInfo tmpNodeInfo = {target,0};
            nodes.push_back(tmpNodeInfo);
            targetParent = target;
            target = target->rchild;
            direction = 1;
        }
        else if (compResult == 0)
        {
            //找到了
            if (target == tree->root)
            {
                tree->root = deleteNode(target);
                nodeInfo tmpNodeInfo = {tree->root,0};
                nodes.push_back(tmpNodeInfo);//此处0与1都可以
            }
            else
            {
                if (direction)
                {
                    targetParent->rchild = deleteNode(target);
                    nodeInfo tmpNodeInfo = {targetParent->rchild,0};
                    nodes.push_back(tmpNodeInfo);//此处0与1都可以
                }
                else
                {
                    targetParent->lchild = deleteNode(target);
                    nodeInfo tmpNodeInfo = {targetParent->lchild,0};
                    nodes.push_back(tmpNodeInfo);//此处0与1都可以
                }
            }
            tree->m_size--;
            //std::cout<<nodes.size()<<std::endl;
            
            //自平衡调整:
            for (size_t i = nodes.size()-1; i >0; i--)
            {   
                if(nodes[i].node==NULL)
                    continue;
                if (nodes[i-1].directory)
                    nodes[i-1].node->lchild = rebuildForDelete(nodes[i].node);
                else    
                    nodes[i-1].node->rchild = rebuildForDelete(nodes[i].node);    
            }
            tree->root = rebuildForDelete(nodes[0].node);
            break;
        }
    }
}

//内部采用递归实现
void insert_BinaryTree2(BTree tree,void* data,int(*myCompare)(void* myInsertData,void* TreeData))
{
    if (!tree ||!data)
	{
		return;
	}
	PBTree pTree = (PBTree)tree;
    insert_BinaryTree_digui(&pTree->root,data,myCompare);
    pTree->m_size++;
}

//层序遍历 
void show_BinaryTree(PBTreeNode root, void(*myShow)(void*))
{
    if(!root)
        return;
    vector<vector<PBTreeNode> > levelVec;//用于临时存放每层的节点
    PBTreeNode curNode = root;
    vector<PBTreeNode> tmpVec;
    tmpVec.push_back(root);
    levelVec.push_back(tmpVec);
    for(int i=0;i<levelVec.size();i++)
    {
        tmpVec.clear();
        while(levelVec[i].size()>0)
        {
            curNode = levelVec[i].front();
            levelVec[i].erase(levelVec[i].begin());
            myShow(curNode->data);
            if(curNode->lchild)tmpVec.push_back(curNode->lchild);
            if(curNode->rchild)tmpVec.push_back(curNode->rchild);
        }
        if(tmpVec.size()>0)
            levelVec.push_back(tmpVec);
        std::cout<<std::endl;
    }
    
}

void middleRecursionShow_BinaryTree(TreeNode root, void(*myShow)(void*))
{
	if (!root || !myShow)
	{
		return;
	}
	PBTreeNode tree = (PBTreeNode)root;
	middleRecursionShow_BinaryTree(tree->lchild, myShow);
	myShow(tree->data);
	middleRecursionShow_BinaryTree(tree->rchild, myShow);
}

//查找元素,返回节点,没有的话返回NULL
PBTreeNode findNode(PBTreeNode root,void* data,int(*myCompare)(void* myInsertData,void* TreeData))
{
    if (!root || !data)
	{
		return NULL;//没找到或传参有问题
	}
    if(myCompare(data,root->data)==1)//小于
        return findNode(root->lchild,data,myCompare);
    else if(myCompare(data,root->data)==-1)//大于
        return findNode(root->rchild,data,myCompare);
    else//等于
        return root;
}

使用上面代码案例:

void myShow(void* data)
{
    std::cout<<*(int*)data<<" ";
}

//自定义的myCompare函数,返回1表示myInsertData<TreeData
//返回0表示myInsertData==TreeData
//返回-1表示myInsertData>TreeData
int myCompare(void* myInsertData,void* TreeData)
{
    if(*(int*)myInsertData<*(int*)TreeData)
        return 1;
    else if(*(int*)myInsertData==*(int*)TreeData)
        return 0;
    else
        return -1;
}

int main(int argc,char** argv)
{
    PBTree tree = (PBTree)init_BinaryTree();
    int a=50,b=60,c=40,d=30,e=45,f=75,g=55,h=42,i=46;
    insert_BinaryTree2(tree,&a,myCompare);  
    insert_BinaryTree2(tree,&b,myCompare); 
    insert_BinaryTree2(tree,&c,myCompare); 
    insert_BinaryTree2(tree,&d,myCompare); 
    insert_BinaryTree2(tree,&e,myCompare); 
    insert_BinaryTree2(tree,&f,myCompare); 
    insert_BinaryTree2(tree,&g,myCompare); 
    insert_BinaryTree2(tree,&h,myCompare); 
    insert_BinaryTree2(tree,&i,myCompare); 
    show_BinaryTree(tree->root,myShow);
    std::cout<<"|||||||||||||||||||||||中序遍历如下|||||||||||||||||||||||||||"<<std::endl;
    middleRecursionShow_BinaryTree(tree->root,myShow);
    std::cout<<std::endl;
    std::cout<<"==============删除30后:==============="<<std::endl;
    delete_BinaryTree2(tree,&d,myCompare);
    show_BinaryTree(tree->root,myShow);
     std::cout<<"==============删除45后:==============="<<std::endl;
    delete_BinaryTree2(tree,&e,myCompare);
    show_BinaryTree(tree->root,myShow);
    return 0;
}

平衡二叉树的重复key如何处理

平衡二叉树上最好没有重复key,所以如果同一个key需要收集多次,需要增加词频信息.

红黑树RBT

红黑树是一种折中的选择，它舍弃平衡二叉树的绝对平衡，换取节点插入时尽可能少的调整。

2-3-4树

红黑树起源于2-3-4树,它的本质就是2-3-4树

2-3-4树是4阶的B树,属于一种多路查找树,结构有以下限制:

所有叶子节点都拥有相同的深度
节点只能是2-节点,3-节点,4-节点之一.(优先满足4-节点)
- 2-节点:包含一个元素的节点,有两个子节点
- 3-节点:包含两个元素的节点,有三个子节点
- 4-节点:包含三个元素的节点,有四个子节点
- 所有节点必须至少包含一个元素
元素始终保持排序顺序,整体上保持二叉查找树的性质,即父节点大于左子节点,小于右子节点;而且节点有多个元素时,每个元素必须大于它左边的和它的左子树中元素

2-3-4树的查询操作像普通的二叉搜索树一样,非常简单,但由于其节点元素数不确定,在一些编程语言中实现起来并不方便,实现一般使用它的等同 – 红黑树

2-3-4树的每一个节点都对应红黑树的一种结构,所以每一棵2-3-4树也都对应一棵红黑树

二者的对应关系

转换为红黑树如下图

左倾规则 preload

右倾规则

上面的转换可知,红黑树中红色的节点不是单独纯在的,而是一定和他上方的黑色节点一体存在的

一个2-3-4树可以转换成很多棵不同的红黑树,但上图两个红黑树转换的都是同一个2-3-4树

红黑树的特点

红黑树是一种节点带有颜色属性的二叉查找树,但它在二叉查找树之外,还有以下5大性质

节点是红色或黑色
根是黑色
所有叶子都是黑色(叶子是NULL节点)
每个红色节点必须有两个黑色的子节点(不存在父子红色节点)
任一节点到器每个叶子的所有简单路径包含相同数量的黑节点(黑色平衡)

可以推出:
$$
红黑树的高度<=2*log_2(n+1)
$$

红黑树节点新增的节点一定是红色的

多路平衡搜索树

红黑树的性能优于B-树和B+树，但是红黑树只能用于存储一维数据，而B-树和B+树可以用于存储多维数据。

B-树

B+树

堆

堆一般指的是二叉堆，顾名思义，二叉堆是完全二叉树或者近似完全二叉树

可以直接理解成用数组表示的完全二叉树

堆的性质

是一棵完全二叉树
每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆。

堆的存储:一般用数组存储

下标为i的结点的父结点下标为(i -1)/2,其左右子结点分别为 (2i + 1)、(2i + 2),如下图

节点数量为n个的堆有

OIP

堆与红黑树的比较

操作	红黑树	堆
查找	O(log n)	O(n)
插入	O(log n)	O(log n)
删除	O(log n)	O(log n)
查找最大/最小	O(log n)	O(1)

堆的基本操作

下面以大根堆为例

上滤最后一个叶子节点向上调整的操作

让节点和他的父元素比较,若大于父节点则交换,直到无法上移为止
下滤根节点向下调整的操作

节点跟他的最大子节点比较,若小于最大子节点则交换.持续直到该节点大于他的子节点或移动到尾部为止.

运用这两个操作能实现堆的所有功能

建堆方式:

自顶向下建堆法,逐个插入元素进行上滤 (适合逐步插入新元素)
自下而上建堆法,对每个父节点进行下滤 (从无到有:建堆更快)

堆排序就是这种,针对现有的数组调配堆序性

堆的应用

优先队列

取优先队列需要的最大值和最小值后,将最后的元素放入根节点位置,对其进行下滤
堆排序

从二叉树的非叶子节点开始,依次往前下滤

pop的实现为取走根节点,将末尾叶子节点放到根节点进行下滤操作

取出三次节点流程如下:

最大堆的代码实现

自己实现的最大堆代码

#include <iostream>
using namespace std;
#include <vector>

//实现一个大根堆
//堆的规则,i节点的左节点是2i+1,右节点是2i+2,父节点是(i-1)/2
template<class T>
class heap
{
private:
    /* data */
    vector<T> vec;
    //上滤
    void siftUp();
    // 下滤
    void siftDown(int i);

public:
    heap(/* args */);
    ~heap();
    //从混乱数组直接构建最大堆
    heap(vector<T>& vec);

    // 将元素插入优先队列。
    void push(T data);
    // 移除队列中的顶部元素。
    void pop();
    // 返回队列中的顶部元素。
    T top();
    // 检查队列是否为空。
    bool empty();
    // 返回队列中的元素数量。
    int size();
    //展示元素
    void show();
};
//上滤
template<class T>
void heap<T>::siftUp()
{
    int i=vec.size()-1;//最后的叶子节点
    while(i>0&&vec[(i-1)/2]<vec[i])//大于父节点就上移
    {
        swap(vec[i],vec[(i-1)/2]);
        i=(i-1)/2;
    }
}

//下滤
template<class T>
void heap<T>::siftDown(int i)
{
    int num=vec.size()-1;
    //尾部: num-i>0//表示还有子节点
    while(1)
    {
        if(num-i>2)//两个子节点
        {
            T largeIndex = 0;
            if(vec[2*i+1]>vec[2*i+2])
                largeIndex = 2*i+1;
            else
                largeIndex = 2*i+2;
            if(vec[i]<vec[largeIndex])
            {
                swap(vec[i],vec[largeIndex]);
                i=largeIndex;
            }
            else
                break;
        }
        else if(num-i>1)//一个子节点
        {
            if(vec[i]<vec[2*i+1])
            {
                swap(vec[i],vec[2*i+1]);
                i=2*i+1;
            }
            else
                break;  
        }
        else//到底了
            break;
    }
}


template<typename T>
heap<T>::heap(/* args */)
{
}

template<typename T>
heap<T>::~heap()
{
}

template<typename T>
heap<T>::heap(vector<T>& unsorted)
{
    //从混乱数组直接构建最大堆
    vec = unsorted;
    int num = vec.size();
    //逆序对每个父节点进行下滤操作
    for(int i=vec.size()-1;i>=0;i--)
    {
        siftDown(i);
    }
}

template<class T>
void heap<T>::push(T data)
{
    vec.push_back(data);
    //进行上滤
    siftUp();
}

template<class T>
void heap<T>::pop()
{
    //最后的节点填补到根节点,进行下滤操作
    T lastValue = vec.back();vec.pop_back();
    vec[0]=lastValue;
    siftDown(0);
}

template<class T>
T heap<T>::top()
{
    return vec[0];
}

template<class T>
bool heap<T>::empty()
{
    return vec.empty();
}

template<class T>
int heap<T>::size()
{
    return vec.size();
}

template<class T>
void heap<T>::show()
{
    for(T item:this->vec)
    {
        cout<<item<<" ";
    }
    cout<<endl;
}

哈希表

**哈希表(Hash Table)**是一种使用[[加解密相关#单向散列函数|哈希函数]]将键映射到存储位置的数据结构

查找,插入和删除操作的平均时间复杂度为O(1)，即常数时间

哈希表的实现方式一般有两种

链地址法(Separate Chaining)
开放寻址法(Open Addressing)

在C++标准库中，通常使用Separate Chaining来处理哈希冲突，即将具有相同哈希值的元素存储在同一个桶（链表、红黑树等）中。这种方式可以有效地处理哈希冲突，保持较好的性能。

链地址法结构体:

布隆过滤器

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于测试一个元素是否在一个集合中。它的优点是空间效率和查询时间都远超一般的算法，缺点是有一定的误识别率和删除困难。

详解跳转

布隆过滤由一个 bitmap(c++中可以用vector<bool>) 和一系列随机映射函数组成，它不存放数据的明细内容，仅仅标识一则
数据是否存在的信息

哈希散列后取模 –进化-> 多个哈希函数进行取模同时几个位置1

优点：

节省空间：一个 bit 位标识一则数据的存在信息，且利用了 k 个散列函数进行映射后，bitmap 的长度 m 可以进一步降低
查询高效：使用 k 个散列函数进行映射，由于 k 为常数，因此实际的时间复杂度为 O(1)

缺点：

存在假阳性误判问题：

误识别: 对于不存在的数据可能会被误判为存在，对于已存在的数据不可能发生误判. (由哈希碰撞问题导致)

即他返回不存在的结果,则一定不存在,他返回存在的结果,则可能不存在.

极端场景下，所有 bit 位都被置为 1，则针对所有不存在数据的误判概率为 100%.

布隆过滤器的误判率推演

针对于布隆过滤器数据删除困难的问题，下面提出两个方向的解决方案：

重新建立bitmap

这种方案适用于我们在数据库中仍然存有全量数据的明细记录，使用布隆过滤器仅仅作为缓存层起到保护关系型数据库的用途. 此时我们可以定期地对一部分数据库中的老数据进行归档，然后定期使用指定时间范围内的新数据构建出一个新的 bitmap，对老的 bitmap 进行覆盖，以此延长布隆过滤器的生命力.

重新建立bitmap颇为费时,拆解到每次操作中就有了:

渐进式迁移

监控到误判率>=阈值的时候,每次操作到来的时候发现存在老bitmap而不存在新bitmap,就查数据库确定是否存在,存在就更新新的bitmap.同时监控老bitmap的使用概率<某阈值,就认为老的bitmap销毁.新bitmap作为正式bitmap
布谷鸟过滤器

误判率推演

首先，我们设置好布隆过滤器的三个基本参数：

bitmap 的长度设置为 m；
hash 函数的个数设置为 k；
bitmap 中已输入的元素个数为 n；（注意是输入的元素而非被置为 1 的 bit 位）

下面我们开始概率推演：

在输入 1 个元素，并通过 hash 函数进行 1 次映射时，1 个 bit 位因为这次操作被置为 1 的概率为 $1/m$；
反之，这个 bit 位不会因为这次操作被置为 1 的概率为 $1-1/m$；
进一步得到，这个 bit 位在经过 k 次 hash 映射后，仍然不被置为 1 的概率为 $(1-1/m)^k$；
进一步得到，这个 bit 位在输入 n 个元素后，仍然不被置为 1 的概率为 $(1-1/m)^(k·n)$；
反之，在输入 n 个元素后，1 个 bit 位被置为 1 的概率为 $1-(1-1/m)^(k·n)$；

有了以上的结论后，我们知道我们每次输入一个元素时，发生误判的前提是，经过 hash 映射后，对应的 k 个 bit 位都在此前恰好被置为 1 了，因此我们可以得到误判发生的概率为:
$$
[1-(1-1/m)^(k·n)]^k
$$
下面我们基于高等数学中等价无穷小的规则，对这个误判概率表达式进行简化.

在高等数学中，我们知道当 x->0 时，有 $(1+x)^(1/x) \approx e$，其中 e 为自然常数，值约为 2.7182818.

于是我们有，当 m->∞ 时，1/m -> 0，于是有 $(1-1/m)^(-m) \approx e$.

于是有 $(1-1/m)^(k·n)=(1-1/m)^[(-m)·(-k·n/m)] \approx e^(-k·n/m)$

最终我们得到，当 m->∞ 时，误判概率可以简化表示为
$$
[1-e^(-k·n/m)]^k
$$

参数调优

我们知道一个布隆过滤器发生误判的概率是同时与 bimap 的长度 m、hash 函数的个数 k 以及 bitmap 中已输入元素的个数 n 有关的.

下面我们的问题是，我们如何通过合理的参数选取，来降低布隆过滤器发生误判的概率呢？

在面对这个问题时，我们采用的视角是，在已知 m 和 n 的前提下，如何通过 k 的取值，来使得误判概率趋于最低，因此 m 和 n 对于我们而言是常量，k 为求取的变量.

为进一步简化误判概率表达式，我们将常量表达式 $e^(n/m)$ 记为常数 t，于是误判概率表达式为:
$$
f(k)=[1-t^(-k)]^k
$$
我们对 f(k) 进行求导，通过求取 f(k) 的极小值（f’(k)=0，f’’(k)>0），最终得到当 $k·n/m=ln(2)$ 时，误判概率 f(k) 取到极小值.

因此我们在设计布隆过滤的参数时，应该遵循如下思路：

首先初步设定 bitmap 长度 m 为一个足够大的值
其次，我们预估这个布隆过滤器中可能存放的元素数量 n
接下来我们根据 $k·n/m=ln(2)$，计算出合适的 hash 函数个数
最后，我们通过误判概率表达式 $[1-e^(-k·n/m)]^k$，推算出可能发生误判的概率，看是否能够满足要求

针对于布隆过滤器的参数选取，这里有一个现成的参数调优模拟器，可供使用

下图的p表示计算得到的失误率

哈希算法选型

针对布隆过滤器的hash函数进行选型时,主要以计算性能为优先考虑项,而无需具备加密属性.

因此不考虑使用类似于[[加解密相关#常用的哈希函数|sha1,md5这类加密hash算法]]

开源的murmur3,这种非加密hash算法是很好的选择

现成的库

RedisBloom：这是Redis插件的布隆过滤器插件的实现。它支持多种哈希函数，并且提供了多种配置选项。
boost-bloom-filters github上的开源项目

布谷鸟过滤器

布谷鸟过滤器是另一类另辟蹊径的算法工具，能够在一定程度上支持 map 中的数据删除操作

好用的数据结构盘点

环形缓冲区

环形缓冲区是一种循环数据结构，具有以下优势：

内存利用率高：环形缓冲区可以重复利用已存储的数据空间，不会造成内存浪费。
实时数据处理：适用于需要连续接收数据并进行实时处理的场景，如音频、视频流处理等。
简单高效：环形缓冲区的读写操作简单高效，适用于需要高性能的数据处理应用。
缓解生产者消费者速度不匹配问题：环形缓冲区可以平衡生产者和消费者之间的速度差异，避免数据丢失或阻塞情况发生。

环形缓冲区通常使用两个指针来指示读写位置：一个是读指针（也称为”头指针”或”读索引”），用于指示当前读取的位置；另一个是写指针（也称为”尾指针”或”写索引”），用于指示当前写入的位置。通过这两个指针的不断更新，可以实现数据在环形缓冲区中的循环存储和读取。

确保读写速度相同是非常重要的，否则可能会导致数据覆盖的问题。当生产者（写入数据）的速度快于消费者（读取数据）的速度时，如果没有合适的同步机制，就有可能发生数据覆盖，新数据会覆盖尚未读取的数据，导致数据丢失或混乱。因此，在使用环形缓冲区时，需要确保生产者和消费者的速度相匹配，或者通过其他同步机制来保证数据的正确读写。

template <typename T>
class RingBuffer : public Buffer<T>
{
public:
    /**
     * @brief Construct a new Ring Buffer object 构造函数
     *
     */
    RingBuffer()
        : m_head(0)
        , m_tail(0)
        , m_maxBufferSize(4096) ///< must power of two
        , m_maxMirrorBufferIndex(2 * m_maxBufferSize - 1)
        , m_buffer(new T[m_maxBufferSize])
    {
    }

    /**
     * @brief Construct a new Ring Buffer object 通过缓冲区大小构造
     *
     * @param maxBufferSize [in] buffer size 缓冲区大小
     */
    RingBuffer(unsigned int maxBufferSize)
        : m_head(0)
        , m_tail(0)
        , m_maxBufferSize((maxBufferSize && (0 == (maxBufferSize & (maxBufferSize - 1)))) ? maxBufferSize : nextPowerOf2(maxBufferSize)) ///< must power of two
        , m_maxMirrorBufferIndex(2 * m_maxBufferSize - 1)
        , m_buffer(new T[m_maxBufferSize])
    {
    }

    /**
     * @brief Destroy the Ring Buffer object 析构函数
     *
     */
    virtual ~RingBuffer()
    {
        if (m_buffer)
        {
            delete[] m_buffer;
            m_buffer = NULL;
        }
    }

    /**
     * @brief write data to buffer 向缓冲区写数据
     *
     * @param data [in] write data 待写入数据
     * @param size [in] write data size 待写入大小
     * @return return write data size 返回写入数据大小
     */
    virtual int write(const T *data, unsigned int size)
    {
        for (unsigned int i = 0; i < size; i++)
        {
            m_buffer[m_tail & (m_maxBufferSize - 1)] = data[i];
            if (isFull())
            {
                m_head = (m_head + 1) & m_maxMirrorBufferIndex; ///< head and tail pointers incrementation is done modulo 2*size
            }
            m_tail = (m_tail + 1) & m_maxMirrorBufferIndex;
        }

        return size;
    }

    /**
     * @brief read data from buffer 从缓冲区读数据
     *
     * @param data [out] read data to save 待读取数据存储
     * @param size [in] read data size 待读取数据大小
     * @return return read data size 返回读取数据大小
     * @retval 0 buffer empty 缓冲区空
     * @retval [other] return read data size 返回读取数据大小
     */
    virtual int read(T *data, unsigned int size)
    {
        if (isEmpty())
        {
            return 0;
        }

        if (size > m_maxBufferSize)
        {
            size = m_maxBufferSize;
        }

        unsigned int usedLen = getUsedLen();
        if (size > usedLen)
        {
            size = usedLen;
        }

        for (unsigned int i = 0; i < size; i++)
        {
            *data = m_buffer[m_head & (m_maxBufferSize - 1)];
            data++;
            m_head = (m_head + 1) & m_maxMirrorBufferIndex;
        }

        return size;
    }

    /**
     * @brief is buffer full 缓冲区是否满
     *
     * @return true
     * @return false
     */
    bool isFull()
    {
        return m_tail == (m_head ^ m_maxBufferSize);
    }

    /**
     * @brief is buffer empty 缓冲区是否空
     *
     * @return true
     * @return false
     */
    virtual bool isEmpty()
    {
        return m_tail == m_head;
    }

    /**
     * @brief get used length of buffer 获取缓冲区已使用大小
     *
     * @return return used length of buffer 返回缓冲区已使用大小
     */
    virtual unsigned int getUsedLen()
    {
        return (m_tail >= m_head) ? (m_tail - m_head) : (m_tail + 2 * m_maxBufferSize - m_head);
    }

    /**
     * @brief get unused length of buffer 获取缓冲区未使用大小
     *
     * @return return unused length of buffer 返回缓冲区未使用大小
     */
    virtual unsigned int getUnusedLen()
    {
        return m_maxBufferSize - getUsedLen();
    }

    /**
     * @brief get total size of buffer 获取缓冲区总大小
     *
     * @return return total size of buffer 返回缓冲区总大小
     */
    virtual unsigned int getBufferSize()
    {
        return m_maxBufferSize;
    }

private:
    unsigned int m_head;
    unsigned int m_tail;

    unsigned int m_maxBufferSize;        ///< must power of two 必须为2的幂
    unsigned int m_maxMirrorBufferIndex; ///< 2 * m_maxBuffSize - 1
    T *m_buffer;
};

静态数组方式实现

所有的数据结构,静态数组的方式都是一种专门针对于竞赛而使用的一种实现方式

竞赛中,静态数组方式是最省空间的,在竞赛中,动态的方式创建空间后又删除空间的情况,系统会计算所有动态创建销毁的的空间的累积量为使用量

但工程上生产上实现有序表结构,为了防止内存泄露的风险,会采用动态结构的方式,动态增加,动态释放

进阶

acm选手常带的有序表模板:替罪羊树,treap,splay

Treap，不仅可以实现经典的有序表，还能非常顺利的改出可持久化的平衡搜索二叉树，也就是大名鼎鼎的FHQ-Treap，这几乎是今天acm选手必带的模版。可以说，全凭同行衬托，尤其是红黑树的衬托。

splay，是实现Link-Cut Tree的前置知识，一般来说，只有想去实现Link-Cut Tree，才会去实现Splay。

上面这些结构，时间复杂度都一样。但是红黑树，调整的繁琐，边界条件的复杂，代码的长度，是其中最恶心的存在，并且毫无美感。那么红黑树的好处是什么呢？折中来看，性能稳定性、工程实践的历史、内存占用等因素，红黑树常常被认为是一个更好的折中方案。

前缀树

前缀树又叫字典树，英文名trie：

前缀树是一个由“路径”和“节点”组成多叉树结构。由根节点出发，按照存储字符串的每个字符，没有对应字符路径则创建对应路径。

由“路径”记载字符串中的字符，由节点记载经过的字符数以及结尾字符结尾数，例如一个简单的记录了”abc”、”abd”、”bcf”、”abcd” 这四个字符串的前缀树如下图所示：

前缀树的使用场景：需要根据前缀信息来查询的场景
前缀树的优点：根据前缀信息选择树上的分支，可以节省大量的时间
前缀树的缺点：比较浪费空间，和总字符数量及字符种类有关
前缀树的定制：pass(路过信息)、end( 结尾信息)等信息

哈希表只能查一个完整的字符串出现的次数,而前缀树可以轻易实现类似”查询某些字符串开头的个数”的功能

代码实现

实现前缀树Trie类

Trie() 初始化前缀树对象
void insert(String word)将字符串word插入前缀树种
int search(String word)返回前缀树种字符串word的实例个数
int prefixNumber(String prefix)返回前缀树中以prefix为前缀的字符串个数
void delete(String word)从前缀树种移除字符串word

public class Trie
{
    public class TrieNode
    {
        public int pass = 0;
        public int end = 0;
        public Dictionary<char, TrieNode> nexts = new Dictionary<char, TrieNode>();
    }
    public TrieNode root;
    public Trie()
    {
        root = new TrieNode();
    }

    public void insert(string word)
    {
        if (word.Length == 0)
            return;
        TrieNode current = root;
        current.pass++;
        for (int i = 0; i < word.Length; i++)
        {
            //不存在则新建,存在则pass++
            if (!current.nexts.ContainsKey(word[i]))
            {
                current.nexts.Add(word[i], new TrieNode());
            }
            current = current.nexts[word[i]];
            current.pass++;
            if (i == word.Length - 1)
            {
                current.end++;
            }
        }
    }

    /// <summary>
    /// 统计有多少个单词是word这个单词一样的
    /// </summary>
    /// <param name="word"></param>
    /// <returns></returns>
    public int countWordsEqualTo(string word)
    {
        if (word.Length == 0)
            return 0;
        TrieNode current = root;
        for (int i = 0; i < word.Length; i++)
        {
            if (!current.nexts.ContainsKey(word[i]))
                return 0;
            current = current.nexts[word[i]];
        }
        return current.end;
    }

    /// <summary>
    /// 统计有多少个单词是以word这个字符串作为前缀的
    /// 与countWordsEqualTo的代码区别只是最后返回的是current.pass
    /// </summary>
    /// <param name="word"></param>
    /// <returns></returns>
    public int countWordsStartingWith(string word)
    {
        TrieNode current = root;
        for (int i = 0; i < word.Length; i++)
        {
            if (!current.nexts.ContainsKey(word[i]))
                return 0;
            current = current.nexts[word[i]];
        }
        return current.pass;
    }

    /// <summary>
    /// 删除word这个单词
    /// </summary>
    /// <param name="word"></param>
    public void erase(string word)
    {
        if (countWordsEqualTo(word) == 0)
            return;
        TrieNode current = root;
        current.pass--;
        for (int i = 0; i < word.Length; i++)
        {
            if (--current.nexts[word[i]].pass == 0)
            {
                current.nexts.Remove(word[i]);
                return;
            }
            current = current.nexts[word[i]];
        }
        current.end--;
    }
}

静态数组方式实现

实现方式大致描述如下:

可以用两个数组来表示整个前缀树的情况,节点也使用数组来表示,两个数组之间的连接通过序号来表示

上图中的3是假设字符串中只出现3种字符,比如英文小写字母的话,3就改成26

AC自动机

参考链接

AC自动机通过Trie树+失败指针的协同设计，将多模式匹配的时间复杂度优化到线性级别，是解决大规模关键词实时匹配问题的核心算法。其思想在搜索引擎、网络安全、生物信息学等领域有广泛应用

后缀树

820. 单词的压缩编码

后缀树（Suffix Tree） 是一种用于高效存储和查询字符串所有后缀的树形数据结构，能够在 线性时间 内构建，并支持快速查找任意子串。其核心思想是通过 压缩存储 和 共享路径 来优化空间和时间复杂度

它是一种压缩树，能够在 O(n) 的时间内构建，且可以在 O(m) 的时间内查找长度为 m 的模式

核心思想：将文本的所有后缀组织成树形结构，支持任意子串的快速匹配。

实现步骤：

预处理文本：构建后缀树（时间 O(n)，空间 O(n)）。
查询子串：沿后缀树路径匹配目标子串字符，若存在完整路径，则记录所有出现位置。

优势：

单次查询时间复杂度 **O(m)**（m 为目标子串长度）。
支持统计子串出现次数、最长重复子串等高级操作。

缺点：

内存消耗高：最坏情况下空间复杂度为 O(n²)，适用于文本长度较小（如 <1MB）的场景。
预处理成本：超长文本（如 GB 级）的构建时间可能无法接受。

后缀树适用于高频子串操作场景，尤其在生物信息学、压缩算法和文本处理中优势显著。若处理超大文本或内存敏感场景，可考虑优化变体（如Ukkonen算法构建线性时间后缀树）。

与前缀树的比较

相比前缀树,后缀树更适合用于搜索中间子串

需求特性	推荐数据结构	原因
目标字符串固定	后缀树/后缀自动机	预处理文本后，单次查询时间复杂度为O(m)（m为目标串长度），适合高频查询。
目标字符串动态变化	AC自动机（前缀树）	预处理目标字符串集合，动态更新成本低，适合频繁增减模式串的场景。
文本固定但超长	后缀树/后缀自动机	预处理时间可接受时，单文本多次查询性能最优。
内存敏感	AC自动机（前缀树）	后缀树内存占用可能达到O(n²)（n为文本长度），前缀树更节省空间。
多文本匹配	AC自动机（前缀树）	后缀树需为每个文本单独构建，AC自动机可复用模式串预处理结果。

是否文本固定且需高频查询？  
├── 是 → 选择后缀树/后缀自动机  
└── 否 → 是否模式串动态变化或需跨文本匹配？  
    ├── 是 → 选择AC自动机  
    └── 否 → 根据内存和预处理时间权衡选择

后缀数组

后缀数组的数字顺序，就是后缀子串的字典顺序，记录了子串的有序排列。
例：sa［0］=5，意思是：排名0的子串，是原字符串中从第5个位置开始的后缀子串，即“adn”’。这里的5被称为后缀下标

有序表专题

有序表可以理解为一个抽象类,实现这个抽象类的方法很多,可以用平衡树实现,或用其他结构实现

有序表中的key按序组织,并且支持和序有关的查询操作,增加或删除某个key时,也要维护序

不管实现有序表的结构是什么,都要做到增删改查,时间复杂度为O(logn)

AVL树,跳表,替罪羊树,笛卡尔树,Treap树,FHQ Treap树,Splay树

替罪羊树

Scapegoat tree

参考链接

为了防止二叉搜索树左右不平衡，我们引入平衡树，而其中思路最简单的是替罪羊树（Scapegoat tree）。

替罪羊树理解难度低、代码容易写、常数时间好，实现常用功能的有序表非常推荐，但扩展性相对较弱

平衡因子为a，以h为头的树，节点总数为n，一旦左树或者右树的节点数>a*n，就认为树不平衡

核心在于: 树不平衡时，中序收集树上所有节点，然后用二分的方式重构整棵树，使其变成标准的平衡树

查询代价由树高决定，重构代价由重构的节点总数决定

选择合适的平衡因子，一般为O.7，单次查询代价O(Log n）、单次调整的均摊代价为O(log n）

平衡因子一般 0.7,0.75,0.8，太大会使树变深，太小会引起过多的重构

删除操作是替罪羊树中最好玩的地方，替罪羊树的删除节点并不是真正的删除，而是惰性删除（即给节点增加一个已经删除的标记，删除后的节点与普通节点无异，只是不参与查找操作而已）。当删除的数量超过树的节点数的一半时，直接重构！（屌丝和暴力属性MAX），可以证明均摊下来的复杂度还是O(logn)

替罪羊树的优化,每次进行增加,删除操作后,只需找到最上方不平衡的位置,重构一次即可