arrays - 【求一些提示】将排序后的数组插入到构造的BST中

Question

我有一个作业问题要提出一个有效的算法，将具有 m 个元素的排序数组插入到具有 n 个元素的（n 个不平衡）二叉搜索树中，这样总运行时间是 O(m+n) 而不是 m*O (n)。由于我苦苦挣扎了很长时间，但仍然没有明确的解决问题的方向，我写这篇文章是想问是否可以给出可能的提示。

标签： arraysalgorithminsertruntimebinary-search-tree

Answer 1

您可以使用以下算法：

1. 对 BST 中的节点进行中序遍历，并保留对在此遍历中访问的前一个节点的引用。这个前一个节点以空值开始。保持以下不变量：要么当前节点没有左孩子，然后前一个节点为空或祖先，要么当前节点有左孩子，前一个节点是后代。

2. 当排序数组中的下一个值小于当前节点时，则为该数组值插入一个新节点作为当前节点的左孩子（当它没有左孩子时）或作为前一个节点的右孩子（当当前节点有左孩子时）。使新创建的节点成为“上一个”节点。递增数组中的索引，并重复此步骤，直到排序后的数组中的下一个值不小于当前节点。

3. 从中序遍历中获取下一对（前一个，当前）并重复步骤 2，直到中序遍历完成或所有数组值都已插入

4. 如果仍有数组值，则将它们附加到中序遍历中找到的最后一个节点的右侧，始终向右加深...

这是 JavaScript 中的一个实现：

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
    add(val) {
        if (val < this.val) {
            if (!this.left) this.left = new Node(val);
            else this.left.add(val);
        } else {
            if (!this.right) this.right = new Node(val);
            else this.right.add(val);
        }
    }
    * inorder() {  // recursive
        if (this.left) yield * this.left.inorder();
        yield this;
        if (this.right) yield * this.right.inorder();
    }
    addSorted(arr) {
        let i = 0; // index in arr
        let prev = null; // follows behind node
        for (let node of this.inorder()) {
            while (arr[i] < node.val) {
                if (!node.left) prev = node.left = new Node(arr[i++]); 
                else prev = prev.right = new Node(arr[i++]);
                if (i >= arr.length) return;
            }
            prev = node;
        }
        while (i < arr.length) {
            prev = prev.right = new Node(arr[i++]);
        }
    }
}

// Demo
// Initialise tree and print the inorder traversal
let root = new Node(40);
for (let i of [30, 70, 20, 35, 60, 80, 5, 55]) root.add(i);
for (let node of root.inorder()) console.log(node.val);

// Apply the algorithm for adding a sorted list of values
root.addSorted([1, 2, 8, 22, 38, 39, 43, 50, 51, 59, 72, 100]);
console.log("after having added sorted array:");
for (let node of root.inorder()) console.log(node.val);