二叉搜索树迭代插入
Harshit Jindal
2023年1月30日
2021年2月28日
在上一篇文章二叉搜索树中，我们讨论了在 BST 中插入节点的递归方法。在这篇文章中，我们将讨论在 BST 中插入一个节点的迭代方法。它比递归方法更好，因为迭代插入算法不需要额外的空间。
二叉搜索树迭代插入算法
假设 root 是 BST 的根节点，key 是我们要插入的元素。
-
创建要插入的节点-
toinsert。 -
初始化两个指针，
curr指向root，prev指向 null。(curr遍历树，prev保持其踪迹)。 -
当
curr!=NULL时，执行以下操作。- 更新
prev为curr，以保持其踪迹。 - 如果
curr->data>key，设置curr为curr->left，丢弃右侧子树。 - 如果
curr->data<key，设置curr为curr->right，丢弃左侧子树。
- 更新
-
如果
prev==NULL，说明树是空的。创建root节点。 -
否则如果
prev->data>key，则在prev的左边插入toinsert，prev->left=toinsert。 -
否则如果
prev->data<key，则在prev的右边插入toinsert，prev->right=toinsert。
BST 迭代插入图解
-
首先，我们通过创建一个
root节点来初始化 BST，并在其中插入5。 -
3比5小，所以被插入5的左边。 -
4比5小，但比3大，所以插入3的右边，但插入4的左边。 -
2是当前树中最小的元素，所以它被插入到最左边的位置。 -
1是当前树中最小的元素，所以它被插入到最左边的位置。 -
6是当前树中最大的元素，所以它被插入到最右边的位置。
这就是我们在 BST 内部插入元素的方法。
二叉搜索树插入的迭代实现
#include <iostream>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node *newNode(int item) {
Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inorder(Node *root) {
if (root != NULL) {
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
}
void insert(Node* &root, int key)
{
Node* toinsert = newNode(key);
Node* curr = root;
Node* prev = NULL;
while (curr != NULL) {
prev = curr;
if (key < curr->key)
curr = curr->left;
else
curr = curr->right;
}
if (prev == NULL) {
prev = toinsert;
root = prev;
}
else if (key < prev->key)
prev->left = toinsert;
else
prev->right = toinsert;
}
int main() {
Node *root = NULL;
insert(root, 5);
insert(root, 3);
insert(root, 8);
insert(root, 6);
insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 7);
inorder(root);
}
二叉搜索树插入迭代算法的复杂度
时间复杂度
- 平均情况
在平均情况下，在 BST 中插入一个节点的时间复杂度与二叉搜索树的高度相当。平均来说，一个 BST 的高度是 O(logn)。当形成的 BST 是一个平衡的 BST 时，就会出现这种情况。因此，时间复杂度是 [Big Theta]：O(logn)。
- 最佳情况
最好的情况是，该树是一个平衡的 BST。最佳情况下，插入的时间复杂度为 O(logn)。它与平均情况下的时间复杂度相同。
- 最坏情况
在最坏的情况下，我们可能要从根节点遍历到最深的叶子节点，即树的整个高度 h。如果树是不平衡的，即它是倾斜的，树的高度可能会变成 n，因此插入和搜索操作的最坏情况下的时间复杂度是 O(n)。
空间复杂度
迭代插入操作的空间复杂度为 O(1)，因为不需要额外的空间。
Author: Harshit Jindal
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn