Binary Search Tree - Starting with lists

[ Personal detail: I want to share the things that I truly think are clever little designs, but if they're not and I'm stupid, then at least I learned about the greater scope of it all. ]

Binary Search Trees

Let's start from the top and work down:

A Binary Search Tree is a data structure centered around the concept of nodes, or structures which contain data and links to other structures. This concept is the driving force of a similar, more simple object as well, the list, more specifically -- a singly-linked list.

Linked Lists

Lets walk through an imaginary linked list and then describe it in code. First we must create our structure to hold data and our links to other structures. In our diagram, we can represent that structure with brackets:

[data,link]

With the definition we have so far a structure pointing to another structure is represented as:

[data,[data,link]]

However, that isn't quite accurate. The links are storing the location of the next structure, so it makes sense to use a more meaningful representation:

[data]->[data]

In that representation, we could walk through a list by following the links sequentially:

[H]->[e]->[l]->[l]->[o]

We do this by following each link to the next node, then following it's link, and so on. In theory, it is a simple idea, but it is the root of so many more complexities.

Now the C code:

(Only the relevant parts of a list)

typedef struct node_t { 
    int data;                                   
    struct node_t * next;                       
} node;


int traverse_forward(node * head, int (*action)(int value)){
    if(head == NULL){
        return -1;
    }
    
    while(head->next != NULL){               
        action(head->data);                  
        head->next = head->next->next; 
    }
}

Comments by line:

1 : This is the definition of the structure which holds our data and link.
2 : It holds a single int variable as our data;
3 : This is a pointer to another structure, this is what gives our list it's properties.

12: While we aren't at the end of the list:
13: Do an action with our data;
14: Go to the next link;

Next Time...

In the following post, I will describe the BST in C++ and break down the algorithm for inserting a node. (This is, after all, the algorithm that shapes the list into a tree.)

A word on content.

Introduction

This is a programming blog which will be going over many different topics. The primary language I will be using is C++, but we will also use C. In the future, I plan to bring Haskell and Prolog into the mix.


I intend for this to be a very abstract blog with very concrete examples. 

Content of This Blog

This blog will also be implementing very many algorithms for the sake of learning how they work, include many features of that most treat as black boxes for their entire career.

I will be posting and analyzing snippets of code, as well as full programs. We will also go over interesting theories in the field, implementing the ones that are short enough. This includes going beyond the normal consideration - "needless details" to the developer who isn't curious about the insides of the abstraction. (Or sometimes just doesn't have the time to do it for production code.)

The following is an outline for a planned set of posts:

• The end product will be a working string class with clean and acceptable code, but the goal was the process -- to learn more about how the internals work. Almost by definition, we will be using as few libraries as possible, even if it means re-implementing code.

1. Implement a Binary Search Tree (BST) class and talk about it's uses, specifications, and mathematical basis.* 
2. Derive a Rope class from the BST class.
3. Derive a string class designed for long strings from the Rope class that is fully compatible with C strings and C++'s std::string.

We will use that string class for another set of posts that will implement a text editor -- hence the reason for using the rope structure. (There will be more interesting things like markov chains, ANNs, et cetera.)

*This is true of all posts!

Other:

I highly encourage comment discussions (as well as "bug reports") and I appreciate suggestions for posts and topics.

I am using a third party code "prettifier" called SyntaxHighlighter:

int cmp_str(char * str1, char * str2){
    int i = 0, j = 0;
    while(*(str1+i) != '\0' && *(str2+i) != '\0'){
        if(*(str1+i) == *(str2+i)){
            j++;
        }
        i++;
    }
    
    if(j == i){
        return true;
    } else {
        return false;
    }
}