Go to Latest
class RedBlackTree
import { RedBlackTree } from "https://deno.land/std@0.167.0/collections/red_black_tree.ts";

A red-black tree. This is a kind of self-balancing binary search tree. The values are in ascending order by default, using JavaScript's built-in comparison operators to sort the values.

Red-Black Trees require fewer rotations than AVL Trees, so they can provide faster insertions and removal operations. If you need faster lookups, you should use an AVL Tree instead. AVL Trees are more strictly balanced than Red-Black Trees, so they can provide faster lookups.

Method Average Case Worst Case
find(value) O(log n) O(log n)
insert(value) O(log n) O(log n)
remove(value) O(log n) O(log n)
min() O(log n) O(log n)
max() O(log n) O(log n)

Examples

Example 1

import {
  ascend,
  descend,
  RedBlackTree,
} from "https://deno.land/std@0.167.0/collections/red_black_tree.ts";
import { assertEquals } from "https://deno.land/std@0.167.0/testing/asserts.ts";

const values = [3, 10, 13, 4, 6, 7, 1, 14];
const tree = new RedBlackTree<number>();
values.forEach((value) => tree.insert(value));
assertEquals([...tree], [1, 3, 4, 6, 7, 10, 13, 14]);
assertEquals(tree.min(), 1);
assertEquals(tree.max(), 14);
assertEquals(tree.find(42), null);
assertEquals(tree.find(7), 7);
assertEquals(tree.remove(42), false);
assertEquals(tree.remove(7), true);
assertEquals([...tree], [1, 3, 4, 6, 10, 13, 14]);

const invertedTree = new RedBlackTree<number>(descend);
values.forEach((value) => invertedTree.insert(value));
assertEquals([...invertedTree], [14, 13, 10, 7, 6, 4, 3, 1]);
assertEquals(invertedTree.min(), 14);
assertEquals(invertedTree.max(), 1);
assertEquals(invertedTree.find(42), null);
assertEquals(invertedTree.find(7), 7);
assertEquals(invertedTree.remove(42), false);
assertEquals(invertedTree.remove(7), true);
assertEquals([...invertedTree], [14, 13, 10, 6, 4, 3, 1]);

const words = new RedBlackTree<string>((a, b) =>
  ascend(a.length, b.length) || ascend(a, b)
);
["truck", "car", "helicopter", "tank", "train", "suv", "semi", "van"]
  .forEach((value) => words.insert(value));
assertEquals([...words], [
  "car",
  "suv",
  "van",
  "semi",
  "tank",
  "train",
  "truck",
  "helicopter",
]);
assertEquals(words.min(), "car");
assertEquals(words.max(), "helicopter");
assertEquals(words.find("scooter"), null);
assertEquals(words.find("tank"), "tank");
assertEquals(words.remove("scooter"), false);
assertEquals(words.remove("tank"), true);
assertEquals([...words], [
  "car",
  "suv",
  "van",
  "semi",
  "train",
  "truck",
  "helicopter",
]);

Constructors

new
RedBlackTree(compare?: (a: T, b: T) => number)

Properties

protected
root: RedBlackNode<T> | null

Methods

protected
removeFixup(parent: RedBlackNode<T> | null, current: RedBlackNode<T> | null)
insert(value: T): boolean

Adds the value to the binary search tree if it does not already exist in it. Returns true if successful.

remove(value: T): boolean

Removes node value from the binary search tree if found. Returns true if found and removed.

Static Methods

from<T>(collection: ArrayLike<T> | Iterable<T> | RedBlackTree<T>): RedBlackTree<T>

Creates a new red-black tree from an array like or iterable object.

from<T>(collection: ArrayLike<T> | Iterable<T> | RedBlackTree<T>, options: { Node?: RedBlackNode; compare?: (a: T, b: T) => number; }): RedBlackTree<T>
from<T, U, V>(collection: ArrayLike<T> | Iterable<T> | RedBlackTree<T>, options: { compare?: (a: U, b: U) => number; map: (value: T, index: number) => U; thisArg?: V; }): RedBlackTree<U>