In computer science, a WAVL tree or weak AVL tree is a self-balancing binary search tree. WAVL trees are named after AVL trees, another type of balanced search tree, and are closely related both to AVL trees and red–black trees, which all fall into a common framework of rank balanced trees. Like other balanced binary search trees, WAVL trees can handle insertion, deletion, and search operations in time O(log n) per operation. WAVL trees are designed to combine some of the best properties of both AVL trees and red–black trees. One advantage of AVL trees over red–black trees is being more balanced: they have height at most log φ n ≈ 1.44 log 2 n {\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n} (for a tree with n data items, where φ {\displaystyle \varphi } is the golden ratio), while red–black trees have larger maximum height, 2 log 2 n {\displaystyle 2\log _{2}n} . If a WAVL tree is created using only insertions, without deletions, then it has the same small height bound that an AVL tree has. On the other hand, red–black trees have the advantage over AVL trees in lesser restructuring of their trees. In AVL trees, each deletion may require a logarithmic number of tree rotation operations, while red–black trees have simpler deletion operations that use only a constant number of tree rotations. WAVL trees, like red–black trees, use only a constant number of tree rotations, and the constant is even better than for red–black trees. WAVL trees were introduced by Haeupler, Sen & Tarjan (2015). The same authors also provided a common view of AVL trees, WAVL trees, and red–black trees as all being a type of rank-balanced tree.
The rank balanced trees framework 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. A rank binary tree is a binary tree where each node x is associated with a rank r(x). By convention, empty node has rank -1. For a node x that is not the root, the rank difference is r ( p ( x ) ) − r ( x ) {\displaystyle r(p(x))-r(x)} , and such a node is called an i-child if the rank difference is i. A node is of type i , j {\displaystyle i,j} if the rank difference of its left child and right child is i and j (disregarding ordering). With that, we can define additional rules, which correspond to different trees:
AVL rule, which corresponds to AVL tree: each node is of type 1,1 or 1,2. 2-3 rule, which corresponds to the binarized 2-3 tree: each node is of type 0,1 or 1,1, and no parent of a 0-child is a 0-child. Red black rule, which corresponds to Red-black tree: all rank differences are 0 or 1, and no parent of a 0-child is a 0-child. Note that the red-black rule generalizes the 2-3 rule by allowing for 0,0 type node. So far all these rules are symmetric for the left node and the right node. By breaking such symmetries, it gives rise to other rules:
Right-Leaning Two-Three Rule, which corresponds to the right leaning binarized 2-3 tree: Every node is 1,1 or 0,1, no parent of a 0-child is a 0-child, and no 0-child is left. Left-Leaning Two-Three Rule, which corresponds to the left leaning binarized 2-3 tree: Every node is 1,1 or 0,1, no parent of a 0-child is a 0-child, and no 0-child is right. Right-leaning red-black rule, which corresponds to Reft-leaning red–black tree: no parent of a 0-child is a 0-child, and no 0-child of a 0,1-node is left. Left-leaning red-black rule, which corresponds to Left-leaning red–black tree: all rank differences are 0 or 1, no parent of a 0-child is a 0-child, and no 0-child of a 0,1-node is right. The weak AVL tree is defined by the weak AVL rule:
Weak AVL rule: all rank differences are 1 or 2, and all leaf nodes have rank 0. Note that weak AVL tree generalizes the AVL tree by allowing for 2,2 type node. A simple proof shows that a weak AVL tree can be colored in a way that represents a red-black tree. So in a sense, weak AVL tree combines the properties of AVL tree and red-black tree.
Definition As with binary search trees more generally, a WAVL tree consists of a collection of nodes, of two types: internal nodes and external nodes. 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. These nodes are arranged to form a binary tree, so that for any internal node x the parents of the left and right children of x are x itself. The external nodes form the leaves of the tree. 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. What distinguishes WAVL trees from other types of binary search tree is its use of ranks. These are numbers, associated with each node, that provide an approximation to the distance from the node to its farthest leaf descendant. 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 rank difference of node x is defined as the difference between the rank of x's parent and the rank of x. The ranks are required to obey the following properties:
… excerpt ends here. Continue reading the full article.
