"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 f	time: O(n)
	ds["Copy"]	return a copy of ds	time: O(n)
	ds["Delete",x]	delete x from ds	time: O(log n)
	ds["DeleteAll"]	delete all elements from ds	time: O(n)
	ds["DropMax"]	remove the maximum element of ds and return it	time: O(log n)
	ds["DropMin"]	remove the minimum element of ds and return it	time: O(log n)
	ds["Elements"]	return a list of the elements of ds	time: O(n)
	ds["EmptyQ"]	True, if ds has no nodes	time: O(1)
	ds["FreeQ",x]	True, if ds does not contain x	time: O(log n)
	ds["InOrderScan",f]	perform an in-order scan of ds, passing the data in each node to f	time: O(n)
	ds["Insert",x]	insert x into ds	time: O(log n)
	ds["Length"]	the number of nodes in ds	time: O(1)
	ds["Max"]	return the maximum element of ds	time: O(log n)
	ds["MemberQ",x]	True, if ds contains x	time: O(log n)
	ds["Min"]	return the minimum element of ds	time: O(log n)
	ds["PostOrderScan",f]	perform a post-order scan of ds, passing the data in each node to f	time: O(n)
	ds["PreOrderScan",f]	perform a pre-order scan of ds, passing the data in each node to f	time: O(n)
	ds["Visualization"]	return a visualization of ds	time: O(n)

The following functions are also supported:

	ds_i===ds_j	True, if ds_i equals ds_j
	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 allclose all

Basic Examples (1)Summary of the most common use cases

A new "AVLTree" can be created with CreateDataStructure:

In[1]:=1

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-n9py1n

Out[1]=1

Insert a number of values:

In[2]:=2

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-tnm4iz

A visualization of the data structure can be generated:

In[3]:=3

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-uvwa1b

Out[3]=3

Scope (4)Survey of the scope of standard use cases

Information (1)

A new "AVLTree" can be created with CreateDataStructure:

In[1]:=1

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-fip55w

Out[1]=1

Information about the data structure ds:

In[2]:=2

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-5du3om

Out[2]=2

Balancing (1)

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

In[1]:=1

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-dhwpn9

Out[1]=1

A modification that would break the balanced property causes rebalancing:

In[2]:=2

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-in3um8

Out[2]=2

Now an insertion on the right does not require rebalancing:

In[3]:=3

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-y0dbmb

Out[3]=3

Removing from the left requires rebalancing:

In[4]:=4

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-rc50ss

Out[4]=4

Ordering (1)

Create a new tree and insert 30 random numbers:

In[1]:=1

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-mndpfn

Out[1]=1

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:

In[2]:=2

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-0ydqj6

Out[2]=2

Ordering Function (1)

Create an empty tree with a custom ordering function:

In[1]:=1

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-7kiomz

Insert some data:

In[2]:=2

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-szouu5

The elements in the tree:

In[3]:=3

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-efcbgx

Out[3]=3

Remove and return the largest element:

In[4]:=4

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-tb71mo

Out[4]=4

The largest element has been removed:

In[5]:=5

✖

https://wolfram.com/xid/0x9f1ydh1ken2z3jngqhwkp4-sdd5ll

Out[5]=5

Top