"RedBlackTree" (Data Structure)

"RedBlackTree"

represents a mutable, self-balancing binary search tree, where the values stored at each node are general expressions.

Details

  • A binary search tree stores data in a sorted form that allows quick insertion operations. A self-balancing binary search tree makes sure that the heights of all branches are balanced; this helps operations to be efficient despite arbitrary insertions and deletions.
  • CreateDataStructure[ "RedBlackTree"]create a new empty "RedBlackTree"
    CreateDataStructure["RedBlackTree",v{l,r}]create a new "RedBlackTree" with specified initial value v and specified left and right children
    CreateDataStructure["RedBlackTree",tree,p]create a new "RedBlackTree" with specified tree and ordering function p
    Typed[x,"RedBlackTree"]give x the type "RedBlackTree"
  • For a data structure of type "RedBlackTree", the following operations can be used:
  • ds["BreadthFirstScan",f]perform a breadth-first scan of ds, passing the data in each node to ftime: O(n)
    ds["Copy"]return a copy of dstime: O(n)
    ds["Delete",x]delete x from dstime: O(log n)
    ds["DeleteAll"]delete all elements from dstime: O(n)
    ds["DropMax"]remove the maximum element of ds and return ittime: O(log n)
    ds["DropMin"]remove the minimum element of ds and return ittime: O(log n)
    ds["Elements"]return a list of the elements of dstime: O(n)
    ds["EmptyQ"]True, if ds has no nodestime: O(1)
    ds["FreeQ",x]True, if ds does not contain xtime: O(log n)
    ds["InOrderScan",f]perform an in-order scan of ds, passing the data in each node to ftime: O(n)
    ds["Insert",x]insert x into dstime: O(log n)
    ds["Length"]the number of nodes in dstime: O(1)
    ds["Max"]return the maximum element of dstime: O(log n)
    ds["MemberQ",x]True, if ds contains xtime: O(log n)
    ds["Min"]return the minimum element of dstime: O(log n)
    ds["PostOrderScan",f]perform a post-order scan of ds, passing the data in each node to ftime: O(n)
    ds["PreOrderScan",f]perform a pre-order scan of ds, passing the data in each node to ftime: O(n)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    FullForm[ds]the full form of ds
    Information[ds]information about ds
    InputForm[ds]the input form of ds
    Normal[ds]convert ds to a normal expression
  • The order of two elements is determined by the order function p, following the interpretation given by the order function of Sort. The default order function is Order.
  • The "RedBlackTree" maintains a balanced property that the height of each subtree never differs by more than 1.
  • If the initial tree specification is Null, an empty "RedBlackTree" is created.

Examples

open allclose all

Basic Examples  (1)

A new "RedBlackTree" can be created with CreateDataStructure:

Insert a number of values:

A visualization of the data structure can be generated:

Scope  (4)

Information  (1)

A new "RedBlackTree" can be created with CreateDataStructure:

Information about the data structure ds:

Balancing  (1)

"RedBlackTree" maintains a balance by using a coloring property, typically shown as red or black:

A modification that would break the balanced property causes rebalancing:

Now an insertion on the right does not require rebalancing:

Removing from the left requires rebalancing:

Ordering  (1)

Create a new tree and insert 30 random numbers:

This makes an in-order scan over the tree. Since it is sorted, the elements are visited in sorted order, as shown in this example:

Ordering Function  (1)

Create an empty tree with a custom ordering function:

Insert some data:

The elements in the tree:

Remove and return the largest element:

The largest element has been removed: