7 Red-Black Trees

8.13.0.4

7 Red-Black Trees🔗ℹ

package: pfds

Red-Black Tree is a binary search tree in which every node is colored either red or black. The red black trees follow two balance invariants

No red node has a red child.

Every path from root to an empty node has the same number of black nodes.

The above two invarients help in balancing the tree. All the operations member?, insert and delete have worst case running time of O(log(n))

syntax
(RedBlackTree A)

A red-black tree of type A.

procedure
(redblacktree comp a ...) → (RedBlackTree A)
comp : (A A -> Boolean)
a : A

Function redblacktree creates a Red-Black Tree with the given inputs.

Example:

> (redblacktree < 1 2 3 4 5)
- : #(struct:RBTree
((-> Positive-Byte Positive-Byte Boolean)
(U (RBNode Positive-Byte) Null)))
#<RBTree>

In the above example, the red black tree obtained will have 2 as its root and < as the comparison function.

procedure
(empty? rbt) → Boolean
rbt : (RedBlackTree A)

Function empty? checks if the given red black tree is empty or not.

Examples:

> (empty? (redblacktree < 1 2 3 4 5 6))
- : Boolean
#f
> (empty? (redblacktree <))
- : Boolean
#t

procedure
(insert a rbt) → (RedBlackTree A)
a : A
rbt : (RedBlackTree A)

Function insert takes an element and a red black tree and inserts the given element into the red black tree.

Example:

> (insert 10 (redblacktree < 1 2 3 4 5 6))
- : #(struct:RBTree
((-> Positive-Byte Positive-Byte Boolean)
(U (RBNode Positive-Byte) Null)))
#<RBTree>

In the above example, insert adds the 10 to (redblacktree < 1 2 3 4 5 6).

procedure
(root rbt) → A
rbt : (RedBlackTree A)

Function root takes a red black tree and returns the root of the given tree.

Examples:

> (root (redblacktree < 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Byte]
2
> (root (redblacktree <))
root: given tree is empty

In the above example, (root (redblacktree < 1 2 3 4 5 6)), returns 2 which is the root of (redblacktree < 1 2 3 4 5 6).

procedure
(member? rbt) → Boolean
rbt : (RedBlackTree A)

Function member? takes an element and a red black tree and checks if the given element is a member of the tree or not.

Examples:

> (member? 5 (redblacktree < 1 2 3 4 5 6))
- : Boolean
#t
> (member? 10 (redblacktree < 1 2 3 4 5 6))
- : Boolean
#f

procedure
(delete-root rbt) → (RedBlackTree A)
rbt : (RedBlackTree A)

Function delete-root takes a red black tree and deletes the root element of the given tree.

Examples:

> (delete-root (redblacktree < 1 2 3 4 5 6))
- : #(struct:RBTree
((-> Positive-Byte Positive-Byte Boolean)
(U (RBNode Positive-Byte) Null)))
#<RBTree>
> (delete-root (redblacktree <))
delete-root: given tree is empty

In the above example, (delete-root rbtree), delete the root of (redblacktree < 1 2 3 4 5 6) which happens to be 2 in this tree.

procedure
(delete elem rbt) → (RedBlackTree A)
elem : A
rbt : (RedBlackTree A)

Function delete takes an element and red black tree and deletes the given element in the tree if the element is in the tree else throws an error.

Examples:

> (delete 5 (redblacktree < 1 2 3 4 5 6))
- : #(struct:RBTree
((-> Positive-Byte Positive-Byte Boolean)
(U (RBNode Positive-Byte) Null)))
#<RBTree>
> (delete 10 (redblacktree < 1 2 3 4 5 6))
delete: given key not found in the tree

In the above example, (delete 5 (redblacktree < 1 2 3 4 5 6)), deletes 5 in (redblacktree < 1 2 3 4 5 6).

procedure
(redblacktree->list rbt) → (Listof A)
rbt : (RedBlackTree A)

Function redblacktree->list takes a red black tree and returns a list of all the elements in the given red black tree.

Example:

> (redblacktree->list (redblacktree > 1 2 3 4 5))
- : (Listof Positive-Byte)
'(2 4 3 5 1)

procedure
(map comparer func rbt1 rbt2 ...) → (RedBlackTree A)
  comparer : (C C -> Boolean)
  func : (A B ... B -> C)
  rbt1 : (RedBlackTree A)
  rbt2 : (RedBlackTree B)

Function map is similar to map for lists.

Examples:

> (redblacktree->list (map < add1 (redblacktree < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(4 6 3 5 2 7)
> (redblacktree->list (map < * (redblacktree < 1 2 3 4 5 6)
(redblacktree < 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(9 25 4 16 1 36)

procedure
(fold func init rbt1 rbt2 ...) → C
  func : (C A B ... B -> C)
  init : C
  rbt1 : (RedBlackTree A)
  rbt2 : (RedBlackTree B)

Function fold is similar to foldl or foldr

fold currently does not produce correct results when the given function is non-commutative.

Examples:

> (fold + 0 (redblacktree < 1 2 3 4 5 6))
- : Integer [more precisely: Nonnegative-Integer]
21
> (fold * 1 (redblacktree < 1 2 3 4 5 6) (redblacktree < 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Integer]
518400

procedure
(filter func rbt) → (RedBlackTree A)
func : (A -> Boolean)
rbt : (RedBlackTree A)

Function filter is similar to filter.

Examples:

> (define rbt (redblacktree < 1 2 3 4 5 6))
> (redblacktree->list (filter (λ: ([x : Integer]) (> x 5)) rbt))
- : (Listof Positive-Byte)
'(6)
> (redblacktree->list (filter (λ: ([x : Integer]) (< x 5)) rbt))
- : (Listof Positive-Byte)
'(3 2 1 4)
> (redblacktree->list (filter (λ: ([x : Integer]) (<= x 5)) rbt))
- : (Listof Positive-Byte)
'(3 2 4 1 5)

procedure
(remove func rbt) → (RedBlackTree A)
func : (A -> Boolean)
rbt : (RedBlackTree A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (redblacktree->list (remove (λ: ([x : Integer]) (> x 5))
                      (redblacktree < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(3 2 4 1 5)
> (redblacktree->list (remove (λ: ([x : Integer]) (< x 5))
                      (redblacktree < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(5 6)
> (redblacktree->list (remove (λ: ([x : Integer]) (<= x 5))
                      (redblacktree < 1 2 3 4 5 6)))
- : (Listof Positive-Byte)
'(6)

1	Queues
2	Deques
3	Heaps
4	Random Access Lists
5	VList
6	Streams
7	Red-Black Trees
8	Tries
9	Treap