常见的基本数据结构-树，二进制树，二进制搜索树，AVL树

struct TreeNode
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
struct TreeNode{
　　ElementType Element;
　　SearchTree Left;
　　SearchTree Right;
};
SearchTree
MakeEmpty(SearchTree T){
　　if(T != NULL){
　　　　MakeEmpty(T->Left);
　　　　MakeEmpty(T->Right);
 　　free(T);
　　}
　　return NULL:
}

查找

find操作通常需要返回具有关键节点的指针，如果该节点不存在，则返回NULL. 如果T为NULL，则返回NULL. 否则，如果存储在T中的关键字是X，则返回T. 否则，我们将根据当前节点与X的关系递归遍历左右子树.

以下代码是通过递归实现的. 我们发现函数中的两个递归是尾递归，显然可以通过goto实现. 但是尾部递归在这里也是合理的，这降低了速度更改代码的简便性，并且使用的堆栈空间也是O（logN）.

Position
Find(ElementType X, SearchTree T){
　　if(T == NULL)
　　　　return NULL;
　　if(X < T->Element){
　　　　Find(X, T->Left);
　　}else if(X > T->Element){
　　　　Find(X, T->Right);
　　}else{
　　　　return T;
　　}
}

FindMin和FindMax

这些例程分别返回树中的最小和最大位置. 返回这些元素的确切值似乎更合理，但这将与Find操作不兼容. FindMin操作仅需要从根节点向左继续，并且终点是最小值. FindMax操作与此相反.

以下分别使用递归和非递归实现:

递归实现FindMin:

Position
FindMin(SearchTree T){
　　if(T == NULL)
　　　　return NULL;
　　else if(T->Left == NULL)
　　　　return T;
　　else
　　　　return FindMin(T->Left);
}

FindMax的非递归操作

Position
FindMax(SearchTree T){
　　if(T != NULL)
　　　　while(T->Right != NULL)
　　　　　　T = T->Right;
　　return T；
}

在例程中，插入操作很简单. 为了将X插入树中，我们可以像“查找”一样沿着树进行搜索. 如果找到X，它将什么都不做（或进行一些更新）. 否则，在遍历路径上方的最后一点插入X.

可以通过在节点记录中保留一个追加来指示发生频率来处理重复元素的插入，但这会增加树的总体空间，但是比将重复信息放入树中更好（将使树的深度增加）. 当然，如果关键字只是较大结构的一部分构造二叉排序树，则此方法将不起作用. 此时，我们可以将所有具有相同键的结构保留在辅助数据结构中，例如表或其他搜索树.

以下是插入例程代码:

SearchTree
Insert(ElementType X, SearchTree T){
　　if(T == NULL){
　　　　T = malloc(sizeof(struct TreeNode));
　　　　T->Element = X;
　　　　T->Left = T->Right = NULL;
　　}else if(X < T->Element){
　　　　T->Left = Insert(X, T->Left);
　　}else if(X > T->Element){
　　　　T->Right = Insert(X, T->Right);
　　}
　　return T;
}

删除操作

与许多数据结构一样，最困难的操作是删除. 一旦发现要删除节点，就需要考虑几种可能的情况.

如果节点是叶，则可以立即将其删除. 如果该节点有子节点，则可以在父节点调整指针以绕过该节​​点后删除该节点（为清楚起见，下面给出了）

复杂的情况是处理有两个儿子的节点. 一般的删除策略是用其右子树的最小数据替换该节点的数据构造二叉排序树，然后递归删除该节点. 因为右子树的最小节点不能有左子，所以第二次删除更容易. 以下是删除:

上面显示的过程效率不高，因为它沿树执行两次搜索以查找并删除右侧子树中的最小节点. 您可以编写DeleteMin函数来更改效率.

如果删除的数量不大，通常的策略是延迟删除它们，但是当要删除一个元素时，它仍会保留在树中，只是留下一个被删除的标记. 这种做法非常流行，尤其是在有重复的关键字的情况下，因为记录的出现频率可以降低1. 如果树中的实际节点数与删除的节点数相同，则记录的深度预计树只会以一个小的常数上升. 因此，与延迟删除相关的时间损失非常小. 此外，如果要重新插入已删除的关键字，则可以避免分配空间的消耗.

平均情况分析

直觉上，除了MakeEmpty外，我们希望上一节中的所有操作都花费O（logN）时间，因为我们使用恒定时间来减少树中的层，因此对树的操作大致减少了大约一半. 因此，除MakeEmpty外，所有操作均为O（d），其中d是包含表示访问权限的关键字的节点深度.

