📄 btree.cpp
字号:
// btree.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "btree.h"
#include <malloc.h>
template<class T>CBTree<T>::CBTree()
{
;
}
template<class T>CBTree<T>::~CBTree()
{
;
}
//左单旋转 (RotateLeft)
// A C
// / \ / \
// B C => A E
// | / \ / \ |
// D E B D +
// | | | |
// +
template<class T> void CBTree<T>::RotateLeft(node<T> **root)
{
node<T> *A = *root;
node<T> *C = A->rnext;
node<T> *D = C->lnext;
A->rnext = D;
C->lnext = A;
*root = C;
}
//右单旋转 (RotateRight)
// A B
// / \ / \
// B C => D A
// / \ | | / \
// D E + E C
// | | | |
// +
template<class T> void CBTree<T>::RotateRight(node<T> **root)
{
node<T> *A = *root;
node<T> *B = A->lnext;
node<T> *E = B->rnext;
B->rnext = A;
A->lnext = E;
*root = B;
}
template<class T> void CBTree<T>::LeftBalance(node<T> **root)
{
node<T> *A = *root;
node<T> *B = A->lnext;
node<T> *E = B->rnext;
switch (B->bf)
{
//左高(LL型)
// A(1) B(0)
// / \ / \
// B(1) C => D A(0)
// / \ | | / \
// D E + E C
// | | | |
// +
case LH:
A->bf = B->bf = EH;
RotateRight(root);
break;
//右高(LR型)
// A(2) A E(0)
// / \ / \ / \
// B(-1) C ==> E C ==> B(0) A(-1)
// / \ | L / \ | R / \ / \
// D E(1) B G D F G C
// | / \ / \ | | | | |
// F G D F +
// | | | |
// + +
case RH:
switch (E->bf)
{
case LH:
A->bf = RH;
B->bf = EH;
break;
case EH:
A->bf = EH;
B->bf = EH;
break;
case RH:
A->bf = EH;
B->bf = LH;
break;
default:
break;
}
E->bf = EH;
RotateLeft(&(*root)->lnext);
RotateRight(root);
break;
default:
break;
}
}
template<class T> void CBTree<T>::RightBalance(node<T> **root)
{
node<T> *A = *root;
node<T> *C = A->rnext;
node<T> *D = C->lnext;
switch (C->bf)
{
//右高(RR型)
// A(-1) C
// / \ / \
// B C(-1) => A E
// | / \ / \ |
// D E B D +
// | | | |
// +
case RH:
A->bf = C->bf = EH;
RotateLeft(root);
break;
//左高(RL型)
// A A D
// / \ / \ / \
// B C ==> B D ==> A C
// | / \ R | / \ L / \ / \
// D E F C B F G E
// / \ | | / \ | | | |
// F G G E +
// | | | |
// + +
case LH:
switch (D->bf)
{
case RH:
A->bf = LH;
C->bf = EH;
break;
case EH:
A->bf = EH;
C->bf = EH;
break;
case LH:
A->bf = EH;
C->bf = RH;
break;
}
D->bf = EH;
RotateRight(&(*root)->rnext);
RotateLeft(root);
break;
default:
break;
}
}
template<class T> int CBTree<T>::InsertAVL(node<T> **p_root, T key,node<T> **p_keypos, bool &taller)
{
node<T> *root = *p_root;
if (root == NULL)
{
//没有找到
node<T> *p = (node<T> *)malloc(sizeof(node<T>));
p->data = key;
p->lnext = p->rnext = NULL;
p->bf = EH;
*p_root = p;
taller = true;
return 0;
}
else if (root->data == key)
{
//找到
*p_keypos = root;
return -1;
}
else if (key < root->data)
{
//继续找
if (-1 == InsertAVL(&root->lnext, key, p_keypos, taller))
{
return -1;
}
if (taller)
{
switch (root->bf)
{
case LH:
LeftBalance(p_root);
taller = false;
break;
case EH:
root->bf = LH;
taller = true;
break;
case RH:
root->bf = EH;
taller = false;
break;
}
}
return 0;
}
else
{
//继续找
if (-1 == InsertAVL(&root->rnext, key, p_keypos, taller))
{
return -1;
}
if (taller)
{
switch(root->bf)
{
case LH:
root->bf = EH;
taller = false;
break;
case EH:
root->bf = RH;
taller = true;
break;
case RH:
RightBalance(p_root);
taller = false;
break;
}
}
return 0;
}
}
//给你一个接点排好序的算法：假说左孩子小于等于根接点，右孩子大于等于根接点
//删除当前接点，1）当前结点的左孩子为空，右孩子移到当前接点的位置。
// 2）当前结点的右孩为空，左孩子移到当前接点的位置。
// 3）当前结点左右孩子都为空，当前位置改为空。
// 4）当前结点左右孩子都不为空，左子树接点是小于父接点，所有的右子树大于父接点，
// 现在删除的正好是左右子树的父接点，那么左子树中，肯定是左子树的最右孩子排在右子树
// 的根前面，那么先把左子树的根连接到当前删除的接点位置，再找到左子树的最右孩子，把
// 当前接点的右子树的根连接上去就是这些了
template<class T> int CBTree<T>::DeleteAVL(node<T> **p_root, T key,node<T> **p_keyparentpos, bool &lower)
{
node<T> *root = *p_root;
if(!root)
{
return -1;
}
if(key == root->data)
{
node<T> *lnext = root->lnext;
node<T> *rnext = root->rnext;
delete root;
root = *p_root = NULL;
return 0;
}
else if(key < root->data)
{
//Go on searching...
if(-1 == DeleteAVL(&root->lnext, key, p_keyparentpos, lower))
{
return -1;
}
if(lower)
{
switch(root->bf)
{
case(LH):
root->bf = EH;
lower = false;
break;
case(EH):
root->bf = RH;
lower = true;
break;
case(RH):
LeftBalance(p_root);
lower = false;
break;
}
}
return 0;
}
else
{
//Go on searching...
if(-1 == DeleteAVL(&root->rnext, key, p_keyparentpos, lower))
{
return -1;
}
if(lower)
{
switch(root->bf)
{
case(LH):
LeftBalance(p_root);
lower = false;
break;
case(EH):
root->bf = LH;
lower = true;
break;
case(RH):
root->bf = EH;
lower = false;
break;
}
}
return 0;
}
}
/*int main(int argc, char* argv[])
{
printf("Hello World!\n");
CBTree<int> bt;
node<int> *root = NULL;
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
int a[] = { 1,30,2,29,3};
void output(node<int> *, int);
int i;
bool taller;
node<int> *position;
for (i=0; i<5; i++)
{
bt.InsertAVL(&root, a[i], &position, taller);
printf("insert %d...\n", a[i]);
output(root, 0);
printf("|\n");
}
for(i = 4; i >= 0; i--)
{
bt.DeleteAVL(&root, a[i], &position, taller);
printf("delete %d...\n", a[i]);
output(root, 0);
printf("|\n");
}
return 0;
}
void output(node<int> *root, int floor)
{
int i;
if (root == NULL)
return;
for (i=0; i<10; i++)
{
if (i < floor)
{
printf(" ");
}
else if (i == floor)
{
printf("%3d", root->data);
}
else
{
printf("====");
}
}
printf("\n");
output(root->lnext, floor + 1);
output(root->rnext, floor + 1);
}*/
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -