Class: AVLTree

data-structures/avl-tree. AVLTree

Constructor

new AVLTree()

AVL Tree.
Source:

Methods

_getHeightAtNode(node)

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

_getNodesToRestructureInsert(traveledNodes)

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

_getNodesToRestructureRemove(traveledNodes)

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

_isBalancedAtNode(node)

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

_leftLeft(x, y, z)

Rotates the given nodes from a left left pattern to a parent, with 2 children.
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.
Source:

_leftRight(x, y, z)

Rotates the given nodes from a left right pattern to a parent, with 2 children.
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.
Source:

_maintainHeightBalanceProperty(node, isRemove)

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

_restructure(nodesToBeRestructured)

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

_rightLeft(x, y, z)

Rotates the given nodes from a right left pattern to a parent, with 2 children.
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.
Source:

_rightRight(x, y, z)

Rotates the given nodes from a right right pattern to a parent, with 2 children.
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.
Source:

find(value)

Finds a node by it's value.

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

findMax() → {Node}

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

findMin() → {Node}

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

getDiameter() → {Number}

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

getTreeHeight() → {Number}

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

inorder(callback)

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

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.
Parameters:
Name Type Description
value Number | String Node value.
current Node Current node.
Source:

isBalanced() → {Boolean}

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

lowestCommonAncestor() → {Node}

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

postorder(callback)

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

preorder(callback)

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

remove(value) → {Boolean}

Removes node from the tree.

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