Index calculations for balanced binary search trees in in-order layout
JavaScript
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
test
.gitignore
LICENSE
README.md
inorder.js
package.json

README.md

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