splaytree.mjs 8.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291
  1. // Copyright 2009 the V8 project authors. All rights reserved.
  2. // Redistribution and use in source and binary forms, with or without
  3. // modification, are permitted provided that the following conditions are
  4. // met:
  5. //
  6. // * Redistributions of source code must retain the above copyright
  7. // notice, this list of conditions and the following disclaimer.
  8. // * Redistributions in binary form must reproduce the above
  9. // copyright notice, this list of conditions and the following
  10. // disclaimer in the documentation and/or other materials provided
  11. // with the distribution.
  12. // * Neither the name of Google Inc. nor the names of its
  13. // contributors may be used to endorse or promote products derived
  14. // from this software without specific prior written permission.
  15. //
  16. // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17. // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18. // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19. // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20. // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21. // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22. // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23. // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24. // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25. // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26. // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27. /**
  28. * Constructs a Splay tree. A splay tree is a self-balancing binary
  29. * search tree with the additional property that recently accessed
  30. * elements are quick to access again. It performs basic operations
  31. * such as insertion, look-up and removal in O(log(n)) amortized time.
  32. *
  33. * @constructor
  34. */
  35. export class SplayTree {
  36. /**
  37. * Pointer to the root node of the tree.
  38. *
  39. * @type {SplayTreeNode}
  40. * @private
  41. */
  42. root_ = null;
  43. /**
  44. * @return {boolean} Whether the tree is empty.
  45. */
  46. isEmpty() {
  47. return this.root_ === null;
  48. }
  49. /**
  50. * Inserts a node into the tree with the specified key and value if
  51. * the tree does not already contain a node with the specified key. If
  52. * the value is inserted, it becomes the root of the tree.
  53. *
  54. * @param {number} key Key to insert into the tree.
  55. * @param {*} value Value to insert into the tree.
  56. */
  57. insert(key, value) {
  58. if (this.isEmpty()) {
  59. this.root_ = new SplayTreeNode(key, value);
  60. return;
  61. }
  62. // Splay on the key to move the last node on the search path for
  63. // the key to the root of the tree.
  64. this.splay_(key);
  65. if (this.root_.key == key) return;
  66. const node = new SplayTreeNode(key, value);
  67. if (key > this.root_.key) {
  68. node.left = this.root_;
  69. node.right = this.root_.right;
  70. this.root_.right = null;
  71. } else {
  72. node.right = this.root_;
  73. node.left = this.root_.left;
  74. this.root_.left = null;
  75. }
  76. this.root_ = node;
  77. }
  78. /**
  79. * Removes a node with the specified key from the tree if the tree
  80. * contains a node with this key. The removed node is returned. If the
  81. * key is not found, an exception is thrown.
  82. *
  83. * @param {number} key Key to find and remove from the tree.
  84. * @return {SplayTreeNode} The removed node.
  85. */
  86. remove(key) {
  87. if (this.isEmpty()) {
  88. throw Error(`Key not found: ${key}`);
  89. }
  90. this.splay_(key);
  91. if (this.root_.key != key) {
  92. throw Error(`Key not found: ${key}`);
  93. }
  94. const removed = this.root_;
  95. if (this.root_.left === null) {
  96. this.root_ = this.root_.right;
  97. } else {
  98. const { right } = this.root_;
  99. this.root_ = this.root_.left;
  100. // Splay to make sure that the new root has an empty right child.
  101. this.splay_(key);
  102. // Insert the original right child as the right child of the new
  103. // root.
  104. this.root_.right = right;
  105. }
  106. return removed;
  107. }
  108. /**
  109. * Returns the node having the specified key or null if the tree doesn't contain
  110. * a node with the specified key.
  111. *
  112. * @param {number} key Key to find in the tree.
  113. * @return {SplayTreeNode} Node having the specified key.
  114. */
  115. find(key) {
  116. if (this.isEmpty()) return null;
  117. this.splay_(key);
  118. return this.root_.key == key ? this.root_ : null;
  119. }
  120. /**
  121. * @return {SplayTreeNode} Node having the minimum key value.
  122. */
  123. findMin() {
  124. if (this.isEmpty()) return null;
  125. let current = this.root_;
  126. while (current.left !== null) {
  127. current = current.left;
  128. }
  129. return current;
  130. }
  131. /**
  132. * @return {SplayTreeNode} Node having the maximum key value.
  133. */
  134. findMax(opt_startNode) {
  135. if (this.isEmpty()) return null;
  136. let current = opt_startNode || this.root_;
  137. while (current.right !== null) {
  138. current = current.right;
  139. }
  140. return current;
  141. }
  142. /**
  143. * @return {SplayTreeNode} Node having the maximum key value that
  144. * is less or equal to the specified key value.
  145. */
  146. findGreatestLessThan(key) {
  147. if (this.isEmpty()) return null;
  148. // Splay on the key to move the node with the given key or the last
  149. // node on the search path to the top of the tree.
  150. this.splay_(key);
  151. // Now the result is either the root node or the greatest node in
  152. // the left subtree.
  153. if (this.root_.key <= key) {
  154. return this.root_;
  155. } else if (this.root_.left !== null) {
  156. return this.findMax(this.root_.left);
  157. } else {
  158. return null;
  159. }
  160. }
  161. /**
  162. * @return {Array<*>} An array containing all the values of tree's nodes paired
  163. * with keys.
  164. */
  165. exportKeysAndValues() {
  166. const result = [];
  167. this.traverse_(function(node) { result.push([node.key, node.value]); });
  168. return result;
  169. }
  170. /**
  171. * @return {Array<*>} An array containing all the values of tree's nodes.
  172. */
  173. exportValues() {
  174. const result = [];
  175. this.traverse_(function(node) { result.push(node.value) });
  176. return result;
  177. }
  178. /**
  179. * Perform the splay operation for the given key. Moves the node with
  180. * the given key to the top of the tree. If no node has the given
  181. * key, the last node on the search path is moved to the top of the
  182. * tree. This is the simplified top-down splaying algorithm from:
  183. * "Self-adjusting Binary Search Trees" by Sleator and Tarjan
  184. *
  185. * @param {number} key Key to splay the tree on.
  186. * @private
  187. */
  188. splay_(key) {
  189. if (this.isEmpty()) return;
  190. // Create a dummy node. The use of the dummy node is a bit
  191. // counter-intuitive: The right child of the dummy node will hold
  192. // the L tree of the algorithm. The left child of the dummy node
  193. // will hold the R tree of the algorithm. Using a dummy node, left
  194. // and right will always be nodes and we avoid special cases.
  195. let dummy, left, right;
  196. dummy = left = right = new SplayTreeNode(null, null);
  197. let current = this.root_;
  198. while (true) {
  199. if (key < current.key) {
  200. if (current.left === null) break;
  201. if (key < current.left.key) {
  202. // Rotate right.
  203. const tmp = current.left;
  204. current.left = tmp.right;
  205. tmp.right = current;
  206. current = tmp;
  207. if (current.left === null) break;
  208. }
  209. // Link right.
  210. right.left = current;
  211. right = current;
  212. current = current.left;
  213. } else if (key > current.key) {
  214. if (current.right === null) break;
  215. if (key > current.right.key) {
  216. // Rotate left.
  217. const tmp = current.right;
  218. current.right = tmp.left;
  219. tmp.left = current;
  220. current = tmp;
  221. if (current.right === null) break;
  222. }
  223. // Link left.
  224. left.right = current;
  225. left = current;
  226. current = current.right;
  227. } else {
  228. break;
  229. }
  230. }
  231. // Assemble.
  232. left.right = current.left;
  233. right.left = current.right;
  234. current.left = dummy.right;
  235. current.right = dummy.left;
  236. this.root_ = current;
  237. }
  238. /**
  239. * Performs a preorder traversal of the tree.
  240. *
  241. * @param {function(SplayTreeNode)} f Visitor function.
  242. * @private
  243. */
  244. traverse_(f) {
  245. const nodesToVisit = [this.root_];
  246. while (nodesToVisit.length > 0) {
  247. const node = nodesToVisit.shift();
  248. if (node === null) continue;
  249. f(node);
  250. nodesToVisit.push(node.left);
  251. nodesToVisit.push(node.right);
  252. }
  253. }
  254. }
  255. /**
  256. * Constructs a Splay tree node.
  257. *
  258. * @param {number} key Key.
  259. * @param {*} value Value.
  260. */
  261. class SplayTreeNode {
  262. constructor(key, value) {
  263. this.key = key;
  264. this.value = value;
  265. /**
  266. * @type {SplayTreeNode}
  267. */
  268. this.left = null;
  269. /**
  270. * @type {SplayTreeNode}
  271. */
  272. this.right = null;
  273. }
  274. };