有没有办法在 O(k) 中创建一个有 k 个节点的空 avl_tree？

Question

我想创建一棵 AVL 树，节点的键是 O(k) 时间内从 0 到 k 的数字。我知道可以在 O(k) 中创建具有相同条件的常规搜索树，但我不知道如何使用 AVL 树来做到这一点。

谢谢！

Answer 1

一个想法可能是首先确定给定参数的树的形状。我们可以选择所谓的 complete tree，有时也称为“接近完成”。这唯一地定义了给定数量的节点的形状。

我们可以计算出那棵树的高度是多少，以及那棵树最底层最右边的叶子中存储的值是多少。稍加改动，就可以很容易地推导出这两个值的公式。

利用这些信息，您可以递归地构建树，在构建树时使用中序遍历，其中每个下一个节点将具有下一个顺序值。

在 AVL 树中，您需要存储平衡因子（-1、0 或 1）。在这棵树中，大多数节点的平衡为 0，除了从根到底层最右边叶子的路径上的一些节点：其中一些节点是左重的，平衡因子为 -1。这些可以在构建树后通过从根执行二进制搜索来识别。

这是JavaScript中的交互式实现：

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.balance = 0;
    }
    // Function to create a string representation of the subtree rooted at this node
    toString() {
        let text = "";
        if (this.right) {
            let lines = this.right.toString().split(/\n/);
            let mid = lines.findIndex(line => line[0] != " ");
            text = lines.map((line, i) => 
                i < mid ? "   " + line
                : i > mid ? " │ " + line
                : " ┌─" + line
            ).join("\n") + "\n";
        }
        text += "(" + this.value + ") " + (this.balance || "");
        if (this.left) {
            let lines = this.left.toString().split(/\n/);
            let mid = lines.findIndex(line => line[0] != " ");
            text += "\n" + lines.map((line, i) => 
                i < mid ? " │ " + line
                : i > mid ? "   " + line
                : " └─" + line
            ).join("\n");
        }
        return text;
    }
}

function createBalanced(k) {
    // Determine the height of the target tree
    let height = Math.floor(Math.log2(k + 1));
    // Determine the value that the right most node on the bottom level will have
    let lastBottom = (k + 1 - 2**height) * 2;    
    // The value which the next generated node will get
    let value = 0;
    
    // Recursive function for inorder generation of tree nodes
    function recur(depth) {
        if (depth > height) return null;
        let left = recur(depth + 1);
        // Check whether we are about to generate the last node at the bottom level
        if (value == lastBottom) height--; // This happens at the most once.
        let node = new Node(value);
        value++; // non-local variable!
        node.left = left;
        node.right = recur(depth + 1);
        return node;
    }
    
    let root = recur(0);
    // Identify the nodes that have a non-zero balance
    let node = root;
    while (node.value != lastBottom) {
        if (lastBottom < node.value) {
            node.balance = -1;
            node = node.left;
        } else {
            node = node.right;
        }
    }
    return root;
}

// I/O management in this snippet

function refresh() {
    let k = +input.value;
    if (k >= 0 && k <= 126) {
        let tree = createBalanced(k);
        output.textContent = tree.toString();
    } else {
        output.textContent = "Please enter a value between 0 and 126";
    }
}

let input = document.querySelector("input");
let output = document.querySelector("pre");
input.addEventListener("input", refresh);
refresh();

k: <input type="number" size="4" value="12" min="0" max="126"><br>
Tree (turned 90°). The balance is printed after the node when it is non-zero:
<pre></pre>

有没有办法在 O(k) 中创建一个有 k 个节点的空 avl_tree？

is there a way to create an empty avl_tree with k nodes in O(k)?

algorithm

data-structures

tree

time-complexity

avl-tree