AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. I will try to implement it and log in this article. You can find the source code in here.

## Node

Evey Node have five member properties. `balFactor_`

is the balance factor that equal to -1, 0, 1 representing the left sub-tree 1 layer taller than right sub-tree, tall equally and converse, respectively.

1 | `template <typename T>` |

## Iterator

function `increment()`

find the last node that is larger than current node, corresponding `operator++`

. function `decrement()`

find the last node that is smaller than current node, corresponding `operator--`

.

1 | `template <typename T>` |

## Tree Property

### header

Let us see a tree without value node, and the only node called `header`

.

- parent: link to root if exist
- left: also call leftmost, link to the most left node of tree
- right: also call leftmost, link to the most right node of tree
- balFactor: always equal to -2 (special)

### root

root is the top node of a tree.

- parent: link to header
- left: link to nullptr if no node
- right: link to nullptr if no node

1 | `NodePtr& root() const { return header_->parent_; }` |

### Multi Node

See a tree with three nodes. The children of leaf are nullptr.

### Balance

AVL Tree (Adelson-Velskii-Landis tree) is a kind of balanced binary search tree with the demand that the difference heigth of the left and right tree cannot over 1.

the sub-tree or tree with a root node whose balance factor = -2 or = 2 is an unbalance tree. We can rebalance it by rotation.

## Rotation

### Left Rotation

When the right sub-tree is taller, we need to rotate left to shorten it.

1 | `/*` |

### Right Rotation

When the left sub-tree is taller, we need to rotate right to shorten it.

1 | `/*` |

### Left Right Rotation

As for Double rotation, we need to look four layers of tree. When the top node of tree or sub-tree has 2 layers taller left sub-tree, and the left sub-tree have a taller right sub-tree,

- we need to do a left rotation to make the latter right sub-tree shorter firstly
- and then do a right rotation to make the former left sub-tree shorter shorter secondly

1 | `/*` |

### Right Left Rotation

As for Double rotation, we need to look four layers of tree. When the top node of tree or sub-tree has 2 layers taller right sub-tree, and the right sub-tree have a taller left sub-tree,

- we need to do a right rotation to make the latter left sub-tree shorter firstly
- and then do a left rotation to make the former right sub-tree shorter shorter secondly.

1 | `/*` |

## Insertion

When we insert a node to tree, we consider three section:

- Ensuring insert to the child of the leaf
- Considering the parent of new node is header, means that the new node is root, and that we need to add the relation between header and root, including the parent of them each other and the leftmost or rightmost.
- Rebalance. We consider the parent of x at the start, and
**percolate up**the path from leaf to root. We at least do zero or once rotation for certein.

1 | `// [x] is the new node to insert` |

We insert a not-allow-replaced key with three considerations:

- insert to the left of leftmost
- insert to the right of y if just bigger than y
- insert to the left of y if just bigger than decrement(y)

1 | `pair<iterator, bool> insertUnique(const Val& v) {` |

Insertion of allowing equal key.

1 | `iterator insertEqual(const Val& v) {` |

## Deletion

When we delete a node from a tree, we consider three sections:

- Find the successor to replace the position of deleted node.
- If the node to be deleting has only one child, the successor is the child.
- If it has two children, the successor is the last node that is larger than it.

- The replacement action including three steps:
- Disconnecting to its children and make the successor links to them
- Suturing the wound caused by successor moved
- Its parent link to the successor

- Rebalance. We will percolate up and rotate multi times probably until
- the balFactor of certain node is 0, we just change its balFactor to -1 or 1 (depending the deleted node in right or left).
- the balFactor of certain node after rotation becomes from 1 to -1 or from -1 to 1.

1 | `// erase node [z] and return the deleted node` |

Nothing additional thing If need to delete a known node.

1 | `void erase(iterator pos) {` |

Deleting a key that probably exists in multi node, we need to find the range and delete them one by one.

lowerBound() can find the last node that greater than or equal to a certein key. And upperBound() find the last node that greater than a certein key. So the deleted range is [lowerBound(), upperBound()).

1 | `size_type erase(const Key& k) {` |

## Find

Using lowerBound, we can find the last node that greater than or equal to a certein key, if no, return the header node. And we only need the node with the same key.

1 | `iterator lowerBound(const Key& k) const {` |

## Comments