npm i red-black-tree-js
import RbTree from "red-black-tree-js" const rbTree = new RbTree(); rbTree.insert(1, "foo"); rbTree.insert(2, "bar"); rbTree.insert(3, "bar"); rbTree.insert(4, "bar"); rbTree.insert(5, "bar"); rbTree.insert(6, "bar"); rbTree.remove(6); const iterator = rbTree.createIterator(); let result = []; while (iterator.hasNext()) { result.push(iterator.next()); }
- https://www.cs.usfca.edu/~galles/visualization/RedBlack.html visualization
- https://en.wikipedia.org/wiki/Red%E2%80%93black_tree wiki
- data structure
| nodeColor | value |
|---|---|
| BLACK | 1 |
| RED | 0 |
| Node | LeafNode |
|---|---|
| left | left(null) |
| right | right(null) |
| parent | parent(null) |
| key | key(null) |
| value | value(null) |
| color | color(black) |
-
create RB TREE
let rbTree = new RbTree()
create a red black tree with root = null -
find
const rbTree = new RbTree(); rbTree.insert(1, "foo"); rbTree.insert(2, "bar"); rbTree.insert(3, "bar"); const value = rbTree.find(2); value is "bar" Look up value by it's key
- iterator() return the next smallest number
rbTree.insert(30, "abc"); rbTree.insert(20, "foo"); rbTree.insert(40, "bar"); rbTree.insert(10, "bar"); const iterator = rbTree.createIterator(); let result = []; while (iterator.hasNext()) { result.push(iterator.next()); }
- findNode(key)
const rbTree = new RbTree(); rbTree.insert(1, "foo"); rbTree.insert(2, "bar"); rbTree.insert(3, "bar"); const node = rbTree.findNode(2); return the node object
- update(key, value)
const rbTree = new RbTree(); rbTree.insert(1, "foo"); rbTree.insert(2, "bar"); rbTree.update(2, "updated") now the value is "updated"
-
insert(key, value)
rbTree.insert(1, "abc")insert a key and a value to a node -
remove(key)
rbTree.remove(1)
remove a node by its key -
print()
rbTree.insert(30, "abc"); rbTree.insert(20, "foo"); rbTree.insert(40, "bar"); rbTree.insert(10, "bar"); rbTree.print(); 30 color: 1 ___20 color: 0 (parent node 30) ___40 color: 0 (parent node 30) ______null color: 1 (parent node 20) ______null color: 1 (parent node 20) ______null color: 1 (parent node 40) ______null color: 1 (parent node 40)
print out the current tree in a good format
- inOrderSucc(node)
const rbTree = new RbTree(); rbTree.insert(2, "foo"); rbTree.insert(1, "bar"); rbTree.insert(3, "bar"); let next = rbTree.inOrderSucc(rbTree.root) console.log(next) {key : 3, value: "bar"}
- toSortedArray()
const rbTree = new RbTree(); rbTree.insert(1, "foo"); rbTree.insert(2, "bar"); rbTree.insert(3, "bar"); const array = rbTree.toSortedArray(); array is [Object, Object, Object] return a sorted array of objects that contains key and value
- toArrayPreOrder()
const rbTree = new RbTree(); rbTree.insert(3, "abc"); rbTree.insert(4, "abc"); rbTree.insert(1, "foo"); rbTree.insert(0, "bar"); rbTree.insert(2, "bar"); const array = rbTree.toArrayPreOrder(); array is [Object, Object, Object, Object, Object] return an array of objects that contains key and value the key order is [3, 1, 0, 2, 4]
- toArrayPostOrder()
const rbTree = new RbTree(); rbTree.insert(3, "abc"); rbTree.insert(4, "abc"); rbTree.insert(1, "foo"); rbTree.insert(0, "bar"); rbTree.insert(2, "bar"); const array = rbTree.toArrayPostOrder(); array is [Object, Object, Object, Object, Object] the key order is [0, 2, 1, 4, 3] return an array of objects that contains key and value
- minNode()
const rbTree = new RbTree(); rbTree.insert(1, "foo"); rbTree.insert(2, "bar"); rbTree.insert(3, "bar"); const node = rbTree.minNode(); node is Object {key: 1, value: "foo"} return the smallest node value in the tree
- maxNode()
const rbTree = new RbTree(); rbTree.insert(1, "foo"); rbTree.insert(2, "bar"); rbTree.insert(3, "bar"); const node = rbTree.maxNode(); node is Object {key: 3, value: "bar"} return the largest node value in the tree
letter 'a' will be treated as 1
letter 'b' will be treated as 2
letter 'b' will be treated as 3
letter 'A' will be treated as 1 as well
letter 'B' will be treated as 2 as well
letter 'C' will be treated as 3 as well
a string like "abc" will be treated as 123
a string like "Abc" will be treated as 123
a string like "dc" will be treated as 41
rbTree.insert("id", 1001) => rbTree.insert(94, 1001); rbTree.insert("a", "foo") => rbTree.insert(1, "foo"); rbTree.insert("Am", "bar")=> rbTree.insert(113, "foo"); rbTree.insert("boy", "foo") => rbTree.insert(21525, "foo");
- future work
Better print format
Pass all linter
and more ...