营销型 展示类网站,游戏优化,临安市住房和建设局网站,广西送变电建设公司网站1.二叉查找树:
为了更好的实现动态的查找(可以插入/删除),并且不超过logn的时间下达成目的
定义: 二叉查找树#xff08;亦称二叉搜索树、二叉排序树#xff09;是一棵二叉树#xff0c;其各结点关键词互异#xff0c;且中根序列按其关键词递增排列。
等价描述: 二叉查找…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(rootNULL||root-valk){
rootnew node(k);
Return;
} If(kroot-k)insert(root-left,k);
Else insert(root-right,k);
}
返回: node* insert(node* root,int k){
If(rootNULL)return new node(k);
If(root-valk)return root;
If(root-valk)root-rightinsert(root-right,k);
Else root-leftinsert(root-left,k);
Return root;
} 3,删除,就是通过查找,然后判断:
,没有子树,直接删除
,有一个子树,直接上提
,两个子树,让右边最小的节点s上提到当前位置,之后删除S void remove(BSTnode* root, int K) {
if(rootNULL) return;
if(Kroot-key) remove(root-left, K); //在左子树删K
else if(Kroot-key) remove(root-right, K); //在右子树删K
else if(root-left!NULL root-right!NULL){ //非根节点删除
BSTnode *sroot-right;
while(s-left!NULL) ss-left;
root-keys-key; //s为t右子树中根序列第一个结点
remove(root-right, s-key);
}
else{ //根节点删除
BSTnode* oldrootroot;
root(root-left!NULL)? root-left:root-right;
delete oldroot;
}
} numofBST
F[i]f[i-1]*(4*i-2)/(i1) 二叉查找树总结
➢则由n个互异关键词随机生成的二叉查找树平均高度为O(logn)
➢查找、插入、删除平均时间复杂度O(logn)但最坏情况时间复杂度为O(n) 2,高度平衡树:(AVL)
为了防止出现二叉查找树发生左/右偏的情况出现的,让一个树的左右高度相差不大于1
平衡系数:左子树高度-右子树高度
高度为h的AVL至少有 所以n2^(h/2),同理,h2logn
一颗AVL平均比完全二叉树高44%
节点AVLnode 记录的信息是键值,高度,左右子树
初始的时候每个节点的高度是0,空节点的高度为-1 具体操作:
1,计算高度
Int update_H(node* t){
If(tNULL)return -1;
Int lupdate_H(t-left);
Int rupdate_H(t-right);
heightmax(l,r)1;
Return t-height;
}
Int Height(node* a){
Return aNULL?-1”a-height;
}
2,旋转操作:
当前子树为root 左边的子树的高度为l1,右边为r1
2.1左边更高
2.1.1 左边的左边发生了插入,让左边提升 我们需要把B提升,A下降然后b右子树变成a的左子树
插入前后我们发现,高度没变
Void LL(node* A){
Node* Ba-left;
leftB-right;rightA;
Update_H(A);
Update_H(B);
AB;
}
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(tNULL) 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(rootNULL) rootnew 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(rootNULL) return;
if(Kroot-key) remove(root-left, K);
//在左子树删K
else if(Kroot-key) remove(root-right, K); //在右子树删K
else if(root-left!NULL root-right!NULL){
AVLnode *sroot-right;
while(s-left!NULL) ss-left;
root-keys-key; //s为t右子树中根序列第一个结点
remove(root-right, s-key);
}else{
AVLnode* oldrootroot;
root(root-left!NULL)? root-left:root-right;
delete oldroot;
}
ReBalance(root);
} 高度平衡树总结
➢AVL树的高度为O(logn)因此使插入、删除、查找的最坏时间复杂度均为O(logn)。
➢删除操作最坏情况下需要做O(logn)次旋转。
➢对任意连续多次删除操作每次删除所需的均摊旋转次数为O(1)[1]。对于任意多次插入和删除的混合序列存在精心构造出的特定操作序列使每次删除所需的均摊旋转次数为O(logn)
