网站如何做移动规则适配/seo每日工作

建立动态查找表的目的：使查找的效率较高，且删除、插入将方便。

二叉排序树

二叉排序树又称二叉搜索树、二叉查找树。定义为：

二叉排序树的性质：

中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

二叉排序树的存储结构

typedef int KeyType;
typedef struct{KeyType key;/*...其它数据域...*/ 
} ElemType;
typedef struct BSTNode{ElemType data;struct BSTNode *lChild;struct BSTNode *RChild;
} BSTNode, *BSTree;//二叉排序树结点类型（二叉链表）

二叉排序树的查找

BSTree SearchBST(BSTree T, KeyType x)//递归算法
{if (T == NULL || T->data.key == x) return T;//返回要找结点的地址else if (x < T->data.key) return SearchBST(T->lChild, x);//在左子树中继续查找else return SearchBST(T->RChild, x);//在右子树中继续查找
}

BSTNode* SearchBST2(BSTree T, KeyType x)//非递归算法
{BSTNode *p = T;while (p){if (p->data.key == x) return p;else if (p->data.key < x) p = p->RChild;else p = p->lChild;}return NULL;
}

那么如何提高形态不均衡的二叉排序树的查找效率？$⟹$ 做“平衡化”处理——平衡二叉树。

二叉排序树的插入结点

如果要插入$x$，将$x$与根结点进行比较，若$x$大于根结点，则视线移到右子树；若$x$小于根结点，则视线移到左子树。再将$x$与新的根结点进行比较…，依次类推。

void BSTInsert(BSTree &T, ElemType x)//向排序二叉树中插入元素x
{BSTNode *cur = T, *t = NULL; while (cur) //找应插入的位置（叶子结点）{if (cur->data.key == x.key) return;//若二叉树中已存在该关键字，不再插入t = cur;if (x.key < cur->data.key) cur = cur->lChild;//cur下移else cur = cur->RChild;} //最终t指向某个叶子结点，x就应该插入在t之后BSTNode *p = new BSTNode;//二叉树中不含该关键字，则创建一个结点，插入到二叉树中p->data = x;p->lChild = p->RChild = NULL;if (t == NULL) T = p;//原树为空树，现为含一个结点的树else if (x.key < t->data.key) t->lChild = p;//新结点插入为t所指结点的左孩子else t->RChild = p;
}

从一棵空树出发，经过一系列的插入操作之后，即可生成一棵二叉排序树。中序遍历该二叉树即可得到一个有序序列，因此生成排序二叉树的过程也可视作对序列的排序过程。且由于插入的均是叶子结点，无需移动其它结点，相当于在有序序列上插入结点而无需移动其它记录。

注意：关键字序列的顺序不同，建立的排序二叉树也可能不同。

二叉排序树的删除结点

删除方法：

• 若被删除的是叶子结点，直接删除
• 若被删除的结点只有左子树（或右子树），用其左子树（或右子树）替换它即可
• 若被删除的结点既有左子树，又有右子树
  • 以中序前驱结点替换该结点，再删除该前驱结点（前驱结点即左子树中最大的结点）
    
  • 也可以用中序后继结点替换该结点，然后再删除该后继结点（后继结点即右子树中最小的结点）
    （注意此处删除结点时，若删除的是前驱结点，则该前驱结点没有右子树；若删除的是后继结点，则该后继结点没有左子树。）
  • 这两种方法应尽量选择使删除结点后树形更加均匀的那一种。

BiNode* search(BiTree T, int x) //在二叉树中查找x，若二叉树中不存在x，则返回NULL；否则返回x的地址
{BiNode *p = T;while (p){if (p->data == x) return p;else if (p->data < x) p = p->lc;else p = p->rc;}return NULL;
}void DeleteNode(BiTree &T, int x) //从排序二叉树中删除x
{BiNode* p = search(T, x);if (p == NULL) return; //若不存在该元素，就谈不上删除了else {if (p->lc == NULL || p->rc == NULL) //所删结点不存在两子树，直接用其子树替换该结点即可{BiNode *tmp = p;if (p->lc) p = p->lc;else p = p->rc;delete tmp;}else //所删结点存在两子树，用其中序前驱结点覆盖该结点，再删除中序前驱结点{BiNode *pre = p, *tail = p->lc;while (tail->rc) //找中序前驱结点{pre = tail;tail = tail->rc;} //tail指向中序序列的前一个结点，pre为tail的双亲结点p->data = tail->data; //用前驱结点的值覆盖所要删除的点的值，接下来任务就转化为删除前驱结点tail了if (pre == p) p->lc = tail->lc;else pre->rc = tail->lc;delete tail; //删除前驱结点}}
}

二叉搜索树的性能：

平衡二叉树

二叉树搜索树虽然平均时间复杂度为$O(logn)$，但在最坏情况下会退化为线性。平衡二叉树就是对二叉搜索树的优化，使其时间复杂度稳定为$O(logn)$.

平衡二叉树（Balanced Binary Tree）又称为AVL树。其定义为：

为方便起见，给每个结点增加一个数字（平衡因子BF），记录该结点左子树与右子树的高度差。则根据平衡二叉树的定义：所有结点的BF = -1或0或1。

平衡二叉树的调整

如果在一棵平衡二叉树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡。

调整原则：

1. 降低树的高度
2. 保持二叉排序树的性质

