以有效的方式将排序数组中的元素插入 BST

Question

我正在为这个练习而苦苦挣扎：

Given a BST T, whose nodes contain only a key field, a left and right field and a sorted array A which contains m keys. Write an efficient algorithm which inserts into T any A's keys which are not already present in T. You must not apply the InsertBST(T,key) algorithm on single A's keys.

例如，如果 BST 包含 1,3,4,5 而 A 包含 1,2,5,6，我必须插入 2,6 而无需使用 InsertBST(T,2) 和 InsertBST(T,6)。

这是我试过的：

Algo(T,A,index)
     if T != null then
          Algo(T->sx,A,index)
          p = NewNode()
          p->key = A[index]
          if T->key > A[index] then
               T->sx = p
               index = index + 1
          else if T->key < A[index] then
               T->dx = p
               index = index + 1
          Algo(T->dx,A,index)

但是它在错误的地方插入了节点。你能帮帮我吗？

Answer 1

我发现您的尝试存在以下问题：

在每个递归调用中，您将插入一个节点。因此，例如，当您到达第一个 left-most 叶时。但这不可能是对的。第一个节点插入可能必须完全发生在树的其他地方，而根本不会影响此叶子
没有检查 index 超出范围。该代码假定要插入的值与树中的节点数一样多。
没有规定值何时等于树中现有节点的值。在那种情况下，根本不应添加该值，而应将其忽略。
在大多数语言中，index 将是 Algo 函数的局部变量，因此更新它（使用 + 1）不会影响index 调用者拥有的变量。您将需要一个 index 变量，该变量在 Algo 的所有执行中共享。在某些语言中，您可以通过引用传递 index，而在其他语言中，您可以访问更全局的变量，该变量不作为参数传递。

算法

使用的算法如下：

执行中序遍历（就像你已经做的那样）。但要跟踪先前访问过的节点。只有当您检测到要插入的下一个值介于这两个节点的值之间时，您才需要采取行动：在这种情况下，创建一个新节点并将其插入。这是检测插入位置的方法。或者：

当前节点没有左child，这也意味着前一个节点（在顺序序列中）不存在或在树上更高。在这种情况下，新节点应该成为当前节点
的左侧 child
当前节点有左child，这也意味着前一个节点在左子树中，没有自己的右child。在这种情况下，将新节点添加为前一个节点的右侧 child。

哨兵理念

有可能访问完inorder序列的最后一个节点后，还有值要插入，因为它们大于树中的最大值。您必须在递归遍历完成后单独处理这种情况，或者您可以通过向树添加一个新的临时根来开始您的算法，该树具有一个虚拟的但很大的值——大于要插入的最大值。它的左边 child 就是真正的根。使用该技巧，您可以确定上述递归逻辑将为 all 值插入节点，因为它们都将小于该临时节点的值。

在 Python

中实施

这是 Python 语法中的算法，使用了“哨兵”节点思想：

def insertsorted(root, values):
    if not values:
        return root  # Nothing to do

    # These variables are common to all recursive executions:
    i = 0  # index in values
    prev = None  # the previously visited node in inorder sequence

    def recur(node):
        nonlocal i, prev  # We allow those shared variables to be modified here
        if i < len(values) and node.left:
            recur(node.left)
        while i < len(values) and values[i] <= node.value:
            if values[i] < node.value:
                newnode = Node(values[i])
                if node.left is None:
                    node.left = newnode
                else:
                    prev.right = newnode
                prev = newnode
            i += 1
        prev = node
        if i < len(values) and node.right:
            recur(node.right)
    
    # Create a temporary node that will become the parent of the root
    # Give it a value greater than the last one in the array
    sentinel = Node(values[-1] + 1)  
    sentinel.left = root
    recur(sentinel)
    # Return the real root to the caller
    return sentinel.left

以有效的方式将排序数组中的元素插入 BST

Inserting elements from a sorted array into a BST in an efficient way

arrays

binary-search-tree

算法

哨兵理念

在 Python