SeachTree Delete(ElementType X, SearchTree T){
　　Position TmpCell;
　　if(T == NULL)
　　　　Error();
　　else if(X < T->Element)
　　　　T->Left = Delete(X, T->Left);
　　else if(X > T->Element)
　　　　T->Right = Delete(X, T->Right);
　　else if(T->Left && T->Right){
　　　　TmpCell = FindMin(T->Right);
　　　　T->Element = TmpCell->Element;
　　　　T->Right = Delete(T->Element, T->Right);
　　}else{
　　　　TmpCell = T;
　　　　if(T->Left == NULL)
　　　　　　T = T->Right;
　　　　else if(T->Right == NULL)
　　　　　　T = T->Left;
　　　　free(TmpCell);
　　}
　　return T;
}

以下内容旨在证明，假设所有树的机会均等，则树的所有节点的平均深度为O（logN）.

树中所有节点的深度之和称为内部路径长度. 现在，我们将计算二进制搜索树的平均内部路径长度，其中平均值是二进制搜索树中所有可能的插入序列的长度.

令D（N）为具有N个节点的树T的内部路径长度，D（1）= 0. N节点树由一个i节点左子树和一个（Ni-1）节点右子树，以及一个深度为0的根节点组成，其中0 <= i

D（N）= D（i）+ D（N-i-1）+ N-1

如果所有子树的大小相等，则对于二叉搜索树可能是正确的（因为子树的大小仅取决于插入到树中的第一个元素的相对等级），但对于没有建立. 那么，D（i）和D（N-i-1）的平均值为:

通过求解此递归关系，平均值为D（N）= O（NlogN）. 因此，任何节点的期望深度为O（logN）.

但是，声明此结果并不意味着上一节中讨论的所有操作的平均运行时间为O（logN），并且并不完全正确. 原因在于删除操作，我们不知道是否所有二进制搜索树都同样可能出现.

具体来说，上述删除算法有助于使左子树比右子树更深，因为我们始终使用右子树中的一个节点来替换已删除的节点. 已经证明，在我们反复插入和删除多次之后，树的预期深度将变为O（sqrt（N）），并且树将变得明显不平衡.

在删除操作中，我们可以随机选择右侧子树的最小元素或左侧子树的最大元素来替换已删除的元素，以消除这种不平衡. 这显然可以消除树的偏见并保持树的平衡.

在没有删除或延迟删除的情况下，可以证明所有二进制搜索树都是同等可能的，因此可以断言上述操作都是O（logN）时间复杂度.

另一种新方法是放弃平衡条件并允许树具有任何深度，但是使用规则调整每个操作，以使后续操作更有效.

AVL树

AVL树是具有平衡条件的二叉搜索树. 此平衡条件必须易于维护，并且树的深度可以保证为O（logN）. 最简单的想法是要求左右子树具有相同的高度.

另一个平衡条件是每个节点必须具有相同高度的左和右子树. 尽管这种平衡条件确保了树的深度很小，但是使用起来过于严格.

AVL树是二叉搜索树，其每个节点的左子树和右子树的高度最多相差1. （空树的高度定义为-1）. AVL树的高度最多为1.44log（N + 2）-1.328，但实际上高度仅比logN高一点.

在高度为h的AVL树中，最小节点数S（h）由S（h）= S（h-1）+ S（h-2）+1给出. 对于h = 0，S（h）= 1; h = 1，S（h）= 2. 函数S（h）与斐波那契密切相关，从而推导了上面AVL树的高度范围.

插入时，我们需要更新那些通向根节点路径的节点的所有余额信息. 插入操作的困难在于插入节点可能会破坏AVL树的特性. 发生这种情况时，有必要还原树以完成插入操作. 实际上，可以通过旋转树来完成.

在插入节点之后，只有从插入点到根节点的路径上的节点平衡可能会更改，因为只有这些节点的子树可能会更改. 当我们沿着路径到达根并更新节点平衡信息时，我们可以找到一个平衡度超出AVL条件的节点. 我们将指出如何在第一个这样的节点上重新平衡树，并证明这种重新平衡可以确保整本书符合AVL特性.

如果重新平衡的节点称为a. 由于任何节点最多具有两个子节点，因此当高度不平衡时，在点a处两个子树之间的高度差为2，因此很容易知道在以下四种情况下会发生不平衡:

1. 插入一次左子的左子树

2. 插入一次左儿子的右子树

3. 插入一次右儿子的左子树

4. 插入一次右儿子的右子树

案例1和案例4是关于点a的镜像对称，案例2和案例3是关于点a的镜像对称.

第一种情况是插入发生在外部，即左右或左右，这是通过在树上执行一次旋转来调整的. 第二种情况是内部情况，即左右或左右情况，稍微复杂些，可以通过两次旋转进行调整.

