WOLFRAM

Wolfram Language & System Documentation Center

"AVLTree" (Data Structure)

"AVLTree"

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[ "AVLTree"]create a new empty "AVLTree"
    CreateDataStructure["AVLTree",v{l,r}]create a new "AVLTree" with specified initial value v and specified left and right children
    CreateDataStructure["AVLTree",tree,p]create a new "AVLTree" with specified tree and ordering function p
    Typed[x,"AVLTree"]give x the type "AVLTree"
  • For a data structure of type "AVLTree", 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 "AVLTree" 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 "AVLTree" is created.

Examples

open all close all

Basic Examples  (1)

A new "AVLTree" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["AVLTree"]

Insert a number of values:

Wolfram Language code: ds["Insert", 10]; ds["Insert", 15]; ds["Insert", 5];

A visualization of the data structure can be generated:

Wolfram Language code: ds["Visualization"]

Scope  (4)

Information  (1)

A new "AVLTree" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["AVLTree", f[1]]

Information about the data structure ds:

Wolfram Language code: Information[ds]

Balancing  (1)

"AVLTree" maintains a balance where the height of each subtree never differs by more than 1:

Wolfram Language code: ds = CreateDataStructure["AVLTree"]; ds["Insert", 0]; ds["Insert", 10]; ds["Visualization"]

A modification that would break the balanced property causes rebalancing:

Wolfram Language code: ds["Insert", 15]; ds["Visualization"]

Now an insertion on the right does not require rebalancing:

Wolfram Language code: ds["Insert", 20]; ds["Visualization"]

Removing from the left requires rebalancing:

Wolfram Language code: ds["Remove", 0]; ds["Visualization"]

Ordering  (1)

Create a new tree and insert 30 random numbers:

Wolfram Language code: ds = CreateDataStructure["AVLTree"]; Scan[ds["Insert", #]&, RandomInteger[{0, 500}, 30]]; ds["Visualization"]

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:

Wolfram Language code: arr = CreateDataStructure["DynamicArray"];ds["InOrderScan", arr["Append", #]&]; arr//Normal

Ordering Function  (1)

Create an empty tree with a custom ordering function:

Wolfram Language code: ds = CreateDataStructure["AVLTree", Null, Order[First[#1], First[#2]]&];

Insert some data:

Wolfram Language code: data = Table[{RandomInteger[1000], f[i]}, {i, 10}]; Scan[ds["Insert", #]&, data];

The elements in the tree:

Wolfram Language code: ds["Elements"]

Remove and return the largest element:

Wolfram Language code: ds["DropMax"]

The largest element has been removed:

Wolfram Language code: ds["Elements"]