AvlTree

AvlTree Class

Namespace: Unity_Tools.Collections

Represents an avl-tree implementation with generic keys and values.

[System.Serializable]
public class AvlTree<TKey, TValue> 
    where TKey : System.IComparable<TKey>

Type parameters

TKey
The type of the keys in the avl-tree.

TValue
The type of the values in the avl-tree.

Examples

The following code example creates a new avl tree for vectors using strings as keys.
Then it adds a few key-value pairs using the Add method.
It tests whether the direction argument is part of the collection using ContainsKey.
Finally, it extracts the vector that matches the direction argument using the indexer and returns it.

The example could be implemented way more efficiently by caching the avl-tree or using a switch-case statement.
For the sake of the example, it was kept simple.

// Returns the vector that matches the direction string.
public Vector3 GetVector(string direction)
{
    // Create a new instance of the avl tree
    AvlTree<string, Vector3> points = new AvlTree<string, Vector3>();

    // Add all supported vectors
    points.Add("zero", new Vector3(0, 0, 0));
    points.Add("one", new Vector3(1, 1, 1));
    points.Add("left", new Vector3(-1, 0, 0));
    points.Add("right", new Vector3(1, 0, 0));
    points.Add("forward", new Vector3(0, 0, 1));
    points.Add("back", new Vector3(0, 0, -1));
    points.Add("up", new Vector3(0, 1, 0));
    points.Add("down", new Vector3(0, -1, 0));

    // Make sure that the direction string is supported.
    if (!points.ContainsKey(direction))
    {
        throw new ArgumentException("The direction string is not recognized.", nameof(direction));
    }

    // Get and return the vector matching the direction string.
    return points[direction];
}

Remarks

Performance wise, it's better to use a System.Collections.Generic.Dictionary<TKey, TValue>, but this data structure can be used as a template implementation for custom avl-trees.

Constructors

• AvlTree<TKey, TValue>()
  Creates a new instance of the AvlTree type.

Properties

• Count : int
  Gets the amount of key-values pairs stored in this tree.
• Item[TKey] : TValue
  Gets the value that belongs to the key.

Methods

• Add(TKey, TValue) : bool
  Tries to add the key-value pair to the collection.
• ContainsKey(TKey) : bool
  Gets a value indicating whether the given key exists in the collection.
• Remove(TKey) : bool
  Tries to remove the key and its associated value from the collection.
• SetValue(TKey, TValue) : void
  Adds the value or replaces an existing value with the new value for the corresponding key.
• TryGet(TKey, out TValue) : bool
  Tries to get the value that belongs to the given key.

Thread safety

The AvlTree supports multiple concurrent readers.
When the AvlTree is being used in a multi threaded read and write environment, proper locking must be applied.