平衡二叉树(AVL树)
前提是有序的二叉树,它的左右子树的高度差不超过1,而且它的所有子树也满足这个条件
如果一个有序二叉树呈现接近单支状(类似链表),它的查找效率接近链表,因此只有达到平衡
由于节点的值受限,因此只能通过调整达到有序,而不能进行值的修改
二叉树不平衡的基础原因:有以下四种
1 x
/ \ y
y t1 以y为轴向右旋转 / \
/ \ z x
z t2 / \ / \
/ \ t3 t4 t2 t1
t3 t4
2 x y
/ \ / \
t1 y 以y为轴向左旋转 x z
/ \ / \ / \
t2 z t1 t2 t3 t4
/ \
t3 t4
3 x x z
/ \ / \ / \
y t1 z t1 y x
/ \ / \ / \ / \
t2 z 以z为轴向左旋转 y t4 以z为轴向右旋转 t2 t3 t4 t1 最终平衡
/ \ / \
t3 t4 t2 t3
4 x x z
/ \ / \ / \
t1 y t1 z x y
/ \ / \ / \ / \
z t2 以z为轴向右旋转 t3 y 以z为轴向左旋转 t1 t3 t4 t2 最终平衡
/ \ / \
t3 t4 t4 t2以下为平衡二叉树的操作以及如何解决上述四种情况
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct TreeNode
{
int data;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
TreeNode* create_tree_node(int data)
{
TreeNode* node = malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// 高度
int high_tree(TreeNode* root)
{
if(NULL == root) return 0;
int lh = high_tree(root->left);
int rh = high_tree(root->right);
return lh>rh ? lh+1 : rh+1;
}
// 计算左右子树高度差
int diff_high(TreeNode* root)
{
return high_tree(root->left) – high_tree(root->right);
}
// 右旋
TreeNode* right_rotate(TreeNode* x)
{
TreeNode* y = x->left;
TreeNode* t2 = y->right;
y->right = x;
x->left = t2;
return y;
}
// 左旋
TreeNode* left_rotate(TreeNode* x)
{
TreeNode* y = x->right;
TreeNode* t2 = y->left;
y->left = x;
x->right = t2;
return y;
}
// 自动调成平衡 返回调整后的root
TreeNode* auto_balance(TreeNode* x)
{
if(NULL == x) return NULL;
int lh = high_tree(x->left);
int rh = high_tree(x->right);
// 左比右高
if(lh-rh > 1)
{
if(diff_high(x->left) >= 0)
{
// x->left 为轴 右旋
x = right_rotate(x);
}
else
{
// 左旋
x->left = left_rotate(x->left);
// 右旋
x = right_rotate(x);
}
}
// 右比左高
if(rh-lh >1)
{
if(diff_high(x->right) >= 0)
{
// 右旋
x->right = right_rotate(x->right);
// 左旋
x = left_rotate(x);
}
else
{
// 左旋
x = left_rotate(x);
}
}
return x;
}
// 添加 通过返回值返回添加后树的root
// 返回值相当于root的指向
TreeNode* insert_tree(TreeNode* root,int data)
{
if(NULL == root)
return create_tree_node(data);
if(data < root->data)
root->left = insert_tree(root->left,data);
else
root->right = insert_tree(root->right,data);
// 调整成平衡
root = auto_balance(root);
return root;
}
void dlr_show(TreeNode* root)
{
if(NULL == root) return;
printf(“%d “,root->data);
dlr_show(root->left);
dlr_show(root->right);
}
void ldr_show(TreeNode* root)
{
if(NULL == root) return;
ldr_show(root->left);
printf(“%d “,root->data);
ldr_show(root->right);
}
/*
删除节点
1、待删除的节点是叶子节点，直接删除
2、待删除的节点左或右子树为空，则使用非空子节点替换
3、待删除的节点左右子树非空，根据左右子树高度，选择高的一边，如果是左高则选择左子树中的最大值替换待删除节点的值，然后删除左子树中的最大值节点，反之则选择右子树的最小值节点进行同样操作
重新调整平衡
*/
// 找最大值
TreeNode* max_data(TreeNode* root)
{
TreeNode* max = root;
while(max->right) max = max->right;
return max;
}
// 找最小值
TreeNode* min_data(TreeNode* root)
{
TreeNode* min = root;
while(min->left) min = min->left;
return min;
}
TreeNode* del_tree(TreeNode* root,int data)
{
if(NULL == root) return NULL;
if(data == root->data)
{
// 左右为空，直接删除
if(NULL == root->left && NULL == root->right)
{
free(root);
return NULL;
}
// 左子树非空
if(NULL == root->right)
{
TreeNode* temp = root->left;
free(root);
return temp;
}
// 右子树非空
if(NULL == root->left)
{
TreeNode* temp = root->right;
free(root);
return temp;
}
// 左右子树非空
int lh = high_tree(root->left);
int rh = high_tree(root->right);
if(lh >= rh)
{
// 左子树找最大值节点
TreeNode* node = max_data(root->left);
// 把最大值赋值给待删除节点
root->data = node->data;
// 在左子树删除最大值节点
root->left = del_tree(root->left,node->data);
}
else
{
// 右子树找最小值节点
TreeNode* node = min_data(root->right);
// 把最小值赋值给待删除节点
root->data = node->data;
// 在右子树删除最小值节点
root->right = del_tree(root->right,node->data);
}
}
if(data < root->data)
root->left = del_tree(root->left,data);
else
root->right = del_tree(root->right,data);
root = auto_balance(root);
return root;
}
int main(int argc,const char* argv[])
{
TreeNode* root = NULL;
for(int i=0; i<10; i++)
{
root = insert_tree(root,i+1);
}
root = del_tree(root,1);
root = del_tree(root,3);
root = del_tree(root,6);
printf(“dlr:”);
dlr_show(root);
printf(“\nldr:”);
ldr_show(root);
}