javascript_trees_with_es6_classes_inheritance.js

/*
 *  Binary Tree
 *  Binary Search Tree
 *  AVL Tree
 *
 *  All in pure Javascript, ES6 classes and with inheritance.
 */


/*
 * The goal of this file is to experiment with, and to showcase OOPs
 * with ES6
 *
 * Starting with implementing a simple binary tree, we move on to a binary
 * search tree (which inherits from the original binary tree); Later an AVL
 * tree, which inherits from the binary-search-tree is added.
 *
 * NOTE: only 'insertion' is implemented; and the traversal is a very
 * simplistic inorder traversal
 */


/*
 * A simple binary tree class.
 *
 * As for 'insertion', a random side is chosen to go to
 *
 * Also, note that the insert method returns a tree. It is designed so, to
 * make sure that in future versions, the tree might re-arrange itself, and
 * the root being returned might be different. So, an insert might be capable
 * of changing the tree (at least from an external perspective). Hence, the
 * insert syntax will be `tree = tree.insert(value)`
 *
 * Another point to note is the `selfClone` which returns a base version of
 * the same type. This is what will be overridden by the derived classes
 */

class BinaryTree {
    constructor(value) {
        this.data = value;
        this.left = undefined;
        this.right = undefined;
    }

    leftOrRight(nodeValue, newValue) {
        return Math.random() > 0.5 ? 'left' : 'right';
    }

    selfClone(value) {
        return new BinaryTree(value);
    }

    // NOTE: see the remark above the class definition to see why insert
    // returns a tree.
    insert(value) {
        if (this.data === undefined) {
            this.data = value;
            return this;
        }

        const direction = this.leftOrRight(this.data, value);

        if (direction === 'left') {
            if (this.left === undefined) {
                this.left = this.selfClone(value);
            } else {
                this.left = this.left.insert(value);
            }
            return this;
        }

        if (this.right === undefined) {
            this.right = this.selfClone(value);
        } else {
            this.right = this.right.insert(value);
        }
        return this;
    }

    toString() {
        if (this.data === undefined) {
            return '"null"';
        }

        const lhs = this.left ? this.left.toString() : '';
        const rhs = this.right ? this.right.toString() : '';
        return [ lhs, this.data, rhs ].map(String).filter(Boolean).join(', ');
    }

    height() {
        return Math.max(this.lHeight(), this.rHeight()) + 1;
    }

    lHeight() {
        return this.left ? this.left.height() : 0;
    }

    rHeight() {
        return this.right ? this.right.height() : 0;
    }

    /*
     * TODO -- level print.
     * For pseudocode, see:
     * https://github.com/sillyfellow/ds_in_ruby/blob/master/trees.rb#L62
     * (well, code in Ruby)
     *------------ (ss@03/18/2018) */
}

/*
 * Only the choice of left/right is the only distinguishing feature of a BST
 * from a binary tree.
 *
 * And, obviously, a selfClone will have to return a BST
 */
class BinarySearchTree extends BinaryTree {
    leftOrRight(nodeValue, newValue) {
        return nodeValue > newValue ? 'left' : 'right';
    }

    selfClone(value) {
        return new BinarySearchTree(value);
    }
}


/*
 * We need a balancing act.
 *
 * For that, see the overridden insert: We use super.insert() for the actual
 * insert, and then balance the updated tree, and return it.  Nothing fancy,
 * but easy to overlook
 */
class AVLTree extends BinarySearchTree {
    selfClone(value) {
        return new AVLTree(value);
    }

    imbalance() {
        return this.lHeight() - this.rHeight();
    }

    rlRotate() {
        this.left = this.left.rRotate();
        return this.lRotate();
    }

    lrRotate() {
        this.right = this.right.lRotate();
        return this.rRotate();
    }

    lRotate() {
        if (!this.left) {
            return this;
        }

        const pullUp = this.left;

        this.left = pullUp.right;
        pullUp.right = this;
        return pullUp;
    }

    rRotate() {
        if (!this.right) {
            return this;
        }
        const pullUp = this.right;

        this.right = pullUp.left;
        pullUp.left = this;
        return pullUp;
    }

    balance() {
        const diff = this.imbalance();
        if (Math.abs(diff) < 2) {
            return this;
        }

        if (diff < 0) {
            if (this.right.imbalance() === 1) {
                return this.lrRotate();
            }

            return this.rRotate();
        }

        if (this.left.imbalance() === -1) {
            return this.rlRotate();
        }
        return this.lRotate();
    }

    // NOTE: See the remark above the class definition
    insert(value) {
        return super.insert(value).balance();
    }
}


// Binary Tree test  -- (ss@03/18/2018) --
const bTree = new BinaryTree(0).insert(1).insert(2).insert(3).insert(4)
    .insert(11).insert(12).insert(13).insert(14).insert(15).insert(16)
    .insert(5).insert(6).insert(7).insert(8).insert(9).insert(10);
console.log(bTree.height()); // will mostly be 5, or close enough -- 5 levels
console.log(bTree.toString()); // something like: 16, 15, 3, 1, 13, 9, 11, 7, 0, 12, 5, 2, 6, 14, 4, 10, 8

// Binary Search Tree test  -- (ss@03/18/2018) --
const bstree = new BinarySearchTree(0).insert(1).insert(2).insert(3).insert(4)
    .insert(11).insert(12).insert(13).insert(14).insert(15).insert(16)
    .insert(5).insert(6).insert(7).insert(8).insert(9).insert(10);
console.log(bstree.height()); // will be 12 levels
console.log(bstree.toString()); // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

// AVL Tree test  -- (ss@03/18/2018) --
const avltree = new AVLTree(0).insert(1).insert(2).insert(3).insert(4)
    .insert(11).insert(12).insert(13).insert(14).insert(15).insert(16)
    .insert(5).insert(6).insert(7).insert(8).insert(9).insert(10);
console.log(avltree.height()); // always 5 levels
console.log(avltree.toString()); // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16