Lines Matching refs:key
44 function GeneratePayloadTree(depth, key) {
48 string : 'String for key ' + key + ' in leaf node'
52 left: GeneratePayloadTree(depth - 1, key),
53 right: GeneratePayloadTree(depth - 1, key)
67 // Insert new node with a unique key.
68 var key;
70 key = GenerateKey();
71 } while (splayTree.find(key) != null);
72 splayTree.insert(key, GeneratePayloadTree(kSplayTreePayloadDepth, key));
73 return key;
109 var key = InsertNewNode();
110 var greatest = splayTree.findGreatestLessThan(key);
111 if (greatest == null) splayTree.remove(key);
112 else splayTree.remove(greatest.key);
147 * Inserts a node into the tree with the specified key and value if
148 * the tree does not already contain a node with the specified key. If
151 * @param {number} key Key to insert into the tree.
154 SplayTree.prototype.insert = function(key, value) {
156 this.root_ = new SplayTree.Node(key, value);
159 // Splay on the key to move the last node on the search path for
160 // the key to the root of the tree.
161 this.splay_(key);
162 if (this.root_.key == key) {
165 var node = new SplayTree.Node(key, value);
166 if (key > this.root_.key) {
180 * Removes a node with the specified key from the tree if the tree
181 * contains a node with this key. The removed node is returned. If the
182 * key is not found, an exception is thrown.
184 * @param {number} key Key to find and remove from the tree.
187 SplayTree.prototype.remove = function(key) {
189 throw Error('Key not found: ' + key);
191 this.splay_(key);
192 if (this.root_.key != key) {
193 throw Error('Key not found: ' + key);
202 this.splay_(key);
212 * Returns the node having the specified key or null if the tree doesn't contain
213 * a node with the specified key.
215 * @param {number} key Key to find in the tree.
216 * @return {SplayTree.Node} Node having the specified key.
218 SplayTree.prototype.find = function(key) {
222 this.splay_(key);
223 return this.root_.key == key ? this.root_ : null;
228 * @return {SplayTree.Node} Node having the maximum key value that
229 * is less or equal to the specified key value.
231 SplayTree.prototype.findGreatestLessThan = function(key) {
235 // Splay on the key to move the node with the given key or the last
237 this.splay_(key);
240 if (this.root_.key <= key) {
256 this.root_.traverse_(function(node) { result.push(node.key); });
263 * Perform the splay operation for the given key. Moves the node with
264 * the given key to the top of the tree. If no node has the given
265 * key, the last node on the search path is moved to the top of the
269 * @param {number} key Key to splay the tree on.
272 SplayTree.prototype.splay_ = function(key) {
285 if (key < current.key) {
289 if (key < current.left.key) {
303 } else if (key > current.key) {
307 if (key > current.right.key) {
337 * @param {number} key Key.
340 SplayTree.Node = function(key, value) {
341 this.key = key;