* Removes a node with the specified key from the tree if the tree * contains a node with this key. The removed node is returned. If the * key is not found, an exception is thrown. * * @param {number} key Key to find and remove from the tree. * @return {SplayTreeNode} The removed node.
(key)
| 92 | * @return {SplayTreeNode} The removed node. |
| 93 | */ |
| 94 | remove(key) { |
| 95 | if (this.isEmpty()) { |
| 96 | throw Error(`Key not found: ${key}`); |
| 97 | } |
| 98 | this.splay_(key); |
| 99 | if (this.root_.key != key) { |
| 100 | throw Error(`Key not found: ${key}`); |
| 101 | } |
| 102 | const removed = this.root_; |
| 103 | if (this.root_.left === null) { |
| 104 | this.root_ = this.root_.right; |
| 105 | } else { |
| 106 | const { right } = this.root_; |
| 107 | this.root_ = this.root_.left; |
| 108 | // Splay to make sure that the new root has an empty right child. |
| 109 | this.splay_(key); |
| 110 | // Insert the original right child as the right child of the new |
| 111 | // root. |
| 112 | this.root_.right = right; |
| 113 | } |
| 114 | return removed; |
| 115 | } |
| 116 | |
| 117 | /** |
| 118 | * Returns the node having the specified key or null if the tree doesn't contain |