"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"

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)

	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.

open allclose all

A new "AVLTree" can be created with CreateDataStructure:

Insert a number of values:

A visualization of the data structure can be generated:

A new "AVLTree" can be created with CreateDataStructure:

Information about the data structure ds:

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

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:

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:

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:

Top