C++AVL树
2020-07-11 本文已影响0人
youxiaochen
前言
AVL树又叫平衡二叉排序树,是一棵空树或它的任何节点的两个子树的高度最大差别为1的二叉排序树
AVL平衡二叉排序树.png
一：平衡调整
每次在插入或者删除节点的时候,都有可能导致树的不平衡, 这里就介绍插入节点时的情况, 删除节点与插入节点的平衡调整类似, 节点调整的4种旋转直接看图
，
，
1：左旋，节点的右子树高度与左子树高度差>1时, 且右子节点的右子树高度 >= 右子节点的左子树高度
左旋转
2：右旋，节点的左子树高度与右子树高度差>1时, 且左子节点的左子树高度 >= 左子节点的右子树高度
右旋转.png
3：先右旋再左旋(1的另一种情况)，节点的右子树高度与左子树高度差>1时, 且右子节点的右子树高度 < 右子节点的左子树高度
先右旋再左旋.png
4：先左旋再右旋(2的另一种情况)，节点的左子树高度与右子树高度差>1时, 且左子节点的左子树高度 < 左子节点的右子树高度
先左旋再右旋.png
struct AVLTreeNode {
int data;
int height = 1;
AVLTreeNode *left = NULL;
AVLTreeNode *right = NULL;
AVLTreeNode(int data) {
this->data = data;
}
//节点高度
static int getNodeHeight(AVLTreeNode *node) {
return node == NULL ? 0 : node->height;
}
//重新计算高度
void calculateHeight() {
this->height = max(getNodeHeight(left), getNodeHeight(right)) + 1;
}
//检测右旋
AVLTreeNode* checkRightRotate() {
if (getNodeHeight(this->left) - getNodeHeight(this->right) > 1) {//左孩子>右孩子, 左孩子必不NULL
if (getNodeHeight(this->left->right) > getNodeHeight(this->left->left)) {
return leftRightRotate();
}
return rightRotate();
}
return this;
}
//检测左旋
AVLTreeNode* checkLeftRotate() {
if (getNodeHeight(this->right) - getNodeHeight(this->left) > 1) {//左孩子>右孩子, 左孩子必不NULL
if (getNodeHeight(this->right->left) > getNodeHeight(this->right->right)) {
return rightLeftRotate();
}
return leftRotate();
}
return this;
}
//左旋转
AVLTreeNode* leftRotate() {
AVLTreeNode *rotateRight = this->right;
this->right = rotateRight->left;
rotateRight->left = this;
this->calculateHeight();
rotateRight->calculateHeight();
return rotateRight;
}
//右节点先右旋,再左旋转
AVLTreeNode* rightLeftRotate() {
this->right = this->right->rightRotate();
return this->leftRotate();
}
//右旋转
AVLTreeNode* rightRotate() {
AVLTreeNode *rotateLeft = this->left;
this->left = rotateLeft->right;
rotateLeft->right = this;
this->calculateHeight();
rotateLeft->calculateHeight();
return rotateLeft;
}
//左节点先左旋,再右旋
AVLTreeNode* leftRightRotate() {
this->left = this->left->leftRotate();
return this->rightRotate();
}
};
二：删除节点
删除节点的方式与二叉排序树删除方法相似,删除之后检测平衡调整, 删除节点可能导致的不平衡需要的调整方式与添加节点类似
1：删除叶子节点(左右子节点都为空)时,不影响整体树结构,直接删除即可
2：删除的节点只有左子节点或只有右子节点(即右子节点为空或左子节点为空)时,只需要将其左子节点或右子节点代替删除的节点位置即可
3：删除节点的左右子节点都不为空时，找到删除节点的前驱(右子树高度<=左子树高度时)或者后继(右子树高度>左子树高度时)为替代删除的节点, 然后删除前驱或者后继点节即可,前驱节点为最右节点不存在右子节点,后继节点为最左节点不存在左子节点,因此删除前驱或后继节点又相当到第1,或第2步了
class AVLTree {
private:
AVLTreeNode *root = NULL;
int len = 0;
//释放节点及其所有子节点
void freeNode(AVLTreeNode *node);
//添加新节点
AVLTreeNode* addNode(AVLTreeNode *node, int data);
//删除节点
AVLTreeNode* removeNode(AVLTreeNode *node, int data);
/**
* 获取右节点中最小的节点,并移除该节点
* @param node
* @param successor
* @return 需要旋转时返回旋转后的节点
*/
AVLTreeNode* removeLeftMinNode(AVLTreeNode *node, AVLTreeNode **successor);
/**
* 获取左节点中最大的节点,并移除该节点
* @param node
* @param successor
* @return 需要旋转时返回旋转后的节点
*/
AVLTreeNode* removeRightMaxNode(AVLTreeNode *node, AVLTreeNode **successor);
public:
~AVLTree();
int size();
void add(int data);
void remove(int data);
};
AVLTree::~AVLTree() {
freeNode(root);
root = NULL;
}
void AVLTree::freeNode(AVLTreeNode *node) {
if (node) {
freeNode(node->left);
freeNode(node->right);
delete node;
}
}
AVLTreeNode* AVLTree::addNode(AVLTreeNode *node, int data) {
if (node == NULL) {
len++;
return new AVLTreeNode(data);
}
if (node->data <= data) {//允许有相同值, 若是在Map中要另处理
node->right = addNode(node->right, data);
node = node->checkLeftRotate();
} else {
node->left = addNode(node->left, data);
node = node->checkRightRotate();
}
node->calculateHeight();
return node;
}
AVLTreeNode* AVLTree::removeRightMaxNode(AVLTreeNode *node, AVLTreeNode **successor) {
if (node->right) {
node->right = removeRightMaxNode(node->right, successor);
node = node->checkRightRotate();
node->calculateHeight();
return node;
} else {
*successor = node;
return node->left;
}
}
AVLTreeNode* AVLTree::removeLeftMinNode(AVLTreeNode *node, AVLTreeNode **successor) {
if (node->left) {
node->left = removeLeftMinNode(node->left, successor);
node = node->checkLeftRotate();
node->calculateHeight();
return node;
} else {
*successor = node;
return node->right;
}
}
AVLTreeNode* AVLTree::removeNode(AVLTreeNode *node, int data) {
if (!node) return NULL;
if (node->data > data) {
node->left = removeNode(node->left, data);
node = node->checkLeftRotate();
} else if (node->data < data) {
node->right = removeNode(node->right, data);
node = node->checkRightRotate();
} else {
len--;
if (!node->left && !node->right) {
delete node;
return NULL;
}
if (!node->left) {
AVLTreeNode *right = node->right;
delete node;
return right;
}
if (!node->right) {
AVLTreeNode *left = node->left;
delete node;
return left;
}
AVLTreeNode *successor;
if (AVLTreeNode::getNodeHeight(node->right) < AVLTreeNode::getNodeHeight(node->left)) {
//这里不需要检测平衡,删除节点后不会大于右节点
node->left = removeRightMaxNode(node->left, &successor);
} else {
//这里不需要检测平衡,删除节点后不会大于左节点
node->right = removeLeftMinNode(node->right, &successor);
}
node->data = successor->data;
delete successor;
}
node->calculateHeight();
return node;
}
int AVLTree::size() {
return len;
}
void AVLTree::add(int data) {
root = addNode(root, data);
}
void AVLTree::remove(int data) {
root = removeNode(root, data);
}
