binary search tree c++
时间: 2023-05-02 20:06:17 浏览: 79
二叉搜索树(Binary Search Tree)是一种常用的数据结构之一,是一种有序的树形结构。它的每个节点都有一个键值,且每个节点的键值大于其左子树的所有节点的键值,小于其右子树的所有节点的键值。它可以用来实现集合、映射等抽象数据类型。
对于二叉搜索树,最常见的操作是插入和查找。插入操作比较简单,首先将新节点插入到树的叶子节点上,然后利用上述的键值大小关系进行调整。查找操作也很方便,只需要从树的根节点开始,递归地与左右子树比较键值大小即可。
二叉搜索树的时间复杂度与树的高度有关,一般在理想情况下,树的高度为 O(log n)。但如果二叉搜索树不平衡,所有节点都在一条从根节点向左或向右的路径上,时间复杂度就会变为 O(n)。
为了保持二叉搜索树的平衡性,有很多优化的方法,如 AVL 树、红黑树、Treap 等,这些方法可以通过对树的旋转、颜色变换等方式来保持树的平衡,从而提升查找效率。
相关问题
Projects 1. Convert a binary search tree into a sorted circular doubly linked list 【Problem Description】 Given a binary search tree, you need to convert it into a circular doubly linked list, the elements in the linked list are sorted. For example, a binary search tree in Fig.1 is converted into a sorted circular doubly linked list in Fig.2. 【Basic Requirements】 The input data is a set of data elements to build a binary search tree, you should design algorithms to realize the conversion process and verify the accuracy of your code on multiple test data. The output includes the following: (1) Print the binary search tree (2) Traverse the binary search tree (3) Print the converted doubly linked list (4) Output all elements of the doubly linked list in positive and reverse order
【Solution】
Here is a C++ implementation of the solution to the problem:
```cpp
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* treeToDoublyList(TreeNode* root) {
if (!root) {
return NULL;
}
stack<TreeNode*> s;
TreeNode* p = root;
TreeNode* pre = NULL;
TreeNode* head = NULL;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top();
s.pop();
if (pre) {
pre->right = p;
p->left = pre;
} else {
head = p;
}
pre = p;
p = p->right;
}
head->left = pre;
pre->right = head;
return head;
}
};
void printBST(TreeNode* root) {
if (root) {
printBST(root->left);
cout << root->val << " ";
printBST(root->right);
}
}
void printList(TreeNode* head) {
TreeNode* p = head;
do {
cout << p->val << " ";
p = p->right;
} while (p != head);
cout << endl;
}
void printListReverse(TreeNode* head) {
TreeNode* p = head->left;
do {
cout << p->val << " ";
p = p->left;
} while (p != head->left);
cout << endl;
}
int main() {
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(5);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
Solution s;
TreeNode* head = s.treeToDoublyList(root);
cout << "Binary Search Tree: ";
printBST(root);
cout << endl;
cout << "Doubly Linked List: ";
printList(head);
cout << "Doubly Linked List in Reverse Order: ";
printListReverse(head);
return 0;
}
```
【Explanation】
To convert a binary search tree into a sorted circular doubly linked list, we can use a stack to perform an inorder traversal of the binary search tree. During the traversal, we maintain a pointer to the previous node visited and link the current node to the previous node. After the traversal, we link the head and tail of the linked list to form a circular doubly linked list. Finally, we can print the binary search tree, traverse the doubly linked list, and output all elements in positive and reverse order.
【Example】
Input:
```
4
/ \
2 5
/ \
1 3
```
Output:
```
Binary Search Tree: 1 2 3 4 5
Doubly Linked List: 1 2 3 4 5
Doubly Linked List in Reverse Order: 5 4 3 2 1
```
C++insert时间复杂度
C中插入操作的时间复杂度取决于数据结构的不同。以下是常见数据结构中插入操作的时间复杂度:
1. 数组(Array):在数组的末尾插入元素的时间复杂度为O(1),在其他位置插入元素则需要将位置之后的元素依次向后移动,时间复杂度为O(n)。
2. 链表(Linked List):在链表的开头插入元素的时间复杂度为O(1),在其他位置插入元素需要先遍历找到插入位置,然后修改指针指向,时间复杂度为O(n)。
3. 栈(Stack):栈只能在栈顶进行插入操作,因此插入元素的时间复杂度为O(1)。
4. 队列(Queue):队列只能在队尾进行插入操作,因此插入元素的时间复杂度为O(1)。
5. 哈希表(Hash Table):插入元素的时间复杂度取决于哈希函数的效率,通常情况下平均插入时间复杂度为O(1)。
6. 二叉搜索树(Binary Search Tree):在平衡二叉搜索树中插入操作的时间复杂度为O(log n),但如果树不平衡,最坏情况下插入的时间复杂度可达到O(n)。
7. 堆(Heap):在堆中插入元素的时间复杂度为O(log n)。