二叉搜索树迭代插入

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 二叉搜索树迭代插入算法
  2. BST 迭代插入图解
  3. 二叉搜索树插入的迭代实现
  4. 二叉搜索树插入迭代算法的复杂度
二叉搜索树迭代插入

在上一篇文章二叉搜索树中,我们讨论了在 BST 中插入节点的递归方法。在这篇文章中,我们将讨论在 BST 中插入一个节点的迭代方法。它比递归方法更好,因为迭代插入算法不需要额外的空间。

二叉搜索树迭代插入算法

假设 root 是 BST 的根节点,key 是我们要插入的元素。

  • 创建要插入的节点-toinsert
  • 初始化两个指针,curr 指向 rootprev 指向 null。(curr 遍历树,prev 保持其踪迹)。
  • curr !=NULL 时,执行以下操作。
    • 更新 prevcurr,以保持其踪迹。
    • 如果 curr->data > key,设置 currcurr->left,丢弃右侧子树。
    • 如果 curr->data < key,设置 currcurr->right,丢弃左侧子树。
  • 如果 prev == NULL,说明树是空的。创建 root 节点。
  • 否则如果 prev->data>key,则在 prev 的左边插入 toinsertprev->left=toinsert
  • 否则如果 prev->data<key,则在 prev 的右边插入 toinsertprev->right=toinsert

BST 迭代插入图解

BST 迭代插入插图

  • 首先,我们通过创建一个 root 节点来初始化 BST,并在其中插入 5
  • 35 小,所以被插入 5 的左边。
  • 45 小,但比 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),因为不需要额外的空间。

Harshit Jindal avatar Harshit Jindal avatar

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

相关文章 - Data Structure

相关文章 - Binary Tree

相关文章 - Binary Search Tree