数据结构复习 (二叉查找树,高度平衡树AVL)
1.二叉查找树:
为了更好的实现动态的查找(可以插入/删除),并且不超过logn的时间下达成目的
定义: 二叉查找树（亦称二叉搜索树、二叉排序树）是一棵二叉树，其各结点关键词互异，且中根序列按其关键词递增排列。
等价描述: 二叉查找树中任一结点P，其左子树中结点的关键词都小于P的关键词，右子树中结点的关键词都大于P的关键词，且结点P的左右子树也都是二叉查找树。
节点:
BTSTreenode,有左右子树,有键值
有的操作是:
查找,插入和删除,
其他的创建和排序都可以通过上述完成
1,查找:
通过和当前的节点比较大小,来确定之后是:F.返回答案S.去更小的左边,T.去更大的右边
BSTnode* Search(BSTnode* root, int K){
if (root == NULL || root->key == K) return root;
if (K < root->key) return Search(root->left, K);
else return Search(root->right, K);
}
2,插入
根据和左右比较的方法来选择左边还是右边插入,但是不会插入相同的节点
可以引用实现,也可以是返回值实现
引用:
void insert(node*& root,int k){
If(root==NULL||root->val==k){
root=new node(k);
Return;
}
If(k>root->k)insert(root->left,k);
Else insert(root->right,k);
}
返回:
node* insert(node* root,int k){
If(root==NULL)return new node(k);
If(root->val==k)return root;
If(root->val>k)root->right=insert(root->right,k);
Else root->left=insert(root->left,k);
Return root;
}
3,删除,就是通过查找,然后判断:
,没有子树,直接删除
,有一个子树,直接上提
,两个子树,让右边最小的节点s上提到当前位置,之后删除S
void remove(BSTnode* &root, int K) {
if(root==NULL) return;
if(K<root->key) remove(root->left, K); //在左子树删K
else if(K>root->key) remove(root->right, K); //在右子树删K
else if(root->left!=NULL && root->right!=NULL){ //非根节点删除
BSTnode *s=root->right;
while(s->left!=NULL) s=s->left;
root->key=s->key; //s为t右子树中根序列第一个结点
remove(root->right, s->key);
}
else{ //根节点删除
BSTnode* oldroot=root;
root=(root->left!=NULL)? root->left:root->right;
delete oldroot;
}
}
numofBST
F[i]=f[i-1]*(4*i-2)/(i+1)
二叉查找树总结
➢则由n个互异关键词随机生成的二叉查找树，平均高度为O(logn)
➢查找、插入、删除平均时间复杂度O(logn)，但最坏情况时间复杂度为O(n)
2,高度平衡树:(AVL)
为了防止出现二叉查找树发生左/右偏的情况出现的,让一个树的左右高度相差不大于1
平衡系数:左子树高度-右子树高度
高度为h的AVL至少有
所以n>=2^(h/2),同理,h<=2logn
一颗AVL平均比完全二叉树高44%
节点AVLnode 记录的信息是键值,高度,左右子树
初始的时候每个节点的高度是0,空节点的高度为-1
具体操作:
1,计算高度
Int update_H(node* t){
If(t==NULL)return -1;
Int l=update_H(t->left);
Int r=update_H(t->right);
- >height=max(l,r)+1;
Return t->height;
}
Int Height(node* a){
Return a==NULL?-1”a->height;
}
2,旋转操作:
当前子树为root
左边的子树的高度为l1,右边为r1
2.1左边更高
2.1.1 左边的左边发生了插入,让左边提升
我们需要把B提升,A下降然后b右子树变成a的左子树
插入前后我们发现,高度没变
Void LL(node* & A){
Node* B=a->left;
- >left=B->right;
- >right=A;
Update_H(A);
Update_H(B);
A=B;
}
2.1.2左边的右边发生了插入,让左边的右边提升
将C的更低的子树交给B,然后让C提升,然后让C再次提升,将高的子树交给A
void LR(node* &A) {
RR(A->left);
LL(A);
}
2.2.1右边的右边发生了插入
void RR(AVLnode* &A) {
AVLnode *B = A->right;
A->right = B->left;
B->left = A;
UpdateHeight(A);
UpdateHeight(B);
A = B;
}
2.2.2右边的左边发生了插入
先让A的右子树的左子树上提,然后再让右子树上移动
void RL(AVLnode* &A){
LL(A->right);
RR(A);
}
注意;我们在插入节点时我们需要从下面向上去调整
比如:依次插入关键字5, 4, 2, 8, 6, 9
插入2时:
--->
插入6时:
--->
再插入一个9:
使平衡:
void ReBalance(AVLnode* &t) {
if(t==NULL) return;
if(Height(t->left) - Height(t->right)==2){ //左边更深
if(Height(t->left->left) >= Height(t->left->right)) //左边的左边更深
LL(t);
else //右边更深
LR(t);
}else if(Height(t->right) - Height(t->left)==2){
if(Height(t->right->right) >= Height(t->right->left))
RR(t);
else
RL(t);
}
Update_H(t); //更新高度
}
插入:
void Insert(AVLnode* &root, int K) {
if(root==NULL) root=new AVLnode(K);
else if(K < root->key) //在左子树插入
Insert(root->left, K);
else if(K > root->key) //在右子树插入
Insert(root->right, K);
ReBalance(root);
}
删除
和二叉树的删除差不多,需要注意的是删除之后的平衡的保持
所以代码是一样的,只是最后需要加一个使平衡
void remove(AVLnode* &root, int K) {
if(root==NULL) return;
if(K<root->key) remove(root->left, K);
//在左子树删K
else if(K>root->key) remove(root->right, K); //在右子树删K
else if(root->left!=NULL && root->right!=NULL){
AVLnode *s=root->right;
while(s->left!=NULL) s=s->left;
root->key=s->key; //s为t右子树中根序列第一个结点
remove(root->right, s->key);
}else{
AVLnode* oldroot=root;
root=(root->left!=NULL)? root->left:root->right;
delete oldroot;
}
ReBalance(root);
}
高度平衡树总结
➢AVL树的高度为O(logn)，因此使插入、删除、查找的最坏时间复杂度均为O(logn)。
➢删除操作最坏情况下需要做O(logn)次旋转。
➢对任意连续多次删除操作，每次删除所需的均摊旋转次数为O(1)[1]。对于任意多次插入和删除的混合序列，存在精心构造出的特定操作序列，使每次删除所需的均摊旋转次数为O(logn)