@datastructures/avl-tree 🦄⛓

The AVL Tree is a Binary Search Tree that self balances when the right or left side becomes > 1 deeper than the other The self-balancing ensures that time complexity of the search method stays close to O(NlogN) Each node is a seperate object; an instance of AvlTreeNode AvlTree currently only handles numbers, but could be converted to a Generic to handle strings as well

Install

npm i @datastructures/avl-tree -D

# or

yarn add @datastructures/avl-tree -D

Usage

New AVL Trees can be created by importing the AvlTree class and setting them up similarly to the example below.

import { AvlTree } from '@datastructures/avl-tree'

const tree = new AvlTree()
tree.add(2)
tree.add(1)

console.log(tree.count()) // 2
console.log(tree.search(2)) // 2
console.log(tree.search(3)) // null

tree.inOrderTraversal(node => console.log('This node has value:', node.value))
/*
This node has value: 1
This node has value: 2
*/

API

Listed below is the AVL Tree API.

`Methods`

add(value): adds a AvlTreeNode with a value {number} to the tree. Rebalancing is performed automatically after the new AvlTreeNode is added.

ex: tree.add(1)

remove(value): removes a AvlTreeNode by value from the tree. Rebalancing is performed automatically after the AvlTreeNode is removed.

ex: tree.remove(1)

search(value): searches for an existing AvlTreeNode by value. If one is found, the value is returned. The tree is not modified.

ex: if (tree.search(value)) { /* do something about it */ }

preOrderTraversalRecursive(fn): envokes a callback function (fn) on each node within a tree, using "preOrder traversal" order

ex: tree.preOrderTraversalRecursive(node => console.log('This node has value:', node.value))

postOrderTraversalRecursive(fn): envokes a callback function (fn) on each node within a tree, using "postOrder traversal" order

ex: tree.postOrderTraversalRecursive(node => console.log('This node has value:', node.value))

inOrderTraversalRecursive(fn): envokes a callback function (fn) on each node within a tree, using "inOrder traversal" order

ex: tree.inOrderTraversalRecursive(node => console.log('This node has value:', node.value))

inOrderTraversal(fn): envokes a callback function (fn) on each node within a tree, using "inOrder traversal" order. This method is iterative rather than recursive, so is safer for production scenarios.

ex: tree.inOrderTraversal(node => console.log('This node has value:', node.value))

count: returns number of AvlTreeNodes currently in the tree

ex: const count = tree.count()

clear: removes all AvlTreeNodes from tree and allows them to be garbage collected

ex: tree.clear()

Resources

The list below provides links to other helpful tools for understanding the Linked List data structure.

AVL Tree via Wikipedia

Code Examples

View other Data Structures.