两次旋转

对于左右插入或左右插入的情况，无法通过单次旋转来解决，而需要通过两次旋转来解决.

现在让我们总结以上讨论. 除几种情况外，要将关键字X插入AVL树中，我们将X递归地插入与T对应的树中. 如果TLR的高度不变，则插入完成. 否则，如果T中存在不平衡，那么我们将根据X和T和TLR中的关键字进行适当的单旋转或双旋转，更新这些高度，并解决与树的其余部分的连接以完成插入.

另一个针对高存储量的效率问题. 真正需要存储的是子树的高度，该高度应保持较小，我们可以使用两个二进制位进行存储.

struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
struct AvlNode{
　　ElementType Element;
　　AvlTree Left;
　　AvlTree Right;
　　int Height;
};

删除AVL树比插入更为复杂. 如果删除操作相对较少，那么延迟删除可能是最好的策略.

计算节点的高度

static int
Height(Position P){
　　if(P == NULL){
　　　　return -1;
　　}else{
　　　　return P->Height;
　　}
}

将节点插入AVL树的功能

AvlTree Insert(ElementType X, AvlTree T){
　　if(T == NULL){
　　　　T = malloc(sizeof(struct AvlNode));
　　　　if(T == NULL)
　　　　　　return ERROR();
　　　　T->Element = X; T->Height = 0;
　　　　T->Left = T->Right = NULL;
　　}else if(X < T->Element){
　　　　T->Left = Insert(X, T->Left);
　　　　if(Height(T->Left) - Height(T->Right) == 2)
　　　　　　if(X < T->Left->Element)
　　　　　　　　T = SingleRotateWithLeft(T);
　　　　　　else
　　　　　　　　T = DoubleRotateWithLeft(T); 
　　}else if(X > T->Element){
　　　　T->Right = Insert(X, T->Right);
　　　　if(Height(T->Right) - Height(T->Left) == 2)
　　　　　　if(X > T->Right->Element)
　　　　　　　　T = SingleRotateWithRight(T);
　　　　　　else
　　　　　　　　T = DoubleRotateWithRight(T);
　　}
　　T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
　　return T;
}

static Position SingleRotateWithLeft(Position K2){
　　Position 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;
}

static Position DoubleRitateWithLeft(Position K3){
　　K3->Left = SingleRotateWithRight(K3->Left);
　　return SingleRotateWithLeft(K3);
}

遍历树

对于遍历二叉树，由于每个节点的工作时间总计为N，因此总运行时间为O（N）.

树遍历可以分为前遍遍，中遍遍，后遍遍和分层遍历. 为了遍历树的层次结构，我们使用队列来辅助，而不是递归的默认堆栈.

B树

B树是常用的搜索树. M阶B树具有以下结构特征:

所有数据都存储在叶子上. 每个内部节点都包含分别表示该节点的子代的指针P1，P2，...，Pm和Pm. ......，是在Pm K1，K2，...，km-1中找到的最小关键字值. 当然，可能有一个指针为NULL，并且其对应的Ki是未定义的. 对于每个节点，子树P1中的关键字小于子树P2中的关键字，依此类推.

叶子包含所有实际数据，这些数据既可以是关键字本身，也可以是指向包含关键字的记录的指针.

对于M阶B树的属性:

树的根是叶子，或者儿子的数目在2到M之间.

除根以外，非树叶节点的子节点数量在M / 2（向上取整）到M

所有叶子都在同一深度

所有数据都存储在叶子上

每个内部节点都包含一个指向每个子节点的指针和一个表示非第一个节点的最小键值的值

对于每个节点，子树P1中的所有键值均小于子树P2中的关键字

对于B的插入操作，首先遵循Find（）操作. 到达叶子时，找到用于插入X的正确位置. 当叶子的单位不足以存储时，我们需要执行一系列操作调整.

对于一般的M阶B树，插入关键字时，唯一的困难发生在接收关键字的节点已经具有M个关键字的情况下. 此关键字使节点具有M + 1个关键字. 我们可以将其分为两个节点，分别具有（M + 1）/ 2和（M + 1）/ 2个关键字. 由于这会使父节点再有一个子节点，因此有必要检查父节点是否可以接收该节点. 如果父节点已经有M个儿子，则父节点将被拆分为两个节点. 我们重复此过程，直到找到具有至少M个儿子的父节点. 如果我们拆分根节点，则必须创建一个新的带有两个儿子的根盒.

B树的深度最多为[log（M / 2）N]. 在路径的每个节点上，我们执行O（logM）时间工作量以确定要选择的分子.

以下是AVL的示例:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-262418-1.html