生成avl树的伪代码示例
时间: 2023-05-26 09:03:47 浏览: 55
以下是用伪代码示例生成AVL树的算法:
AVL树结构定义:
```
struct Node {
int value; //节点值
int height; //节点高度
Node *left; //左子树指针
Node *right; //右子树指针
};
```
生成AVL树的算法:
```
//计算节点高度
int calcHeight(Node *node) {
if (node == NULL) {
return 0;
}
return max(calcHeight(node->left), calcHeight(node->right)) + 1;
}
//获取平衡因子
int getBalanceFactor(Node *node) {
if (node == NULL) {
return 0;
}
return calcHeight(node->left) - calcHeight(node->right);
}
//左旋转调整
Node *leftRotate(Node *node) {
Node *newroot = node->right;
node->right = newroot->left;
newroot->left = node;
//更新节点高度
node->height = max(calcHeight(node->left), calcHeight(node->right)) + 1;
newroot->height = max(calcHeight(newroot->left), calcHeight(newroot->right)) + 1;
return newroot;
}
//右旋转调整
Node *rightRotate(Node *node) {
Node *newroot = node->left;
node->left = newroot->right;
newroot->right = node;
//更新节点高度
node->height = max(calcHeight(node->left), calcHeight(node->right)) + 1;
newroot->height = max(calcHeight(newroot->left), calcHeight(newroot->right)) + 1;
return newroot;
}
//插入节点
Node *insert(Node *node, int value) {
if (node == NULL) {
node = new Node();
node->value = value;
node->height = 1;
node->left = node->right = NULL;
return node;
}
if (value < node->value) {
node->left = insert(node->left, value);
} else if (value > node->value) {
node->right = insert(node->right, value);
} else {
//已存在该节点
return node;
}
//更新节点高度
node->height = max(calcHeight(node->left), calcHeight(node->right)) + 1;
//检查是否需要旋转调整
int balanceFactor = getBalanceFactor(node);
if (balanceFactor > 1 && value < node->left->value) { //LL型情况
return rightRotate(node);
} else if (balanceFactor < -1 && value > node->right->value) { //RR型情况
return leftRotate(node);
} else if (balanceFactor > 1 && value > node->left->value) { //LR型情况
node->left = leftRotate(node->left);
return rightRotate(node);
} else if (balanceFactor < -1 && value < node->right->value) {//RL型情况
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
```