# AVL Tree

The AVL Tree is a self-balancing binary search tree in which balancing operations take place based on the difference of height between the left and right subtrees. Such operations may occur during the insertion and deletion of keys performing recursive *rotate operations* to ensue that the difference between the heights of the left and right substrees is restricted to $[-1, 1]$.

Example of AVL Tree with balance factors shown in green.

AVL Trees are often compared with Red–Black Trees because both take $O(\log n)$ time for the basic operations. However, for lookup-intensive applications, AVL Trees are faster than Red–Black Trees because they are more strictly balanced. Similar to Red–Black Trees, AVL Trees are height-balanced.

Computational complexity for common operations using an AVL Tree

Operation | Average Case | Worst Case |
---|---|---|

Space | $\Theta(n)$ | $O(n)$ |

Search | $\Theta(\log n)$ | $O(\log n)$ |

Insertion | $\Theta(\log n)$ | $O(\log n)$ |

Deletion | $\Theta(\log n)$ | $O(\log n)$ |

# Constructors

`DataStructures.AVLTree`

— Type`AVLTree{T}`

Construct new `AVLTree`

with keys of type `T`

.

**Example**

```
julia> tree = AVLTree{Int64}()
AVLTree{Int64}(nothing, 0)
```

# Usage

The `AVLTree`

type implements the following methods:

`delete!(tree::AVLTree{K}, k::K) where K`

`in(key, tree::AVLTree)`

`getindex(tree::AVLTree{K}, ind::Integer) where K`

`haskey(tree::AVLTree{K}, k::K) where K`

`push!(tree::AVLTree{K}, k) where K`

`sorted_rank(tree::AVLTree{K}, key::K) where K`

`Base.delete!`

— Method`delete!(tree::AVLTree{K}, k::K) where K`

Delete key `k`

from `tree`

AVL tree.

`Base.getindex`

— Method`getindex(tree::AVLTree{K}, ind::Integer) where K`

Considering the elements of `tree`

sorted, returns the `ind`

-th element in `tree`

. Search operation is performed in $O(\log n)$ time complexity.

**Examples**

```
julia> tree = AVLTree{Int}()
AVLTree{Int64}(nothing, 0)
julia> for k in 1:2:20
push!(tree, k)
end
julia> tree[4]
7
julia> tree[8]
15
```

`Base.haskey`

— Method`haskey(tree::AVLTree{K}, k::K) where K`

Verify if AVL tree `tree`

contains the key `k`

. Analogous to `in(key, tree::AVLTree)`

.

`Base.in`

— Method`in(key, tree::AVLTree)`

`In`

infix operator for `key`

and `tree`

types. Analogous to `haskey(tree::AVLTree{K}, k::K) where K`

.

`Base.length`

— Method`length(tree::AVLTree)`

Return number of elements in AVL tree `tree`

.

`Base.push!`

— Method`push!(tree::AVLTree{K}, key) where K`

Insert `key`

in AVL tree `tree`

.

`DataStructures.left_rotate`

— Method`left_rotate(node_x::AVLTreeNode)`

Performs a left-rotation on `node_x`

, updates height of the nodes, and returns the rotated node.

`DataStructures.minimum_node`

— Method`minimum_node(tree::AVLTree, node::AVLTreeNode)`

Returns the AVLTreeNode with minimum value in subtree of `node`

.

`DataStructures.right_rotate`

— Method`right_rotate(node_x::AVLTreeNode)`

Performs a right-rotation on `node_x`

, updates height of the nodes, and returns the rotated node.

`DataStructures.sorted_rank`

— Method`sorted_rank(tree::AVLTree{K}, key::K) where K`

Returns the rank of `key`

present in the `tree`

, if it present. A `KeyError`

is thrown if `key`

is not present.

**Examples**

```
julia> tree = AVLTree{Int}();
julia> for k in 1:2:20
push!(tree, k)
end
julia> sorted_rank(tree, 17)
9
```