// 2018-12-08
// By Mattuy
// AVL树的C语言实现
// 实现对AVL树节点的增删改查
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int DataType; //树的数据域
//定义AVL树
typedef struct SearchTree
{
int height; //树的深度，空树（NULL）的深度为-1
DataType value;
struct SearchTree* left;
struct SearchTree* right;
} TreeNode, SearchTree;
TreeNode* SingleRotateWithLeft(TreeNode* grandpa); //左左单旋转
TreeNode* SingleRotateWithRight(TreeNode* grandpa); //右右单旋转
TreeNode* DoubleRotateWithLeft(TreeNode* grandpa); //左右双旋转
TreeNode* DoubleRotateWithRight(TreeNode* grandpa); //右左双旋转
TreeNode* Remove(SearchTree* tree, TreeNode* node); //删除节点
void Assign(TreeNode* dest, DataType* value); //将一个节点的值赋给另外一个节点
TreeNode* Find(SearchTree* tree, DataType value); //查找节点
//获取树高度
int getHeight(SearchTree* tree);
//删除同时有左右孩子的节点时寻找子合适的子节点来顶替被删除节点
TreeNode* findExtreamNode(TreeNode* node);
//中序遍历输出AVL树
void output(SearchTree* tree);
//左左单旋转
TreeNode* SingleRotateWithLeft(TreeNode* grandpa)
{
//将祖父变为父亲的右儿子，父亲原来的右儿子变为祖父的左儿子（祖父原来的左儿子就是父亲，关系已断开）
TreeNode* parent = grandpa->left;
grandpa->left = parent->right;
parent->right = grandpa;
//新的关系是，原来的孙子和祖父变成父亲的左右儿子（孙子位置没动）。
//原祖父(现父亲右儿子)的深度取决于原父亲的右儿子和原祖父的右儿子
//父亲的深度取决于孙子和祖父（现右儿子），因此须先计算祖父（右儿子）的深度
grandpa->height = max(getHeight(grandpa->left), getHeight(grandpa->right)) + 1;
parent->height = max(getHeight(parent->left), grandpa->height) + 1;
//返回新的根节点（原来是祖父，现在是父亲）
return parent;
}
//右右单旋转
TreeNode* SingleRotateWithRight(TreeNode* grandpa)
{
TreeNode* parent = grandpa->right;
grandpa->right = parent->left;
parent->left = grandpa;
grandpa->height = max(getHeight(grandpa->left), getHeight(grandpa->right)) + 1;
parent->height = max(getHeight(parent->right), grandpa->height) + 1;
return parent;
}
//左右双旋转
TreeNode* DoubleRotateWithLeft(TreeNode* grandpa)
{
grandpa->left = SingleRotateWithRight(grandpa->left);
return SingleRotateWithLeft(grandpa);
}
//右左双旋转
TreeNode* DoubleRotateWithRight(TreeNode* grandpa)
{
grandpa->right = SingleRotateWithLeft(grandpa->right);
return SingleRotateWithRight(grandpa);
}
//插入节点，返回插入后的根节点
TreeNode* Insert(SearchTree* tree, DataType value)
{
if (tree == NULL)
{
TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
if (!temp)
{
return NULL;
} //申请内存失败
temp->left = temp->right = NULL;
temp->value = value;
temp->height = 0;
return temp;
} //插入新节点
if (value < tree->value)
{
tree->left = Insert(tree->left, value);
//当平衡被破坏时调整
if (getHeight(tree->left) - getHeight(tree->right) == 2)
{
//插入的节点在哪边就旋转哪边
if (value < tree->left->value)
tree = SingleRotateWithLeft(tree);
else
tree = DoubleRotateWithLeft(tree);
}
}
else if (value > tree->value)
{
tree->right = Insert(tree->right, value);
if (getHeight(tree->right) - getHeight(tree->left) == 2)
{
if (value > tree->right->value)
tree = SingleRotateWithRight(tree);
else
tree = DoubleRotateWithRight(tree);
}
}
else
return NULL; //不允许插入值相同的节点
tree->height = max(getHeight(tree-> left), getHeight(tree->right)) + 1;
return tree;
}
//删除节点
TreeNode* Remove(SearchTree* tree, TreeNode* node)
{
if (!tree || !node)
return NULL;
if (node == tree)
{
if (tree->left && tree->right)
{
//找到一个合适的子节点来替换被删除的节点
TreeNode* leaf = findExtreamNode(tree);
//记录是在左子树找的子节点还是右子树
bool doesLeft = true;
if (leaf->value > tree->value)
doesLeft = false;
//用子节点的值替代要删除节点的值
Assign(tree, leaf->value);
//删除子节点。因为现在tree节点的值和子节点一样，所以不能直接传tree节点作为参数
if (doesLeft)
tree->left = Remove(tree->left, leaf);
else
tree->right = Remove(tree->right, leaf);
tree->height = max(getHeight(tree->left), getHeight(tree->right)) + 1;
return tree;
} //被删除的节点有两个儿子
else if (!tree->left && !tree->right)
{
free(tree);
return NULL;
} //被删除的是叶子节点
else if (tree->left || tree->right)
{
TreeNode* temp = tree->left ? tree->left : tree->right;
free(tree);
return temp;
} //被删除的节点只有一个儿子
} //当前节点为待删除节点
else if(node->value > tree->value)
{
tree->right = Remove(tree->right, node);
//如果删除节点后破坏平衡，调整以重新平衡
//从右子树删除节点后进行左旋转
//如果左孩子有左孩子则进行单旋转，否则进行双旋转
if (abs(getHeight(tree->left) - getHeight(tree->right)) == 2)
tree = tree->left->left ? SingleRotateWithLeft(tree) : DoubleRotateWithLeft(tree);
} //待删除节点在右子树
else
{
tree->left = Remove(tree->left, node);
//从左子树删除节点后进行右旋转
//如果右孩子有右孩子则进行单旋转，否则进行双旋转
if (abs(getHeight(tree->left) - getHeight(tree->right)) == 2)
tree = tree->right->right ? SingleRotateWithRight(tree) : DoubleRotateWithRight(tree);
} //待删除节点在左子树
tree->height = max(getHeight(tree->left), getHeight(tree->right)) + 1;
return tree;
}
//为节点赋值
void Assign(TreeNode* dest, DataType* value)
{
dest->value = value;
}
//查找
TreeNode* Find(SearchTree* tree, DataType value)
{
TreeNode* cur = tree;
while (cur != NULL)
{
if (cur->value == value)
break;
cur = value > cur->value ? cur->right : cur->left;
}
return cur;
}
//获取树高度
int getHeight(SearchTree* tree)
{
return tree ? tree->height : -1;
}
/**
* 当被删除节点有左右孩子时找出左子树的最右节点或右子树的最左节点。务必保证传入的参数为被搜索的节点，
* 函数将根据其左右子树的深度来决定返回左孩子的最右子树还是右孩子的最左子树。
* 此函数仅应被Remove函数调用
*/
TreeNode* findExtreamNode(TreeNode* node)
{
if (node->right->height > node->left->height)
{
TreeNode* cur = node->right;
while (cur->left)
cur = cur->left;
return cur;
}
else
{
TreeNode* cur = node->left;
while (cur->right)
{
cur = cur->right;
}
return cur;
}
}
//中序遍历输出
void output(SearchTree* tree)
{
if (!tree) return;
output(tree->left);
printf("value = %d, height = %d\n", tree->value, tree->height);
output(tree->right);
}
//测试
int main()
{
SearchTree* tree = NULL;
for (int i = 1; i <= 8; i++)
tree = Insert(tree, i);
tree = Remove(tree, Find(tree, 6));
output(tree);
system("pause");
}