Comparing version 0.1.0 to 0.1.1
/** | ||
* splaytree v0.1.0 | ||
* splaytree v0.1.1 | ||
* Fast Splay tree for Node and browser | ||
@@ -247,3 +247,3 @@ * | ||
if (!z) return; | ||
if (!z) return false; | ||
@@ -267,5 +267,30 @@ this.splay(z); | ||
this._size--; | ||
return true; | ||
} | ||
removeNode(z) { | ||
if (!z) return false; | ||
this.splay(z); | ||
if (!z.left) this.replace(z, z.right); | ||
else if (!z.right) this.replace(z, z.left); | ||
else { | ||
var y = this.minNode(z.right); | ||
if (y.parent !== z) { | ||
this.replace(y, y.right); | ||
y.right = z.right; | ||
y.right.parent = y; | ||
} | ||
this.replace(z, y); | ||
y.left = z.left; | ||
y.left.parent = y; | ||
} | ||
this._size--; | ||
return true; | ||
} | ||
erase (key) { | ||
@@ -272,0 +297,0 @@ var z = this.find(key); |
/** | ||
* splaytree v0.1.0 | ||
* splaytree v0.1.1 | ||
* Fast Splay tree for Node and browser | ||
@@ -264,3 +264,3 @@ * | ||
if (!z) { return; } | ||
if (!z) { return false; } | ||
@@ -284,5 +284,30 @@ this.splay(z); | ||
this._size--; | ||
return true; | ||
}; | ||
SplayTree.prototype.removeNode = function removeNode (z) { | ||
if (!z) { return false; } | ||
this.splay(z); | ||
if (!z.left) { this.replace(z, z.right); } | ||
else if (!z.right) { this.replace(z, z.left); } | ||
else { | ||
var y = this.minNode(z.right); | ||
if (y.parent !== z) { | ||
this.replace(y, y.right); | ||
y.right = z.right; | ||
y.right.parent = y; | ||
} | ||
this.replace(z, y); | ||
y.left = z.left; | ||
y.left.parent = y; | ||
} | ||
this._size--; | ||
return true; | ||
}; | ||
SplayTree.prototype.erase = function erase (key) { | ||
@@ -289,0 +314,0 @@ var z = this.find(key); |
@@ -16,3 +16,4 @@ export type Node<Key extends any, Value extends any> = { | ||
insert(key: Key, data?: Value): Node<Key, Value>; | ||
remove(key: Key): Node<Key, Value>; | ||
remove(key: Key): boolean; | ||
removeNode(node: Node<Key, Value>): boolean; | ||
find(key: Key): Node<Key, Value>; | ||
@@ -19,0 +20,0 @@ at(index: number): Node<Key, Value>; |
27
index.js
@@ -238,3 +238,3 @@ function DEFAULT_COMPARE (a, b) { return a > b ? 1 : a < b ? -1 : 0; } | ||
if (!z) return; | ||
if (!z) return false; | ||
@@ -258,5 +258,30 @@ this.splay(z); | ||
this._size--; | ||
return true; | ||
} | ||
removeNode(z) { | ||
if (!z) return false; | ||
this.splay(z); | ||
if (!z.left) this.replace(z, z.right); | ||
else if (!z.right) this.replace(z, z.left); | ||
else { | ||
var y = this.minNode(z.right); | ||
if (y.parent !== z) { | ||
this.replace(y, y.right); | ||
y.right = z.right; | ||
y.right.parent = y; | ||
} | ||
this.replace(z, y); | ||
y.left = z.left; | ||
y.left.parent = y; | ||
} | ||
this._size--; | ||
return true; | ||
} | ||
erase (key) { | ||
@@ -263,0 +288,0 @@ var z = this.find(key); |
{ | ||
"name": "splaytree", | ||
"version": "0.1.0", | ||
"version": "0.1.1", | ||
"author": "Alexander Milevski <info@w8r.name>", | ||
@@ -5,0 +5,0 @@ "license": "MIT", |
@@ -42,4 +42,5 @@ # Splay tree [![npm version](https://badge.fury.io/js/splaytree.svg)](https://badge.fury.io/js/avl) [![CircleCI](https://circleci.com/gh/w8r/splay-tree.svg?style=svg)](https://circleci.com/gh/w8r/splay-tree) | ||
* `new SplayTree([comparator], [noDuplicates:Boolean])`, where `compare` is optional comparison function | ||
* `tree.insert(key:any, [data:any])` - Insert item | ||
* `tree.remove(key:any)` - Remove item | ||
* `tree.insert(key:any, [data:any]):Node` - Insert item | ||
* `tree.remove(key:any):Boolean` - Remove item | ||
* `tree.removeNode(Node:any)|Boolean` - Remove node | ||
* `tree.find(key):Node|Null` - Return node by its key | ||
@@ -46,0 +47,0 @@ * `tree.at(index:Number):Node|Null` - Return node by its index in sorted order of keys |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
94385
1369
201