0
$\begingroup$

I was trying to implement a Binary Search Tree using this article as a reference: Binary Search Tree in JavaScript.

I was thinking especially about the node insertion method. Here's my implementation:

class BinaryTree {
// ... initialization
add(val) {
    if(this.root === null) {
        this.root = new Node(val);
        return ;
    }
    this.addNode(val, this.root);
}
addNode(val, node) {
    if(!!!this.comparator) throw new Error('this.comparator cannot be undefined.');
    let comp = this.comparator(val, node.val);
    if(comp === -1) {
        if(node.left === null) {
            node.left = new Node(val);
            return ;
        }
        this.addNode(val, node.left);
    }
    else if(comp === 1) {
        if(node.right === null) {
            node.right = new Node(val);
            return ;
        }
        this.addNode(val, node.right);
    }
}
// ... other methods
}

where this.comparator = (v1, v2) => { return (v1 <= v2) ? -1 : 1; };

My questions are:

  • Is there a way to modify this add method such that it can balance the tree after every addition?
  • If so, by factor would the time complexity of add be growing?
$\endgroup$
0
$\begingroup$

Search & read on AVL trees that follow the BST rules while keeping a worstcase balance difference of 1 between subtrees. read knuth sorting & searching

$\endgroup$
  • $\begingroup$ I will definitely look into it. $\endgroup$ – Abrar Hossain May 16 '18 at 11:34
  • $\begingroup$ I may think of mapping a linear insertion algorithm that keeps OATs optimal to the case where all weights r equal, but since u didn't learn about AVL trees yet this may be difficult and probably beyond the scope of the course u r in now $\endgroup$ – Dr Shymaa Arafat May 16 '18 at 13:02
  • $\begingroup$ By linear insertion, do you mean something similar to this: const mid = 50; tree.add(50); // root for(let i=0; i<mid; i++) tree.add(i); for(let i=mid+1; i<101; i++) tree.add(i);? $\endgroup$ – Abrar Hossain May 16 '18 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.