Index calculations for inorder layout of balanced binary trees
npm install inorder-tree-layoutinorder-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).
npm install inorder-tree-layout
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:
`javascript
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
`
`javascript`
var layout = require("inorder-tree-layout")
Conventions:
* n is always the size of the treex
* is the index of a node in the tree
in a tree of size n$3
Returns the predecessor of in an in-order traversal$3
Returns the successor of x in an in-order traversal$3
Returns the parent of x in a tree of size n$3
Returns the left child of $3
Returns the right child of $3
Returns true if is a leaf node.$3
Returns the left most ancestor of x in the tree$3
Returns the right most ancestor of x` in the tree