平衡二叉树删除节点代码
时间: 2023-03-28 07:04:58 浏览: 66
以下是平衡二叉树删除节点的代码:
```
struct Node {
int val, height;
Node *left, *right;
Node(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
};
int getHeight(Node *node) {
return node ? node->height : ;
}
int getBalanceFactor(Node *node) {
return node ? getHeight(node->left) - getHeight(node->right) : ;
}
void updateHeight(Node *node) {
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
}
Node* leftRotate(Node *node) {
Node *newRoot = node->right;
node->right = newRoot->left;
newRoot->left = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
Node* rightRotate(Node *node) {
Node *newRoot = node->left;
node->left = newRoot->right;
newRoot->right = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
Node* insert(Node *root, int val) {
if (!root) {
return new Node(val);
}
if (val < root->val) {
root->left = insert(root->left, val);
} else {
root->right = insert(root->right, val);
}
updateHeight(root);
int balanceFactor = getBalanceFactor(root);
if (balanceFactor > 1 && getBalanceFactor(root->left) >= ) {
return rightRotate(root);
}
if (balanceFactor > 1 && getBalanceFactor(root->left) < ) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balanceFactor < -1 && getBalanceFactor(root->right) <= ) {
return leftRotate(root);
}
if (balanceFactor < -1 && getBalanceFactor(root->right) > ) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
Node* findMin(Node *root) {
while (root->left) {
root = root->left;
}
return root;
}
Node* remove(Node *root, int val) {
if (!root) {
return nullptr;
}
if (val < root->val) {
root->left = remove(root->left, val);
} else if (val > root->val) {
root->right = remove(root->right, val);
} else {
if (!root->left && !root->right) {
delete root;
return nullptr;
}
if (!root->left || !root->right) {
Node *temp = root->left ? root->left : root->right;
delete root;
return temp;
}
Node *temp = findMin(root->right);
root->val = temp->val;
root->right = remove(root->right, temp->val);
}
updateHeight(root);
int balanceFactor = getBalanceFactor(root);
if (balanceFactor > 1 && getBalanceFactor(root->left) >= ) {
return rightRotate(root);
}
if (balanceFactor > 1 && getBalanceFactor(root->left) < ) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balanceFactor < -1 && getBalanceFactor(root->right) <= ) {
return leftRotate(root);
}
if (balanceFactor < -1 && getBalanceFactor(root->right) > ) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
```