Class IntervalTree

constructor

• new IntervalTree(): IntervalTree

• Returns IntervalTree

nilNode

root

items

• get items(): any[]

• Returns array of items (<key,value> pairs) in the ascended keys order

  Returns any[]

keys

• get keys(): any[]

• Returns array of sorted keys in the ascending order

  Returns any[]

size

• get size(): number

• Returns number of items stored in the interval tree

  Returns number

values

• get values(): any[]

• Return array of values in the ascending keys order

  Returns any[]

clear

• clear(): void

• Clear tree

  Returns void

exist

• exist(key, value?): boolean

• Returns true if item {key,value} exist in the tree

  Parameters

  • key: any

    interval correspondent to keys stored in the tree
  • value: any = key

    value object to be checked

  Returns boolean

  true if item {key, value} exist in the tree, false otherwise

forEach

• forEach(visitor): void

• Tree visitor. For each node implement a callback function.
  Method calls a callback function with two parameters (key, value)

  Parameters

  • visitor: ((key: any, value: any) => {})

    function to be called for each tree item

    • • (key, value): {}

      • Parameters

        • key: any
        • value: any

        Returns {}

  Returns void

insert

• insert(key, value?): null | Node

• Insert new item into interval tree

  Parameters

  • key: [number, number] | Interval

    interval object or array of two numbers [low, high]
  • value: any = key

    value representing any object (optional)

  Returns null | Node

  returns reference to inserted node as an object {key:NumberInterval, value: value}

intersectAny

• intersectAny(interval): boolean

• Returns true if intersection between given and any interval stored in the tree found

  Parameters

  • interval: any

    search interval or tuple [low, high]

  Returns boolean

isEmpty

• isEmpty(): boolean

• Returns true if tree is empty

  Returns boolean

leftRotate

• leftRotate(x): void

• Left rotate subtree around given node. exchange x.right and x, and take x.right.left as x.right

  Parameters

  • x: Node

  Returns void

map

• map(callback): IntervalTree

• Value Mapper. Walk through every node and map node value to another value

  Parameters

  • callback: ((value: any, key: any) => {})

    function to be called for each tree item

    • • (value, key): {}

      • Parameters

        • value: any
        • key: any

        Returns {}

  Returns IntervalTree

recalcMax

• recalcMax(node): void

• Calculate max property for all nodes in the path from given node to the root

  Parameters

  • node: Node

  Returns void

remove

• remove(key, value?): null | Node

• Remove entry {key, value} from the tree

  Parameters

  • key: any

    interval correspondent to keys stored in the tree
  • value: any = key

    value object

  Returns null | Node

  deleted node or null if node not found

rightRotate

• rightRotate(y): void

• Right rotate subtree around given node.

  Parameters

  • y: Node

  Returns void

search

• search(interval, outputMapperFn?): any[]

• Returns array of entry values which keys intersect with given interval
  If no values stored in the tree, returns array of keys which intersect given interval

  Parameters

  • interval: any

    search interval, or tuple [low, high]
  • outputMapperFn: ((value: any, key: any) => any) = ...

    optional function that maps (value, key) to custom output

    • • (value, key): any

      • Parameters

        • value: any
        • key: any

        Returns any

  Returns any[]

testBlackHeightProperty

• testBlackHeightProperty(node): number

• Throw error if not every path from root to bottom has same black height

  Parameters

  • node: Node

  Returns number

testRedBlackProperty

• testRedBlackProperty(): boolean

• Return true if all red nodes have exactly two black child nodes

  Returns boolean

transplant

• transplant(u, v): void

• Transplant subtree v in place of subtree u. replace u.parent.left or u.parent.right with v

  Parameters

  • u: Node
  • v: Node

  Returns void

treeDelete

• treeDelete(deleteNode): void

• Delete node from the tree, and fixup tree properties

  Parameters

  • deleteNode: Node

  Returns void

treeDeleteFixup

• treeDeleteFixup(fixupNode): void

• Recolor nodes and perform rotations to preserve red-black tree properties after delete.

  Parameters

  • fixupNode: Node

  Returns void

treeFindAnyInterval

• treeFindAnyInterval(root, searchNode): boolean

• Returns true if intersection between given and any interval stored in the tree found

  Parameters

  • root: null | Node
  • searchNode: Node

  Returns boolean

treeInsert

• treeInsert(insertNode): void

• Insert new node into the tree.

  Parameters

  • insertNode: Node

  Returns void

treeInsertFixup

• treeInsertFixup(insertNode): void

• Recolor nodes and perform rotations to preserve red-black tree properties after insert.

  Parameters

  • insertNode: Node

  Returns void

treeMinimum

• treeMinimum(currentNode): Node

• Return node with minimal key in the subtree

  Parameters

  • currentNode: null | Node

  Returns Node

treeSearch

• treeSearch(root, searchNode): null | Node

• Tree search. Returns node if found, null otherwise

  Parameters

  • root: null | Node
  • searchNode: Node

  Returns null | Node

treeSearchInterval

• treeSearchInterval(node, searchNode, respNodes): void

• Tree search for interval intersection. save all intersection nodes found as array in respNodes.

  Parameters

  • node: null | Node
  • searchNode: Node
  • respNodes: Node[]

  Returns void

treeSuccessor

• treeSuccessor(currentNode): null | Node

• Return successor of the given node.

  Parameters

  • currentNode: Node

  Returns null | Node

treeWalk

• treeWalk(root, callback): void

• Walk through the tree and call callback function for each node

  Parameters

  • root: null | Node
  • callback: Function

  Returns void