Linear time Cartesian tree data structure construction
MIT License
Constructs a Cartesian tree for an array in linear time.
var createCartesianTree = require("cartesian-tree")
var util = require("util")
var array = [9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5]
var tree = createCartesianTree(array)
console.log(util.inspect(tree.root, {depth: 10}))
Output:
{ value: 1,
index: 3,
left:
{ value: 3,
index: 1,
left: { value: 9, index: 0 },
right: { value: 7, index: 2 } },
right:
{ value: 5,
index: 10,
left:
{ value: 8,
index: 4,
right:
{ value: 10,
index: 6,
left: { value: 12, index: 5 },
right:
{ value: 15,
index: 8,
left: { value: 20, index: 7 },
right: { value: 18, index: 9 } } } } } }
npm install cartesian-tree
require("cartesian-tree")(array[,compare])
Creates a Cartesian tree from the given array
array
is a JavaScript arraycompare
is an optional comparison function for ranking the elements in the treeReturns An object containing two properties:
root
which is the root node of the Cartesian treenodes
which is an array of length array.length
where the i
th entry corresponds the Cartesian tree node associated to the i
th entry in array
Each node in the tree has the following properties:
value
which is the value of the nodeindex
which is its occurence in array
left
which is a reference to the left childright
which is a reference to the right child(c) 2014 Mikola Lysenko. MIT License