NaN Producing Misery

    inorder-tree-layout

    1.0.0 • Public • Published

    inorder-tree-layout

    Operations on nodes for balanced binary trees stored in in-order layout. These are useful if you are building data structures, like binary search trees, implicitly (ie not storing pointers to subtrees).

    Install

    npm install inorder-tree-layout
    

    Example

    Suppose we have a tree with 10 elements, packed in level order. Then the inorder labelling of this tree looks like the following picture:

    The tree:
    
              6
            /   \
           3     8
          / \   / \
         1   5 7   9
        / \  |
       0   2 4
    
    

    Now given this tree, here is how we can compute some queries using this library:

    var layout = require("inorder-tree-layout")
     
    console.log(layout.left(10, 3))     //Prints:  1
     
    console.log(layout.parent(10, 7))   //Prints:  8
     
    console.log(layout.height(10, 9))   //Prints:  0
     

    API

    var layout = require("inorder-tree-layout")

    Conventions:

    • n is always the size of the tree
    • x is the index of a node in the tree

    layout.root(n)

    Returns the index of the root of a tree of size n.

    layout.begin(n)

    Returns the index of the first node of the tree

    layout.end(n)

    Returns the index of the last node in the tree

    layout.height(n, x)

    Returns the height of node x in a tree of size n

    layout.prev(n, x)

    Returns the predecessor of x in an in-order traversal

    layout.next(n, x)

    Returns the successor of x in an in-order traversal

    layout.parent(n, x)

    Returns the parent of x in a tree of size n

    layout.left(n, x)

    Returns the left child of x

    layout.right(n, x)

    Returns the right child of x

    layout.leaf(n, x)

    Returns true if x is a leaf node.

    layout.lo(n, x)

    Returns the left most ancestor of x in the tree

    layout.hi(n, x)

    Returns the right most ancestor of x in the tree

    Credits

    (c) 2013 Mikola Lysenko. MIT License

    Install

    npm i inorder-tree-layout

    DownloadsWeekly Downloads

    1,039

    Version

    1.0.0

    License

    MIT

    Last publish

    Collaborators

    • mikolalysenko