实现一个平衡二叉树算法
时间: 2023-12-01 12:39:05 浏览: 36
平衡二叉树是一种特殊的二叉树,它的左右子树的高度差不超过1,这样可以保证二叉树的查找、插入、删除等操作的时间复杂度都是O(logn)级别的。下面是一个简单的平衡二叉树算法的实现:
1.定义平衡二叉树结构体:
```
typedef struct AVLNode{
int depth;//深度
struct AVLNode *left;//左孩子
struct AVLNode *right;//右孩子
struct AVLNode *parent;//父结点
ElenmentType value; //值
}AVLtree,Tree;
```
2.实现平衡二叉树的插入操作:
```
Tree* insert(Tree *root, ElenmentType value){
if(root == NULL){
root = (Tree*)malloc(sizeof(Tree));
root->value = value;
root->depth = 1;
root->left = NULL;
root->right = NULL;
root->parent = NULL;
return root;
}
if(value < root->value){
root->left = insert(root->left, value);
root->left->parent = root;
}else{
root->right = insert(root->right, value);
root->right->parent = root;
}
int left_depth = get_depth(root->left);
int right_depth = get_depth(root->right);
if(left_depth - right_depth > 1){
if(get_depth(root->left->left) >= get_depth(root->left->right)){
root = right_rotate(root);
}else{
root->left = left_rotate(root->left);
root = right_rotate(root);
}
}else if(right_depth - left_depth > 1){
if(get_depth(root->right->right) >= get_depth(root->right->left)){
root = left_rotate(root);
}else{
root->right = right_rotate(root->right);
root = left_rotate(root);
}
}
root->depth = max(get_depth(root->left), get_depth(root->right)) + 1;
return root;
}
```
3.实现平衡二叉树的删除操作:
```
Tree* delete(Tree *root, ElenmentType value){
if(root == NULL){
return NULL;
}
if(value < root->value){
root->left = delete(root->left, value);
if(root->left != NULL){
root->left->parent = root;
}
}else if(value > root->value){
root->right = delete(root->right, value);
if(root->right != NULL){
root->right->parent = root;
}
}else{
if(root->left == NULL && root->right == NULL){
free(root);
return NULL;
}else if(root->left == NULL){
Tree *temp = root->right;
free(root);
return temp;
}else if(root->right == NULL){
Tree *temp = root->left;
free(root);
return temp;
}else{
Tree *temp = find_min(root->right);
root->value = temp->value;
root->right = delete(root->right, temp->value);
if(root->right != NULL){
root->right->parent = root;
}
}
}
int left_depth = get_depth(root->left);
int right_depth = get_depth(root->right);
if(left_depth - right_depth > 1){
if(get_depth(root->left->left) >= get_depth(root->left->right)){
root = right_rotate(root);
}else{
root->left = left_rotate(root->left);
root = right_rotate(root);
}
}else if(right_depth - left_depth > 1){
if(get_depth(root->right->right) >= get_depth(root->right->left)){
root = left_rotate(root);
}else{
root->right = right_rotate(root->right);
root = left_rotate(root);
}
}
root->depth = max(get_depth(root->left), get_depth(root->right)) + 1;
return root;
}
```
4.实现平衡二叉树的左旋和右旋操作:
```
Tree* left_rotate(Tree *root){
Tree *new_root = root->right;
root->right = new_root->left;
if(new_root->left != NULL){
new_root->left->parent = root;
}
new_root->left = root;
new_root->parent = root->parent;
root->parent = new_root;
root->depth = max(get_depth(root->left), get_depth(root->right)) + 1;
new_root->depth = max(get_depth(new_root->left), get_depth(new_root->right)) + 1;
return new_root;
}
Tree* right_rotate(Tree *root){
Tree *new_root = root->left;
root->left = new_root->right;
if(new_root->right != NULL){
new_root->right->parent = root;
}
new_root->right = root;
new_root->parent = root->parent;
root->parent = new_root;
root->depth = max(get_depth(root->left), get_depth(root->right)) + 1;
new_root->depth = max(get_depth(new_root->left), get_depth(new_root->right)) + 1;
return new_root;
}
```
5.实现平衡二叉树的查找操作:
```
Tree* find(Tree *root, ElenmentType value){
if(root == NULL){
return NULL;
}
if(value < root->value){
return find(root->left, value);
}else if(value > root->value){
return find(root->right, value);
}else{
return root;
}
}
```
6.实现平衡二叉树的深度计算操作:
```
int get_depth(Tree *root){
if(root == NULL){
return 0;
}
return root->depth;
}
```