RedBlackTree | /collections/red_black_tree.ts | std@0.181.0

class RedBlackTree

import { RedBlackTree } from "https://dotland.deno.dev/std@0.181.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.181.0/collections/red_black_tree.ts";
import { assertEquals } from "https://deno.land/std@0.181.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)

Type Parameters

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>