AVLTree

data-structures/avl-tree. AVLTree

new AVLTree()

AVL Tree.
Source:

Methods

_getHeightAtNode(node)

Calculates the height of a node based on height property of children.
Source:
Parameters:
Name Type Description
node Node Given node's height is returned.

_getNodesToRestructureInsert(traveledNodes)

Gets the nodes to be restructured during an AVL restructure after an insert takes place.
Source:
Parameters:
Name Type Description
traveledNodes Array Array of previously traveled nodes that are used to help determine the nodes to be restructured.

_getNodesToRestructureRemove(traveledNodes)

Gets the nodes to be restructured during an AVL restructure after a remove/delete takes place.
Source:
Parameters:
Name Type Description
traveledNodes Array Array of previously traveled nodes that are used to help determine the nodes to be restructured.

_isBalancedAtNode(node)

Checks if a given node has an imbalance.
Source:
Parameters:
Name Type Description
node Node Given node's children are checked for imbalance.

_leftLeft(x, y, z)

Rotates the given nodes from a left left pattern to a parent, with 2 children.
Source:
Parameters:
Name Type Description
x Node node with lowest height to be restructured.
y Node parent of x parameter.
z Node grandparent of x, largest height.

_leftRight(x, y, z)

Rotates the given nodes from a left right pattern to a parent, with 2 children.
Source:
Parameters:
Name Type Description
x Node node with lowest height to be restructured.
y Node parent of x parameter.
z Node grandparent of x, largest height.

_maintainHeightBalanceProperty(node, isRemove)

Maintains the height balance property by walking to root and checking for invalid height differences between children and restructuring appropriately.
Source:
Parameters:
Name Type Description
node Node Started node.
isRemove Boolean Represents if method was called after remove.

_restructure(nodesToBeRestructured)

Identifies the pattern of given nodes, then calls the appropriate pattern rotator.
Source:
Parameters:
Name Type Description
nodesToBeRestructured Array array of nodes, in format, [x, y, z], to be restructured

_rightLeft(x, y, z)

Rotates the given nodes from a right left pattern to a parent, with 2 children.
Source:
Parameters:
Name Type Description
x Node node with lowest height to be restructured.
y Node parent of x parameter.
z Node grandparent of x, largest height.

_rightRight(x, y, z)

Rotates the given nodes from a right right pattern to a parent, with 2 children.
Source:
Parameters:
Name Type Description
x Node node with lowest height to be restructured.
y Node parent of x parameter.
z Node grandparent of x, largest height.

find(value)

Finds a node by it's value.

Average time complexity: O(log N).
Source:
Parameters:
Name Type Description
value Number | String of the node which should be found.

findMax() → {Node}

Finds the node with maximum value in the whole tree.
Source:
Returns:
Type:
Node
The maximum node of the tree.

findMin() → {Node}

Finds the node with minimum value in the whole tree.
Source:
Returns:
Type:
Node
The minimum node of the tree.

getDiameter() → {Number}

Finds the diameter of the AVL tree.
Source:
Returns:
Type:
Number
The longest path in the AVL Tree.

getTreeHeight() → {Number}

Returns the height of the tree.
Source:
Returns:
Type:
Number
The height of the tree.

inorder(callback)

In-order traversal of the whole AVL tree.
Source:
Parameters:
Name Type Description
callback function Callback which will be called for each traversed node.

insert(value, current)

Inserts a node into the AVL Tree.

Time complexity: O(log N) in the average case and O(N) in the worst case.
Source:
Parameters:
Name Type Description
value Number | String Node value.
current Node Current node.

isBalanced() → {Boolean}

Returns whether the AVL Tree is balanced.
Source:
Returns:
Type:
Boolean
Whether the tree is balanced or not.

lowestCommonAncestor() → {Node}

Finds the lowest common ancestor of two nodes.
Source:
Returns:
Type:
Node
The lowest common ancestor of the two nodes or null.

postorder(callback)

Post-order traversal of the whole tree.
Source:
Parameters:
Name Type Description
callback function Callback which will be called for each traversed node.

preorder(callback)

Pre-order preorder traversal of the whole tree.
Source:
Parameters:
Name Type Description
callback function Callback which will be called for each traversed node.

remove(value) → {Boolean}

Removes node from the tree.

Average runtime complexity: O(log N).
Source:
Parameters:
Name Type Description
value Number | String of node to be removed
Returns:
Type:
Boolean
True/false depending on whether the given node is removed.