Class: AVLTree

AVLTree

Extends BinarySearchTree (see src/BinarySearchTree.js) to provide a Map like functionality backed by a balanced Tree. All functionality of BinarySearchTree is available. In addition Tree is height balanced by rotation whenever an insert is done See rotate(), reBalance() and checkAVLProperty() functions for explanation. Caller doesn't need to invoke these functions, they are internally used when an insert or delete violates the AVL property of the tree. The keys are ordered based on the natural ordering or an optional compare function.

new AVLTree(compFn)

Example -

var AVLTree = require("dsjslib").AVLTree
var avl=new AVLTree(function(k1,k2){...})
Parameters:
Name Type Argument Description
compFn userCompareFn <optional>

external compare function for ordering keys
Source:

Extends

Methods

checkInvariants(node)

Validates the tree starting at given node (root otherwise) Validates BST as well as AVL properties.

Parameters:
Name Type Argument Description
node Object <optional>

Starting node, if not provided start at root
Source:

delete(key)

Delete a key value pair from the Map. Also re-balances the tree

Parameters:
Name Type Description
key *
Source:

get(key) → {Object}

Get value for a key

Parameters:
Name Type Description
key
Inherited From:
Source:
Returns:

{key:key used in query,value:value of the key }, null if key was not found

Type
Object

max() → {Object}

Find max key

Inherited From:
Source:
Returns:

{key:maximum key,value: value}

Type
Object

min() → {Object}

Find min key

Inherited From:
Source:
Returns:

{key:minimum key,value: value}

Type
Object

predecessor(key) → {Object}

Return the predecessor key value pair

Parameters:
Name Type Description
key *

key for which predecessor is needed
Inherited From:
Source:
Returns:

{key:predecessor key,value: value}

Type
Object

put(key, value) → {Object}

Insert a key value. It also re-balances the tree

Parameters:
Name Type Description
key *
value *
Source:
Returns:

A closure on the the tree. Calling put() again on this object will insert key value pair in the tree. This is to support easy chaining of put() method. tree.put(k1,v1).put(k2,v2) ...

Type
Object

successor(item) → {Object}

Return the successor key value pair

Parameters:
Name Type Description
item *

key for which successor is needed
Inherited From:
Source:
Returns:

{key:successor key,value: value}

Type
Object

traverse(node, fn)

Inorder traversal, apply provided function on each visited node

Parameters:
Name Type Argument Description
node Object <optional>

Start at root if not given
fn function

Callback function called for every node visited
Inherited From:
Source: