Created
April 24, 2023 08:14
-
-
Save Vilkina/11fe5be2de436f58a365d18793cd607d to your computer and use it in GitHub Desktop.
Red-Black Tree in JavaScript with ES6 syntax
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node { | |
constructor(key, value, color, left = null, right = null) { | |
Object.assign(this, { key, value, color, left, right }); | |
} | |
async insert(key, value) { | |
const cmp = key < this.key ? "left" : "right"; | |
const child = this[cmp]; | |
const newChild = child === null ? new Node(key, value, true) : await child.insert(key, value); | |
return newChild.color && this.color ? this.fixup(newChild, cmp) : new Node(this.key, this.value, this.color, cmp === "left" ? newChild : this.left, cmp === "right" ? newChild : this.right); | |
} | |
fixup(child, cmp) { | |
const otherCmp = cmp === "left" ? "right" : "left"; | |
const sibling = this[otherCmp]; | |
return sibling !== null && sibling.color ? new Node(sibling.key, sibling.value, true, new Node(this.key, this.value, false, this.left, sibling.left), new Node(child.key, child.value, false, sibling.right, child.right)) : new Node(this.key, this.value, false, cmp === "left" ? child : this.left, cmp === "right" ? child : this.right); | |
} | |
} | |
export class ImmutableRedBlackTree { | |
constructor(root = null) { | |
this.root = root; | |
} | |
async insert(key, value) { | |
const newRoot = this.root === null ? new Node(key, value, false) : await this.root.insert(key, value); | |
return new ImmutableRedBlackTree(new Node(newRoot.key, newRoot.value, false)); | |
} | |
} |
Author
Vilkina
commented
Apr 24, 2023
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment