밸 런 스 트 리 의 C + + 구현
6942 단어 데이터 구조 및 구현
#include
#define EH 0
#define LH 1
#define RH -1
#define empty -1000
using namespace std;
struct node *PtrToLNode;
typedef struct node{
int data;
struct node* rchild;
struct node* lchild;
int bf;
}*BSTree;
bool taller,shorter; int a = 0;
void L_Rotate(BSTree &T);
void R_Rotate(BSTree &T);
void LeftBalance(BSTree &T);
void RightBalance(BSTree &T);
bool insert(BSTree &T, int d, bool &taller);
bool Delete(BSTree &T , int d , bool &shorter);
void NodeDelete(BSTree &Node, BSTree &T, bool rl, bool &shorter);
int main() {
int n = 0;
cout << " :n" << endl;
cin >> n;
cout << " n :" << endl;
if (n == 0)return 0;
BSTree Tree=NULL;
for (int i = 0; i < n; i++) {
cin >> a;
insert(Tree, a, taller);
}
cout << " , -1:" << endl;
int da = 0;
cin >> da;
if(da!=-1) Delete(Tree, da,shorter);
BSTree f[100] = { NULL };
f[0] = Tree;
int i = 0, t = 0;
cout << "AVL :" << endl;
while (f[i] != NULL) {
cout << f[i]->data << " ";
if (f[i]->lchild != NULL)f[++t] = f[i]->lchild;
if (f[i]->rchild != NULL)f[++t] = f[i]->rchild;
i++;
}
return 0;
}
void R_Rotate(BSTree &T) {
BSTree lc = T->lchild;
T->lchild = lc->rchild;
lc->rchild = T;
T = lc;
return;
}
void L_Rotate(BSTree &T) {
BSTree rc = T->rchild;
T->rchild = rc->lchild;
rc->lchild = T;
T = rc;
return;
}
void LeftBalance(BSTree &T) {
BSTree lc = T->lchild;
switch (lc->bf) {
case LH:T->bf = lc->bf = EH;
R_Rotate(T); break;
case RH:
BSTree rc = lc->rchild;
switch (rc->bf) {
case LH:lc->bf = EH; T->bf = RH; break;
case EH:lc->bf = T->bf = EH; break;
case RH:lc->bf = LH; T->bf = EH; break;
}
rc->bf = EH;
L_Rotate(T->lchild);
R_Rotate(T);
break;
}
}
void RightBalance(BSTree &T) {
BSTree rc = T->rchild;
switch (rc->bf) {
case RH:rc->bf = T->bf = EH;
L_Rotate(T); break;
case LH:
BSTree lc = rc->lchild;
switch (lc->bf) {
case LH:T->bf = EH; rc->bf = RH; break;
case EH:T->bf = rc->bf = EH; break;
case RH:T->bf = LH; rc->bf = EH; break;
}
lc->bf = EH;
R_Rotate(T->rchild);
L_Rotate(T);
break;
}
}
bool insert(BSTree &T, int d, bool &taller) {
if (T == NULL){
T = (BSTree)malloc(sizeof(struct node));
T->lchild = T->rchild = NULL; T->data = d; taller = true;
T->bf = EH;
}
else {
if (T->data == d) { taller = false; return false; }
else if (d < T->data) {
if (!insert(T->lchild, d, taller)) return false;
if (taller)
switch (T->bf) {
case LH:LeftBalance(T); taller = false; break;
case EH:T->bf = LH; taller = true; break;
case RH:T->bf = EH; taller = false; break;
}
}
else {
if (!insert(T->rchild, d, taller)) return false;
if (taller)
switch (T->bf) {
case LH:T->bf = EH; taller = false; break;
case EH:T->bf = RH; taller = true; break;
case RH:RightBalance(T); taller = false; break;
}
}
}
return true;
}
bool Delete(BSTree &T, int d, bool &shorter) {
if (T == NULL) return false;
else {
if (d == T->data) {
if (T->lchild ==NULL&& T->rchild == NULL) {
T->data = empty;
return true;
}
else
switch (T->bf){
case LH: NodeDelete(T,T->lchild,0, shorter);
if (T->lchild->data == empty)T->lchild = NULL;break;
case RH: NodeDelete(T,T->rchild,1, shorter);
if (T->rchild->data == empty)T->lchild = NULL; break;
case EH: NodeDelete(T,T->lchild,0, shorter);
if (T->lchild->data == empty)T->lchild = NULL; break;
}
return true;
}
else if (d > T->data) {
if (!Delete(T->rchild, d, shorter)) return false;
if (T->rchild->data == empty) T->rchild = NULL;
if(shorter)
switch (T->bf){
case LH: LeftBalance(T); shorter = false; break;
case RH: T->bf = EH;shorter=true; break;
case EH: T->bf = LH; shorter = false; break;
}
}
else if (d < T->data) {
if (!Delete(T->lchild, d, shorter)) return false;
if (T->lchild->data == empty) T->lchild = NULL;
if (shorter)
switch (T->bf){
case LH: T->bf = EH; shorter = true; break;
case RH: RightBalance(T); shorter = false; break;
case EH: T->bf = RH; shorter = false; break;
}
}
}
return true;
}
void NodeDelete(BSTree &Node, BSTree &T,bool rl, bool &shorter) {
if (rl == 1) {
if (T->lchild == NULL) {
Node->data=T->data;shorter = true;
if (T->rchild != NULL) T = T->rchild;
else T->data = empty;
}
else {
NodeDelete(Node, T->lchild, rl, shorter);
if (shorter) {
if (T->lchild!=NULL)if(T->lchild->data == empty) T->lchild = NULL;
switch (T->bf){
case LH:T->bf = EH; shorter = true; break;
case RH:RightBalance(T);shorter = false; break;
case EH:T->bf = RH; shorter = false; break;
}
}
}
}
else {
if (T->rchild == NULL) {
Node->data = T->data;shorter = true;
if (T->lchild != NULL) T = T->lchild;
else T->data = empty;
}
else {
NodeDelete(Node, T->rchild, rl, shorter);
if (shorter) {
if (T->rchild != NULL)if (T->rchild->data == empty) T->rchild = NULL;
switch (T->bf){
case LH:LeftBalance(T); shorter = false;break;
case RH:T->bf = EH; break;
case EH:T->bf = LH; break;
}
}
}
}
}