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
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.
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.
30 * Constructs a Splay tree. A splay tree is a self-balancing binary
31 * search tree with the additional property that recently accessed
32 * elements are quick to access again. It performs basic operations
33 * such as insertion, look-up and removal in O(log(n)) amortized time.
37 function SplayTree() {
42 * Pointer to the root node of the tree.
44 * @type {SplayTree.Node}
47 SplayTree.prototype.root_ = null;
51 * @return {boolean} Whether the tree is empty.
53 SplayTree.prototype.isEmpty = function() {
60 * Inserts a node into the tree with the specified key and value if
61 * the tree does not already contain a node with the specified key. If
62 * the value is inserted, it becomes the root of the tree.
64 * @param {number} key Key to insert into the tree.
65 * @param {*} value Value to insert into the tree.
67 SplayTree.prototype.insert = function(key, value) {
69 this.root_ = new SplayTree.Node(key, value);
72 // Splay on the key to move the last node on the search path for
73 // the key to the root of the tree.
75 if (this.root_.key == key) {
78 var node = new SplayTree.Node(key, value);
79 if (key > this.root_.key) {
80 node.left = this.root_;
81 node.right = this.root_.right;
82 this.root_.right = null;
84 node.right = this.root_;
85 node.left = this.root_.left;
86 this.root_.left = null;
93 * Removes a node with the specified key from the tree if the tree
94 * contains a node with this key. The removed node is returned. If the
95 * key is not found, an exception is thrown.
97 * @param {number} key Key to find and remove from the tree.
98 * @return {SplayTree.Node} The removed node.
100 SplayTree.prototype.remove = function(key) {
101 if (this.isEmpty()) {
102 throw Error('Key not found: ' + key);
105 if (this.root_.key != key) {
106 throw Error('Key not found: ' + key);
108 var removed = this.root_;
109 if (!this.root_.left) {
110 this.root_ = this.root_.right;
112 var right = this.root_.right;
113 this.root_ = this.root_.left;
114 // Splay to make sure that the new root has an empty right child.
116 // Insert the original right child as the right child of the new
118 this.root_.right = right;
125 * Returns the node having the specified key or null if the tree doesn't contain
126 * a node with the specified key.
128 * @param {number} key Key to find in the tree.
129 * @return {SplayTree.Node} Node having the specified key.
131 SplayTree.prototype.find = function(key) {
132 if (this.isEmpty()) {
136 return this.root_.key == key ? this.root_ : null;
141 * @return {SplayTree.Node} Node having the minimum key value.
143 SplayTree.prototype.findMin = function() {
144 if (this.isEmpty()) {
147 var current = this.root_;
148 while (current.left) {
149 current = current.left;
156 * @return {SplayTree.Node} Node having the maximum key value.
158 SplayTree.prototype.findMax = function(opt_startNode) {
159 if (this.isEmpty()) {
162 var current = opt_startNode || this.root_;
163 while (current.right) {
164 current = current.right;
171 * @return {SplayTree.Node} Node having the maximum key value that
172 * is less or equal to the specified key value.
174 SplayTree.prototype.findGreatestLessThan = function(key) {
175 if (this.isEmpty()) {
178 // Splay on the key to move the node with the given key or the last
179 // node on the search path to the top of the tree.
181 // Now the result is either the root node or the greatest node in
183 if (this.root_.key <= key) {
185 } else if (this.root_.left) {
186 return this.findMax(this.root_.left);
194 * @return {Array<*>} An array containing all the values of tree's nodes paired
197 SplayTree.prototype.exportKeysAndValues = function() {
199 this.traverse_(function(node) { result.push([node.key, node.value]); });
205 * @return {Array<*>} An array containing all the values of tree's nodes.
207 SplayTree.prototype.exportValues = function() {
209 this.traverse_(function(node) { result.push(node.value); });
215 * Perform the splay operation for the given key. Moves the node with
216 * the given key to the top of the tree. If no node has the given
217 * key, the last node on the search path is moved to the top of the
218 * tree. This is the simplified top-down splaying algorithm from:
219 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan
221 * @param {number} key Key to splay the tree on.
224 SplayTree.prototype.splay_ = function(key) {
225 if (this.isEmpty()) {
228 // Create a dummy node. The use of the dummy node is a bit
229 // counter-intuitive: The right child of the dummy node will hold
230 // the L tree of the algorithm. The left child of the dummy node
231 // will hold the R tree of the algorithm. Using a dummy node, left
232 // and right will always be nodes and we avoid special cases.
233 var dummy, left, right;
234 dummy = left = right = new SplayTree.Node(null, null);
235 var current = this.root_;
237 if (key < current.key) {
241 if (key < current.left.key) {
243 var tmp = current.left;
244 current.left = tmp.right;
252 right.left = current;
254 current = current.left;
255 } else if (key > current.key) {
256 if (!current.right) {
259 if (key > current.right.key) {
261 var tmp = current.right;
262 current.right = tmp.left;
265 if (!current.right) {
270 left.right = current;
272 current = current.right;
278 left.right = current.left;
279 right.left = current.right;
280 current.left = dummy.right;
281 current.right = dummy.left;
282 this.root_ = current;
287 * Performs a preorder traversal of the tree.
289 * @param {function(SplayTree.Node)} f Visitor function.
292 SplayTree.prototype.traverse_ = function(f) {
293 var nodesToVisit = [this.root_];
294 while (nodesToVisit.length > 0) {
295 var node = nodesToVisit.shift();
300 nodesToVisit.push(node.left);
301 nodesToVisit.push(node.right);
307 * Constructs a Splay tree node.
309 * @param {number} key Key.
310 * @param {*} value Value.
312 SplayTree.Node = function(key, value) {
319 * @type {SplayTree.Node}
321 SplayTree.Node.prototype.left = null;
325 * @type {SplayTree.Node}
327 SplayTree.Node.prototype.right = null;