Avlbinstree
AVL self-balancing binary search trees for ES6
Description
ES6 implementation of the AVL self-balancing binary search tree data structure with TypeScript support.
Come over to Twitter to share your thoughts on the project.
Visit the contributing guidelines to learn more on how to translate this document into more languages.
Contents
Install
Yarn
yarn add avlbinstree
NPM
npm install avlbinstree
In Depth
An AVL tree is a self-balancing binary search tree data structure, whose nodes contain a unique key
, an associated value
, and point to two distinguished left
and right
sub-trees. In the tree, the heights of the two child sub-trees of any node differ by at most one. If during a mutating operation, e.g insertion, deletion, a temporary height difference of more than one arises between two child sub-trees, the balance property of the parent sub-tree, thus of the entire tree itself, is restored through the internal usage of tree rotations. These repair tools move the tree nodes only vertically
, so that the horizontal/in-order
sequence of their keys is fully preserved. Lookup, insertion, and deletion all take O(log n)
time in both the average and worst cases, where n
is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
Usage
Avlbinstree exposes a chainable API, that can be utilized through a simple and minimal syntax, allowing you to combine methods effectively.
Usage examples can be also found at the test
directory.
'use strict';
const {Tree, Node} = require('avlbinstree');
const tree = new Tree();
tree.insert(9, 'A');
tree.root;
const node = new Node(9, 'A');
tree.root.key === node.key;
tree.root.value === node.value;
tree.insert(5, 'B').insert(13, 'C').root;
tree.root.left;
tree.root.right;
tree.insert(11, 'D').insert(15, 'E');
tree.size();
tree.search(13);
tree.search(25);
tree.includes(11);
tree.includes(100);
tree.height();
tree.remove(5);
tree.root.isRightHeavy();
tree.root.isLeftHeavy();
tree.max();
tree.maxKey();
tree.maxValue();
tree.min();
tree.minKey();
tree.minValue();
tree.remove(15);
tree.root.isBalanced();
tree.keys();
tree.values();
API
tree.root
Returns the root node of the tree.
If the tree is empty null
is returned.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A');
tree.root;
tree.clear()
Mutates the tree by removing all residing nodes and returns it empty.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.size();
tree.clear();
tree.size();
tree.fullNodes()
Applies in-order traversal to the tree and stores each traversed full node (node with two non-null children) in an array.
The array is returned at the end of the traversal.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.fullNodes();
tree.height()
Returns the maximum distance of any leaf node from the root.
If the tree is empty -1
is returned.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A');
tree.height();
tree.insert(5, 'B').insert(15, 'C').insert(25, 'D');
tree.height();
tree.includes(key)
Determines whether the tree includes a node with a certain key
, returning true
or false
as appropriate.
key
Node key
to search for.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B');
tree.includes(10);
tree.includes(25);
tree.includes(5);
tree.inOrder(fn)
Applies in-order traversal (depth-first traversal - LNR) to the tree and executes the provided fn
function on each traversed node without mutating the tree itself.
fn
Function to execute on each node.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.inOrder(node => console.log(node.key));
tree.insert(key, value)
Mutates the tree by inserting a new node at the appropriate location.
key
Can be any number that will correspond to the key
of the created node.
Each node has its own unique key
.
value
Can be any value that will stored in the created node.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A');
tree.internalNodes()
Applies in-order traversal to the tree and stores each traversed internal node (node with at least a single non-null child) in an array.
The array is returned at the end of the traversal.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C').insert(20, 'D');
tree.internalNodes();
tree.isComplete()
The method returns true
if the tree is a complete binary search tree, which implies that every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
In any other case, the method returns false
.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.isComplete();
tree.insert(3, 'D');
tree.isComplete();
tree.insert(20, 'E');
tree.isComplete();
tree.isEmpty()
Determines whether the tree is empty, returning true
or false
as appropriate.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A');
tree.isEmpty();
tree.isFull()
The method returns true
if all the nodes residing in the tree are either leaf nodes or full nodes.
In any other case (node degree equal to 1) the method returns false
.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.isFull();
tree.insert(8, 'D');
tree.isFull();
tree.isPerfect()
The method returns true
if all the internal nodes residing in the tree are full nodes (node degree equal to 2) and all leaf nodes are at the same height level. In any other case (node degree equal to 1 or leaf and full nodes are found on the same height level) the method returns false
.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.isPerfect();
tree.insert(3, 'D').insert(7, 'E').insert(12, 'F').insert(20, 'G');
tree.isPerfect();
tree.insert(1, 'H');
tree.isPerfect();
tree.keys()
- Return Type:
Array<Number>
Applies in-order traversal to the tree and stores the key
of each traversed node in an array.
The array is returned at the end of the traversal.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.keys();
tree.leafNodes()
Applies in-order traversal to the tree and stores each traversed leaf node (node without children) in an array.
The array is returned at the end of the traversal.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.leafNodes();
tree.levelOrder(fn)
Applies level-order traversal (breadth-first traversal) to the tree and executes the provided fn
function on each traversed node without mutating the tree itself.
fn
Function to execute on each node.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.levelOrder(node => console.log(node.key));
tree.max()
Returns the right-most node in the tree, thus the node corresponding to the maximum key
.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(15, 'B').insert(25, 'C');
tree.max();
tree.maxKey()
- Return Type:
Number | null
Returns the key
of right-most node in the tree, thus the maximum key
in the tree.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(15, 'B').insert(25, 'C');
tree.maxKey();
tree.maxValue()
Returns the value
of right-most node in the tree, thus the value
of the node corresponding to the maximum key
.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(15, 'B').insert(25, 'C');
tree.maxValue();
tree.min()
Returns the left-most node in the tree, thus the node corresponding to the minimum key
.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(0, 'C');
tree.min();
tree.minKey()
- Return Type:
Number | null
Returns the key
of the left-most node in the tree, thus the minimum key
in the tree.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(15, 'B').insert(25, 'C');
tree.minKey();
tree.minValue()
Returns the value
of the left-most node in the tree, thus the value
of the node corresponding to the minimum key
.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(15, 'B').insert(25, 'C');
tree.maxValue();
tree.outOrder(fn)
Applies out-order traversal (depth-first traversal - RNL) to the tree and executes the provided fn
function on each traversed node without mutating the tree itself.
fn
Function to execute on each node.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.outOrder(node => console.log(node.key));
tree.postOrder(fn)
Applies post-order traversal (depth-first traversal - LRN) to the tree and executes the provided fn
function on each traversed node without mutating the tree itself.
fn
Function to execute on each node.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.postOrder(node => console.log(node.key));
tree.preOrder(fn)
Applies pre-order traversal (depth-first traversal - NLR) to the tree and executes the provided fn
function on each traversed node without mutating the tree itself.
fn
Function to execute on each node.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.preOrder(node => console.log(node.key));
tree.remove(key)
Mutates the tree by removing the node corresponding to the key
argument.
key
Can be any number that corresponds to the key
of an existing node.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A');
tree.remove(10);
tree.search(key)
Determines whether the tree includes a node with a certain key
, returning the targeted node or null
as appropriate.
key
Node key
to search for.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B');
tree.search(10);
tree.search(25);
tree.search(5);
tree.size()
Returns the total number of nodes residing in the tree.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(15, 'B').insert(25, 'C');
tree.size();
tree.toArray()
Applies in-order traversal to the tree and stores each traversed node in an array.
The array is returned at the end of the traversal.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C').insert(3, 'D').insert(20, 'F');
tree.toArray();
tree.toPairs()
- Return Type:
Array<[Number, Any]>
Applies in-order traversal to the tree and for each traversed node stores in an array of size n
, where n
the size of the tree, an ordered-pair/2-tuple, where the first element is a number
corresponding to the key
of the traversed node, and the last one is a value of type any
, corresponding to the value
stored in the traversed node.
The array is returned at the end of the traversal.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C').insert(3, 'D').insert(20, 'F');
tree.toPairs();
tree.values()
Applies in-order traversal to the tree and stores the value
of each traversed node in an array.
The array is returned at the end of the traversal.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(15, 'C');
tree.keys();
Also available, along with the Tree
exposed class, is the Node
class, mainly useful for testing purposes, since it can be utilized to compare tree nodes. The class has a binary constructor method, with a key
and a value
parameter, corresponding to the key and the value stored in the created instance, respectively.
node.key
The key
corresponding to the node instance.
const {Node} = require('avlbinstree');
const node = new Node(10, 'A');
node.key;
node.value
The value that the node contains.
const {Node} = require('avlbinstree');
const node = new Node(10, 'A');
node.value;
node.value = 'B'
node.left
The left sub-tree that the node points to.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root;
tree.root.left;
tree.insert(5, 'B').root;
tree.root.left;
node.right
The right sub-tree that the node points to.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root;
tree.root.right;
tree.insert(15, 'B').root;
tree.root.right;
node.balanceFactor
Returns a number corresponding to the balance factor of a node, which is defined as the height difference of its two child sub-trees.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.balanceFactor;
tree.insert(5, 'B').root.balanceFactor;
tree.remove(5).insert(15, 'C').root.balanceFactor;
node.children
Returns an array contacting the children of the instance, where the left child, if present, is the first element of the array, and the right child, if present, is the last element of the array.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.children;
tree.insert(5, 'B').insert(15, 'C').root.children;
node.degree
Returns the number of sub-trees that the node points to.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.degree;
tree.insert(5, 'B').root.degree;
tree.insert(15, 'C').root.degree;
node.height
Returns the maximum distance of any leaf node from the node instance.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').insert(5, 'B').insert(10, 'C').insert(25, 'D');
tree.root.height;
tree.root.right.height();
node.isBalanced()
Determines whether a node is a balanced (has a balance factor equal to 0), returning true
or false
as appropriate.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.isBalanced();
tree.insert(5, 'B').root.isBalanced();
node.isFull()
Determines whether a node is a full node (has two non-null children), returning true
or false
as appropriate.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.isFull();
tree.insert(5, 'B').insert(15, 'C').root.isFull();
node.isInternal()
Determines whether a node is an internal node (has at least one non-null child), returning true
or false
as appropriate.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.isInternal();
tree.insert(5, 'B').root.isInternal();
node.isLeaf()
Determines whether a node is a leaf node (has no children), returning true
or false
as appropriate.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.isLeaf();
tree.insert(5, 'B').root.isLeaf();
node.isLeftHeavy()
Determines whether a node is left heavy (has a balance factor greater than zero), returning true
or false
as appropriate.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.isLeftHeavy();
tree.insert(5, 'B').root.isLeftPartial();
tree.remove(5).insert(10, 'C').root.isLeftPartial();
node.isLeftPartial()
Determines whether a node is a left partial node (has ony one left non-null child), returning true
or false
as appropriate.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.isLeftPartial();
tree.insert(5, 'B').root.isLeftPartial();
node.isPartial()
Determines whether a node is a partial node (has ony one non-null child), returning true
or false
as appropriate.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.isPartial();
tree.insert(15, 'B').root.isPartial();
node.isRightHeavy()
Determines whether a node is right heavy (has a balance factor less than zero), returning true
or false
as appropriate.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.isRightHeavy();
tree.insert(15, 'C').root.isRightHeavy();
tree.remove(15).insert(5, 'B').root.isRightHeavy();
node.isRightPartial()
Determines whether a node is a right partial node (has ony one right non-null child), returning true
or false
as appropriate.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.isRightPartial();
tree.insert(15, 'B').root.isRightPartial();
node.leftChildHeight()
Returns the maximum distance of any leaf node from the left child of the parent node instance. If the parent node has no left child, then -1
is returned.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.leftChildHeight();
tree.insert(5, 'B').root.leftChildHeight();
node.maxChildHeight()
Returns the maximum between the heights of the two child nodes of parent instance. If the parent node has no children, then -1
is returned.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.maxChildHeight();
tree.insert(15, 'B').root.maxChildHeight();
tree.insert(5, 'C').root.maxChildHeight();
tree.insert(1, 'D').root.maxChildHeight();
node.rightChildHeight()
Returns the maximum distance of any leaf node from the right child of the parent node instance. If the parent node has no right child, then -1
is returned.
const {Tree} = require('avlbinstree');
const tree = new Tree();
tree.insert(10, 'A').root.rightChildHeight();
tree.insert(15, 'B').root.rightChildHeight();
node.toPair()
- Return Type:
[Number, Any]
Returns an ordered-pair/2-tuple, where the first element is a number corresponding to the key
of the node, and the last one is a value, that can be of any type, corresponding to the value
stored in the node.
const {Node, Tree} = require('avlbinstree');
const tree = new Tree();
const node = new Node(5, 'B');
node.toPair();
tree.insert(10, 'A').root.toPair();
Development
For more info on how to contribute to the project, please read the contributing guidelines.
- Fork the repository and clone it to your machine
- Navigate to your local fork:
cd avlbinstree
- Install the project dependencies:
npm install
or yarn install
- Lint the code and run the tests:
npm test
or yarn test
Related
- binstree - Binary search trees for ES6
- doublie - Doubly circular & linear linked lists for ES6
- mheap - Binary min & max heaps for ES6
- prioqueue - Priority queues for ES6
- singlie - Singly circular & linear linked lists for ES6
Team
License
MIT