Deletes the node by given key from the subtree of given node. Returns an array with:
[0] - the node that takes the place of given node after deletion and re-balancing,
which might also be the given node itself.
[1] - A boolean indicating whether a node was actually deleted.
This will be false if the key was not found in the tree.
Inserts the given key an corresponding value into the sub-tree of the given node. Returns an array of length 2 with at:
[0] - the node that takes the place of given node after insertion and re-balancing,
which might also be the given node itself.
[1] - A boolean indicating whether the new key and value were actually inserted.
This will be false if the key was already in the tree prior to insertion.
Returns the given node's balance: the relationship between the heights
of its left and right subtrees. Returns a negative number if the node's
left child is the higher height child, or a positive number if the right
child is the higher height child. Returns zero if either the node is null
or both its children have equal height.
Returns the height of given node or zero if the node is null.
Performs a left rotation on the given node. Returns the node that takes the place of the given node after rotation.
┌──────────────────────────────────────────────────────────────────┐
│ argument -> z y <- return │
│ / \ / \ │
│ T1 y rotateLeft(z) z x │
│ / \ - - - - - - - -> / \ / \ │
│ T2 x T1 T2 T3 T4 │
│ / \ │
│ T3 T4 │
└──────────────────────────────────────────────────────────────────┘
Performs a right rotation on the given node. Returns the node that takes the place of the given node after rotation.
┌──────────────────────────────────────────────────────────────────┐
│ argument -> z y <- return │
│ / \ / \ │
│ y T4 rotateRight(z) x z │
│ / \ - - - - - - - - -> / \ / \ │
│ x T3 T1 T2 T3 T4 │
│ / \ │
│ T1 T2 │
└──────────────────────────────────────────────────────────────────┘
Updates the given node's height property based on the current heights of its left and right subtrees.
Updates the given node's size property based on the current sizes of its left and right subtrees.
The internal recursive functions used by the AVLTree class, and additional helper functions. These perform outside of the tree class context, and take nodes to operate on. This makes them reusable for many more applications.
While the AVLTree interface only exposes its contained values the functions here return nodes with these values within, so that internally we can easily traverse subtrees and otherwise operate on them.