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

user_10983643 0
Viewed 60

I want to create an AVL tree with the nodes' keys being numbers from 0 to k in O(k) time. I know it is possible to create a regular search tree with the same condition in O(k), but I have no idea how to do that with an AVL tree.

Thanks!

avl-tree tree data-structures time-complexity algorithm
1 Answers

An idea could be to first determine what the shape of the tree will be for a given argument. We could go for a so-called complete tree, sometimes also called "nearly complete". This uniquely defines the shape for a given number of nodes.

We can calculate which is the height of that tree, and what will be the value stored in the rightmost leaf on the bottom level of that tree. With a bit of fiddling it is not so hard to derive the formulas for both these values.

With that information you can build the tree recursively, using an inorder traversal as the tree is being built, where each next node will have the next sequential value.

In an AVL tree you'll want to store the balance factor (-1, 0, or 1). In this tree, most nodes will have balance 0, except for some nodes on the path from the root to the rightmost leaf on the bottom level: some of these will be left-heavy and have a balance factor of -1. These can be identified after the tree has been built, by performing a binary search from the root.

Here is an interactive implementation in 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>

user_54598390
Related