Methods
_getHeight(node) → {Number}
Recursive worker function for getHeight()
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
node |
Node
|
The node of the current recursive frame. |
Returns:
- Type:
-
Number
The height of the tree.
_splaylessSearch(value)
Finds a node by it's value.
Average time complexity: O(log N).
Average time complexity: O(log N).
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
value |
Number
|
String
|
of the node which should be found. |
getDiameter() → {Number}
Finds the diameter of the Splay Tree.
- Source:
Returns:
- Type:
-
Number
The longest path in the tree.
getHeight() → {Number}
Returns the height of the tree.
- Source:
Returns:
- Type:
-
Number
The height of the tree.
inorder(callback)
In-order traversal of the whole Splay 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 splay tree.
Time complexity: O(log N) in the average case and amortized O(log n) in the worst case.
Time complexity: O(log N) in the average case and amortized O(log n) in the worst case.
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
value |
Number
|
String
|
Node value. |
current |
Node
|
Current node. |
isBalanced() → {Boolean}
Returns whether the Splay 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 with given value from the tree.
Average runtime complexity: O(log N).
Average runtime complexity: O(log N).
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
value |
Number
|
String
|
Value to be removed |
Returns:
- Type:
-
Boolean
True/false depending
on whether the given node is removed.
search(value)
Finds a node by it's value.
Average time complexity: O(log N).
Average time complexity: O(log N).
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
value |
Number
|
String
|
of the node which should be found. |