c++平衡树 有什么算法实现
时间: 2024-05-24 08:14:35 浏览: 15
C 平衡树是一种自平衡的二叉搜索树,它可以在插入或删除节点时自动调整树的结构,以保证树的高度始终保持在 O(log n) 的范围内,从而保证了树的查找、插入和删除操作的时间复杂度均为 O(log n)。
常用的 C 平衡树算法实现包括红黑树、AVL 树等,其中红黑树较为常用,其实现比较简单,运行效率较高,并且广泛应用于各种编程语言和操作系统的内核中。红黑树的基本思想是,在每个节点上增加一个存储位来表示节点的颜色,并通过规定节点的颜色,使任何一条从根到叶子节点或空子节点的路径上具有一定的特性,这样就可以保证树的平衡性。红黑树的插入和删除操作通常需要进行颜色翻转、旋转等操作,但这些操作都能在 O(log n) 的时间内完成,因此红黑树可以实现快速的查找、插入和删除操作。
相关问题
用C++实现(平衡)二叉排序树的各种算法
以下是使用C++实现平衡二叉排序树AVL树的各种算法:
```cpp
#include <iostream>
using namespace std;
// AVL树节点定义
struct Node {
int val; // 节点值
int height; // 节点高度
Node* left; // 左子节点指针
Node* right; // 右子节点指针
Node(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
};
// 获取节点高度
int getHeight(Node* node) {
return node ? node->height : 0;
}
// 获取节点平衡因子
int getBalanceFactor(Node* node) {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
}
// 更新节点高度
void updateHeight(Node* node) {
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
}
// 左旋
void leftRotate(Node*& node) {
Node* temp = node->right;
node->right = temp->left;
temp->left = node;
updateHeight(node);
updateHeight(temp);
node = temp;
}
// 右旋
void rightRotate(Node*& node) {
Node* temp = node->left;
node->left = temp->right;
temp->right = node;
updateHeight(node);
updateHeight(temp);
node = temp;
}
// 平衡操作
void balance(Node*& node) {
int bf = getBalanceFactor(node);
if (bf > 1) {
int lbf = getBalanceFactor(node->left);
if (lbf >= 0) {
rightRotate(node);
} else {
leftRotate(node->left);
rightRotate(node);
}
} else if (bf < -1) {
int rbf = getBalanceFactor(node->right);
if (rbf <= 0) {
leftRotate(node);
} else {
rightRotate(node->right);
leftRotate(node);
}
}
}
// AVL树插入操作
void insert(Node*& node, int val) {
if (!node) {
node = new Node(val);
return;
}
if (val < node->val) {
insert(node->left, val);
} else if (val > node->val) {
insert(node->right, val);
} else {
return;
}
updateHeight(node);
balance(node);
}
// AVL树删除操作
void remove(Node*& node, int val) {
if (!node) {
return;
}
if (val < node->val) {
remove(node->left, val);
} else if (val > node->val) {
remove(node->right, val);
} else {
if (node->left && node->right) {
Node* temp = node->right;
while (temp->left) {
temp = temp->left;
}
node->val = temp->val;
remove(node->right, temp->val);
} else {
Node* temp = node;
if (node->left) {
node = node->left;
} else if (node->right) {
node = node->right;
} else {
node = nullptr;
}
delete temp;
}
}
if (!node) {
return;
}
updateHeight(node);
balance(node);
}
// 中序遍历
void inorderTraversal(Node* node) {
if (!node) {
return;
}
inorderTraversal(node->left);
cout << node->val << " ";
inorderTraversal(node->right);
}
// AVL树测试
int main() {
Node* root = nullptr;
insert(root, 5);
insert(root, 3);
insert(root, 7);
insert(root, 2);
insert(root, 4);
insert(root, 6);
insert(root, 8);
inorderTraversal(root);
cout << endl;
remove(root, 5);
inorderTraversal(root);
cout << endl;
return 0;
}
```
以上代码演示了AVL树的插入、删除、中序遍历操作,其他平衡二叉排序树算法的实现方式类似,只需根据平衡条件和平衡操作进行相应的修改。
用c++写一下判断二叉树是不是二叉平衡树的算法
二叉平衡树是一种特殊的二叉搜索树,其每个节点的左右子树高度差不超过1。因此,判断一棵二叉树是否为平衡树,需要计算每个节点的左右子树高度差并递归判断。
以下是用C++实现的算法:
```c++
// 定义二叉树节点
struct TreeNode {
TreeNode* left;
TreeNode* right;
int val;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 计算节点高度
int getHeight(TreeNode* node) {
if (node == nullptr) {
return 0;
}
return max(getHeight(node->left), getHeight(node->right)) + 1;
}
// 判断是否为平衡树
bool isBalanced(TreeNode* root) {
if (root == nullptr) {
return true;
}
// 计算左右子树高度差
int diff = abs(getHeight(root->left) - getHeight(root->right));
if (diff > 1) {
return false;
}
// 递归判断左右子树是否为平衡树
return isBalanced(root->left) && isBalanced(root->right);
}
```
该算法时间复杂度为O(nlogn),其中n为二叉树节点数。可以通过遍历每个节点计算其高度,并递归判断其子树是否平衡来实现。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)