Provides a basic implementation of weight-balanced binary trees.

The WBTrees library contains classes as follows:

• A list by a weight-balanced binary tree, with all O(log n) basic operations
  • WBList<T>
• A set and a map by weight-balanced binary search trees, which can be accessed by index in O(log n) time
  • WBSet<T>
  • WBMultiSet<T>
  • WBMap<TKey, TValue>
  • WBMultiMap<TKey, TValue>

All these trees are constructed from Node<T> objects.

See Wiki for more information.
This library is written in C#. You are welcome to port this to other languages.

Provides the WBList<T> class as a list with all O(log n) basic operations.
You can also use a WBList<T> as a (high-grade) double-ended queue (deque).

The following table compares time complexities of System.Collections.Generic.List<T> and WBList<T>:

Provides the WBSet<T>, WBMultiSet<T>, WBMap<TKey, TValue> and WBMultiMap<TKey, TValue> classes, which can be accessed by index in O(log n) time. All these classes are derived from the WBTreeBase<T> class.
You can also use a WBMultiSet<T> or a WBMultiMap<TKey, TValue> as a priority queue with stable sorting or a double-ended priority queue.

The following table compares time complexities of System.Collections.Generic.SortedSet<T> and WBSet<T>:

Both WBList<T> and WBTreeBase<T> are weight-balanced binary trees (not necessarily searchable by items). The Node<T> class contains the Count property that contributes to both self-balancing and fast access by index (order).

• .NET 5
• .NET Standard 2.0
  • .NET Core 2.0, .NET Framework 4.6.1, etc.

The WBTrees library is published to NuGet Gallery. Install the NuGet package via Visual Studio, etc.

You can also download a single source file here for competitive programming, etc.

See Usage on Wiki for coding.

• v1.0.4 The first release.