PicoLisp Explored: The idx function
Tags: functional, picolisp, binarytree, algorithms
Published: 2021-12-06 10:42:29

In this post, we will talk about a special kind of tree - the [binary search tree](https://en.wikipedia.org/wiki/Binary_tree).

This post covers the fundamentals. The purpose is to build the fundamentals for the really interesting parts, which will be covered during the next posts: Enhancing program execution speed with help of the ``cache`` and ``enum`` function. 

--------------------------------

## A little bit of theory

We will not to go to deep here, but we need to know some basics in order to understand the rest of the post.

### What is a binary tree?

A **binary tree** is a structure where each node can have up to **two children** (*left child* and *right child*), also called **nodes**.  A binary tree has some very convenient characteristics as we will see soon. Let's look at the following example:

![bintree.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1630877602879/C5HsHiuYg.png)

In total there are 11 nodes. For each node, the left children are smaller than the node, the right children are larger. This is an example for a **sorted tree**. It is also  **balanced**, because all layers are complete except for the lowest one.

A binary tree with ``n`` layers can store up to ``(2^n) -1`` entries: 
- Two layers: 1+2 = 3 nodes
- Three layers: 1+2+4 = 7 nodes
- Four layers: 1+2+4+8 = 15 nodes
- ... 


### Why should I care about binary trees?

Binary trees enable extremely efficient searching processes. Say we want to look up node 14. We start at the root (value 50):

- 14 < 50 --> go to left
- 14 < 17 --> go left
- 14 > 12 --> go right --> **found it!**

This means that if the tree is balanced and sorted, every node can be reached within max. ``log(n)`` (binary) steps. Imagine you want to reach a specific items in a list of length ``n``. If you're unlucky, your item is the very last one, and you need to do ``n`` steps!

This means: If you have 1 Million entries to search, in worst case, it will take you **20 steps in a binary tree, but 1 Mio. steps in a normal list**. This should be enough for a motivation, right? Let's start!


-------------------

### Now let's plant a PicoLisp binary tree!

![Gif description](https://c.tenor.com/ZKRGdkLah2cAAAAC/totoro-growing-plants.gif)

--------------------------------

### Simple index trees

The function that inserts a single item into a binary search tree is called ``idx`` (for "index"). Let's try to recreate the tree from the example (only the first 3 layers to keep it short). Start the REPL by typing ``pil +`` in the console and try:

```
: (off Tree)     # declare empty tree
-> NIL

: (for X (50 17 12 23 72 54 76) (idx 'Tree X T))    # loop through list and add items
-> NIL
```

We have two possibilities to check our ``Tree``: The default prints a **list** which follows the (recursive) syntax: ``(root (left-child) right-child)``. 
A more **graphical print-out** is possible using the function ``view`` with the ``T`` flag for binary trees.

```
: Tree
-> (50 (17 (12) 23) 72 (54) 76)

: (view Tree T)
      76
   72
      54
50
      23
   17
      12
```

This corresponds exactly to our example above. Good! Let's check its depth using the ``depth`` function. ``depth`` returns two values: the maximum depth of the longest branch, and the average depth of all nodes.

```
: (depth Tree)
-> (4 . 3)   # max. depth: 4, average depth: 3
```

--------------

### Worst case scenario: Sorted lists

In our previous example, we received a perfectly **balanced** tree, which means that all layers were "filled" up before the next layer was started. However, this cannot be guaranteed as we will see in the next example.

Let's enter a **sorted list**.

```
: (for X (1 2 3 4) (idx 'Tree X T))    
-> NIL

: (view Tree T)
         4
      3
   2
1

: (depth Tree)
-> (4 . 3)  # depth: 4, average: 3
```

Oh no, our tree almost looks like a list! **We lost our favorite binary tree feature, the logarithmic search.** 

The ``idx`` function works best with random values. Otherwise we need to improve the structure by **balancing** the tree during the insertion. This can be done using the ``balanced`` function.

--------------------------------

### Balanced trees

The function ``balanced`` automatically creates balanced trees out of a **sorted input list**. If the values are not sorted yet, we can use ``sort`` function before we hand them over.

```
: (balance 'Tree (sort ( 1 7 4 3 5 6 2 )))
 
: (view Tree T)
      7
   6
      5
4
      3
   2
      1
```

This looks much better, right? Now we can reach any of the 7 nodes within max. 2 steps.

--------------------

With this, we have covered the fundamentals of binary trees in PicoLisp. In the next posts, we will solve the "[Tree Traversal Task](https://rosettacode.org/wiki/Tree_traversal#PicoLisp)" from the Rosetta Code to get a feeling how binary tree search works.

--------------------

### Sources

- https://en.wikipedia.org/wiki/Binary_tree  
- https://software-lab.de/doc/index.html  
- https://software-lab.de/doc/tut.html