<commit_before># Balanced Binary Search Tree

A balanced binary search tree is <commit_msg>Add trees/balanced-binary-search-tree article<commit_after># Balanced Binary Search Tree

A balanced binary search tree is a tree such that at any given node, the `size` 
of the `left` subtree compared to the `size` of the `right` subtree differs by 
at most 1. In addition, we would want a self-balancing binary search tree,
which is a balanced binary seach tree with the built in capability to correct
imbalances in tree.

The primary motivation for a balanced binary search tree stems from the key 
problem with a regular binary search tree (more can be read on the article on 
the [Binary Search Tree](/categories/data-structures/trees/binary-search-tree)),
which is that although we would like to use the tree structure to take advantage
of the idea of binary search, and be able to perform operations like `get`, 
`put`, or `delete` in logarithmic time, we have no guarantee for balance. We 
can only say that these operations are done in O(H) time, where H is the height
of the tree. And in some situations, the tree may degenerate into a linked list
(such as if the elements were inserted into the tree in sorted order, then all
of the nodes would link to the `right` node), and then all of those operations
would run in O(N) time.

Being able to keep balance is a highly desirable property because it would mean
that all of those operations could be done in O(lgN) time guaranteed. There are
several tree structures that provide the mechanisms to do so: the 
[2-3 Tree](/categories/data-structures/trees/2-3-tree) gives an abstract 
overview of a self-balacing tree structure, the [Red-Black Tree](/categories/data-structures/trees/red-black-tree),
and the [AVL Tree](/categories/data-structures/trees/avl-tree).

### Visualization

The following visualizes the difference between a balanced binary search tree
and one that is not. Suppose we had the following keys to be inserted into a 
binary search tree:

```
{1, 2, 3, 4, 5, 6, 7, 8}
```

Clearly, they are in sorted order. With a non-balanced binary search tree, we 
would end up with all of the nodes going to the `right`, and then the tree
degenerates into a linked list:

```
    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6
               \ 
                7
                 \
                  8
```

Even if the keys were in a different order, like the following:

```
{1, 3, 2, 6, 7, 4, 5, 8}
```

We have no expectations for balance. Thus for operations like `get`, `put`, or
`delete`, we can only say that they run in O(H) time, where H is the height of
the tree, which is less than or equal to N.

```
    1
   / \
  2   3
       \
        6
       / \ 
      4   7
       \   \
        5   8
```

In a balanced tree however, regardless of the order we insert the elements, we
expect to get a tree that self-balances, an example may be the following:

```
              5
           /     \
          3       7
         / \     / \   
        2   4   6   8
       /
      1
```

The distance from the root to any of the leaf nodes is at most lgN, so we are
able to perform operations like `get`, `put`, or `delete` in O(lgN) time 
guaranteed.
{'fraction_non_alphanumeric': 0.06794637416209628, 'fraction_numerical': 0.013711151736745886, 'mean_word_length': 2.5149892933618845, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5453068', 'n_tokens_mistral': 953, 'n_tokens_neox': 897, 'n_words': 490}