二叉搜索树迭代插入-ag捕鱼王app官网

当前位置：ag捕鱼王app官网 > > 算法 >

web前端编程语言网络算法操作系统数据库

二叉搜索树迭代插入

作者：迹忆客最近更新：2023/03/26 浏览次数：

在上一篇文章二叉搜索树中，我们讨论了在 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 迭代插入图解

bst 迭代插入插图

首先，我们通过创建一个 root 节点来初始化 bst，并在其中插入 5。
3 比 5 小，所以被插入 5 的左边。
4 比 5 小，但比 3 大，所以插入 3 的右边，但插入 4 的左边。
2 是当前树中最小的元素，所以它被插入到最左边的位置。
1 是当前树中最小的元素，所以它被插入到最左边的位置。
6 是当前树中最大的元素，所以它被插入到最右边的位置。

这就是我们在 bst 内部插入元素的方法。

二叉搜索树插入的迭代实现

#include 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)，因为不需要额外的空间。

上一篇：二叉搜索树

下一篇：二叉搜索树检查

转载请发邮件至 1244347461@qq.com 进行申请，经作者同意之后，转载请以链接形式注明出处

本文地址：

将二叉树转换为二叉搜索树

发布时间：2023/03/20 浏览次数：185 分类：算法

本教程教大家如何将二叉树转换为二叉搜索树。二叉树是一种非线性数据结构。它被称为二叉树，因为每个节点最多有两个子节点。这些子节点被称为左子和右子。

二叉搜索树中序后代

发布时间：2023/03/20 浏览次数：155 分类：算法

本教程介绍了如何在 bst 中查找节点的中序后代。

发布时间：2023/03/20 浏览次数：189 分类：算法

本教程介绍了二叉搜索树的删除操作。

二叉搜索树检查

发布时间：2023/03/20 浏览次数：161 分类：算法

如何检查给定的二叉树是否是二叉搜索树。