平衡二叉树的左旋右旋代码
时间: 2024-05-16 14:10:37 浏览: 76
平衡二叉树是一种特殊的二叉搜索树,其左子树和右子树的高度差不超过1,可以避免二叉搜索树退化为链表的情况,提高了查找、插入和删除的效率。
平衡二叉树的左旋和右旋是平衡二叉树中常用的操作,用于调整树的平衡性。左旋是将当前节点的右子树作为新的子树,当前节点成为新子树的左子树;右旋是将当前节点的左子树作为新的子树,当前节点成为新子树的右子树。
以下是平衡二叉树的左旋和右旋代码:
```
// 左旋
void AVLTree::leftRotate(AVLTreeNode* &node) {
AVLTreeNode* rightChild = node->right;
node->right = rightChild->left;
rightChild->left = node;
node = rightChild;
// 更新节点高度
node->left->height = max(height(node->left->left), height(node->left->right)) + 1;
node->height = max(height(node->left), height(node->right)) + 1;
}
// 右旋
void AVLTree::rightRotate(AVLTreeNode* &node) {
AVLTreeNode* leftChild = node->left;
node->left = leftChild->right;
leftChild->right = node;
node = leftChild;
// 更新节点高度
node->right->height = max(height(node->right->left), height(node->right->right)) + 1;
node->height = max(height(node->left), height(node->right)) + 1;
}
```