数据结构复习 (二叉查找树,高度平衡树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);

1. >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;

1. >left=B->right;
2. >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)