Like other balanced binary search trees, WAVL trees can handle insertion, deletion, and search operations in time O(log n) per operation.

is the golden ratio), while red–black trees have larger maximum height,

[1][2] WAVL trees were introduced by Haeupler, Sen & Tarjan (2015).

[2] Different binary search trees have different algorithms for insert/delete and balancing algorithms, making it difficult for a systematic study.

The authors of Haeupler, Sen & Tarjan (2015) introduce the rank balanced trees framework for unifying the study of binary search tree by defining the rank binary tree, and each binary search tree follows by specific constraints applied to the rank function.

Note that the framework doesn't specify the algorithms in which these trees are implemented.

, and such a node is called an i-child if the rank difference is i.

An internal node stores a data item, and is linked to its parent (except for a designated root node that has no parent) and to exactly two children in the tree, the left child and the right child.

An external node carries no data, and has a link only to its parent in the tree.

The external nodes form the leaves of the tree.

[3] The data items are arranged in the tree in such a way that an inorder traversal of the tree lists the data items in sorted order.

Unlike in AVL trees, where ranks are defined to be the same as nodes' heights, ranks do not always equal to heights in WAVL trees.

The ranks are required to obey the following properties:[1][2] Searching for a key k in a WAVL tree is much the same as in any balanced binary search tree data structure.

[6] If the search stops at an internal node, the key k has been found.

The rebalancing step can be performed either top-down or bottom-up,[2] but the bottom-up version of rebalancing is the one that most closely matches AVL trees.

If the rank-difference for that child and node is 2, rotate to move node up in the tree and parent down, then demote parent - reduce its rank by adjusting the rank-differences around it - and balance is restored.

Promote the child, demote the node and parent, and balance is restored.

If the rank-difference between node and parent has grown from 1 to 2, balance is restored.

Overall, a deletion consists of a search downward to find a node with an external child, the removal of a constant number of new nodes, a logarithmic number of rank changes, and a constant number of tree rotations.

[1][2] It is worthwhile to compare the result of a delete which would cause rotations at multiple levels in an AVL tree with the rotation and rank changes performed in a WAVL tree.

Each search, insertion, or deletion in a WAVL tree involves following a single path in the tree and performing a constant number of steps for each node in the path.

In a WAVL tree with n items that has only undergone insertions, the maximum path length is

If both insertions and deletions may have happened, the maximum path length is

Therefore, in either case, the worst-case time for each search, insertion, or deletion in a WAVL tree with n data items is O(log n).

Additionally, after finding a node for insertion and deletion, the amortized complexity of the tree restructuring operations is constant.

Adding or deleting the node itself is constant time, the amount of rotations is always at most constant and it can be shown that the total amount of rank changes in the nodes is linear in the number of both insertions and deletions.

This is because rank is not strictly equal to height in WAVL tree.

This greater flexibility in ranks also leads to a greater flexibility in structures: some WAVL trees cannot be made into AVL trees even by modifying their ranks, because they include nodes whose children's heights differ by more than one.

In particular this implies that a WAVL tree created only through insertions has height at most

[2] A red–black tree is a balanced binary search tree in which each node has a color (red or black), satisfying the following properties: Red–black trees can equivalently be defined in terms of a system of ranks, stored at the nodes, satisfying the following requirements (different than the requirements for ranks in WAVL trees): The equivalence between the color-based and rank-based definitions can be seen, in one direction, by coloring a node black if its parent has greater rank and red if its parent has equal rank.