可以通过让插入点最近的祖先结点恢复平衡使上一层祖先结点恢复平衡。因此，为使二叉排序树恢复平衡，需要从离插入点最近的结点开始调整。

具有$n$个结点的平衡树，其高度$h$满足：$lo{g}_2(n+1)\le h\le [lo{g}_{\frac{\sqrt{5}+1}{2}}\sqrt{5}(n+1)]-2$

• 高为$h$的二叉树最多含有$2^h-1$个结点
• 设高为$h$的二叉树最少含有的结点个数为$N(h)$，则$N(h)$满足递推关系：$$\{\begin{array}{c}N(1)=1\\ N(2)=2\\ N(h)=N(h-1)+N(h-2)+1，h\ge 3\end{array}$$推出：含有高度为$h$的二叉树最少含有的结点个数为$\frac{(\frac{\sqrt{5}+1}{2}{)}^{h+2}}{\sqrt{5}}-1$
  
  

因此平衡二叉树的查找的时间复杂度稳定为$O(logn)$.

• 对于LL型，只需要对离插入点最近的失衡点进行一次顺时针旋转处理即可。
  

void LL(AVLTree &T)//RightRotate。对以T为根结点的二叉排序树进行右旋，之后T指向新的根结点
{AVLNode *lc = T->Lchild;//即旋转之后的新根结点T->Lchild = lc->Rchild;lc->Rchild = T;T->bf = lc->bf = 0;T = lc;//T指向新的根结点
}

• 对于RR型，只需要对离插入点最近的失衡点进行一次逆时针旋转处理即可。

void RR(AVLTree &T)//LeftRotate。对以T为根结点的二叉排序树进行左旋，之后T指向新的根结点
{AVLNode *rc = T->Rchild;//即旋转之后的新根结点T->Rchild = rc->Lchild;rc->Lchild = T;T = rc;//T指向新的根结点
}

• 对于LR型，先进行一次逆时针旋转，再进行一次顺时针旋转
  

void LR(AVLTree &T)//处理后T指向新的根结点
{AVLNode *lc = T->Lchild, *rd;switch (lc->bf)//检查T的左子树的平衡系数，并作相应的平衡处理{case 1://新结点插入的T的左孩子的左子树上T->bf = lc->bf = 0;LL(T);break;case -1://新结点插入在T的左孩子的右子树上rd = lc->Rchild;switch (rd->bf)//修改T及其左孩子的平衡因子{case 1:T->bf = -1;lc->bf = 0;break;case 0:T->bf = lc->bf = 0;break;case -1:T->bf = 0;lc->bf = 1;break;}rd->bf = 0;RR(T->Lchild);LL(T);}
}

• 对于RL型，先进行一次顺时针旋转，再进行一次逆时针旋转

void RL(AVLTree &T)
{AVLNode *rc = T->Rchild, *rd;switch (rc->bf)//检查T的右子树的平衡因子，并做相应的平衡处理{case -1://新结点插入在T的右孩子的右子树上T->bf = rc->bf = 0;RR(T);break;case 1://新结点插入在T的右孩子的左子树上rd = rc->Lchild;switch (rd->bf)//修改T即其右孩子的平衡因子{case -1:T->bf = 1;rc->bf = 0;break;case 0:T->bf = rc->bf = 0;break;case 1:T->bf = 0;rc->bf = -1;}rd->bf = 0;LL(T->Rchild);RR(T);break;}
}

平衡二叉树中结点的插入：

int InsertAVL(AVLTree &T, ElemType e, int &flag)//向T位置中插入结点e，插入成功返回1，否则返回0
{if (T == NULL)//如果找到了插入的位置，则插入新的结点{T = new AVLNode;T->data = e;T->Lchild = T->Rchild = NULL;T->bf = 0;flag = 1;//设置flag为1}else//该位置处有元素{if (e.key == T->data.key)//若已存在该关键字，则不进行插入，即插入失败{flag = 0;return 0;}else if (e.key < T->data.key)//搜索左子树{if (InsertAVL(T->Lchild, e, flag) == 0) return 0;//查找左子树，若找到插入的位置即插入。若左子树中也插入失败，则整个插入过程失败if (flag)//已经插入到左子树中，可能会导致不平衡{switch (T->bf)//检查该树的平衡因子{case 1://在插入之前，左子树比右子树高，插入后为LR型LR(T);flag = 0;//平衡化后子树的高度与之前相同break;case 0://在插入之前，左右子树一样高，插入后左树比右树高1T->bf = 1;flag = 1;//子树“长高”break;case -1://插入之前，左子树比右子树矮，插入后，二者一样高T->bf = 0;flag = 0;break;}}}else//搜索右子树{if (InsertAVL(T->Rchild, e, flag) == 0) return 0;//查找右子树，若找到插入的位置即插入。若右子树中也插入失败，则整个插入过程失败if (flag)//已插入右子树{switch (T->bf)//检查树的平衡因子{case 1://在插入之前，左子树比右子树高，插入后，左右子树一样高T->bf = 0;flag = 0;break;case 0://在插入之前，左右子树等高，插入后，右子树比左子树高1T->bf = -1;flag = 1;break;case -1://插入之前，右子树比左子树高1，插入后，为RL型RL(T);flag = 0;break;}}}}return 1;
}

如果平衡排序二叉树的结点个数为$n$，则查找的时间复杂度为$O(lo{g}_{2}n)$