Could this be considered a bst?

[jjordan33]

Hi, more studying. Is this a basic binary search tree?

Thank you.

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main(){
    
    //Stack <class<t> > 
    // space
    
    map<string, string> PhoneBook;
    PhoneBook["Sally Q"] = "333-3333";
    PhoneBook["Rusty K"] = "555-5555";
    
    cout << PhoneBook["Rusty K"] << endl;
    
    for (std::map<string, string>::iterator it = PhoneBook.begin(); it != PhoneBook.end(); it++){
        cout << it -> first << " " << it -> second << endl;
    } 
    
}

Pardon that crazy for loop.

[Duthomhas]

Yes*

Remember the discussion we had yesterday?

[jjordan33]

I do!
haha

That's what led me to making my first bst!

Just wanted to verify that I was understanding y'all correctly.

Thank you!

[jonnin]

there is probably a hidden tree in there. I would not consider it one: its a map. The fact that it has a tree hidden under there is a useful footnote.. now you know why maps are not ~O(1) (which I had expected when I studied them) and that it will be slow. You can't get to the tree. You can't traverse it. Its fully hidden. you can't use it as a BST object. At best you can get a small part of a tree in hand by exploiting what you know.

[jjordan33]

Is there any way to turn that code into what you'd say was a BST with a best case scenario O(1) complexity?

[jonnin]

It already is... if you ask for the root, it will be O(1) best case, but the average case remains N*lg(N).

There is no way to make that what I would call a BST. Its a map implemented with a BST.

Lets take a side branch... Have you actually studied a BST? Coded one with something like

struct node
{
   type data;
   node* left;
   node * right;
}

^^ That is the core of a binary tree. If you sort it by data as you insert it, it will be a BST (a search tree is defined by being sorted so that you choose left/right and discard half the data each time you follow a pointer).

If you want it to act like an STL container you need a lot of extras, but if you just want a BST, you don't need all that much … insert, delete, find will get you the 10 cent homework version.

I am fairly certain BOOST and probably other libraries have STL like BST classes as well if you just want to USE one. I am not a boost expert … haven't needed it in a while and can't recall what all it has in there, but surely this.

the pointers could be array indices if you want to make a tree in an array, which has pros and cons. Try to keep in mind the conceptual thing (a tree structure, looks like a family tree type idea on paper) and the implementation (irrelevant).

[jjordan33]

That's the thing, I have done some studying on a bst, that's why I'm pretty confused about what you're saying now.

I thought it was similar to a python's dictionary. A structure where every data element had a resulting key.

I also thought that a bst was used for unsorted and unordered data because if it was ordered, it would just be a linked list.

I hate sounding stupid, but I don't see what makes the core code you provided a tree and not a doubly linked list, or deque.

If you have documentation that would be better than what I've studied (mostly notes and a couple web pages), I'd be happy to read it.

[Duthomhas]

There are two types of key-data setups:

    • key and data are separate things (think std::map)
    • key and data are the same thing (think std::set)

The BST simply arranges the data by lookup key. If the key and data are the same thing, you see a structure like jonnin’s above. If they are different, you will see:

struct node
{
    key_type  key;
    data_type data;
    node*    left;
    node*    right;
}

The difference is a trivial one — the important characteristic is the tree organization to produce a best case log n lookup. (Worst case is still O(n), because the BST does not know how to balance itself, and insertion order matters.)


You have almost gotten to a very good observation as well: a linked list is a degenerate tree. Consider:

1 2 3 4 5

struct singly_linked_list_node { type data; singly_linked_list_node* next; };

┌───┐ ┌───┐ ┌───┐ ┌───┐ │ 1 ├──┤ 2 ├──┤ 3 ├──┤ 4 ├──NULL └───┘ └───┘ └───┘ └───┘

1 2 3 4 5 6 7 8 9 10 11 12

struct tree_node { type data; tree_node* next_left; tree_node* next_right; };

┌───┐ ┌─────┤ 1 ├─────┐ │ └───┘ │ ┌─┴─┐ ┌─┴─┐ ┌──┤ 2 ├──┐ ┌──┤ 3 ├──┐ │ └───┘ │ │ └───┘ │ NULL NULL ┌─┴─┐ NULL ┌──┤ 4 ├──┐ │ └───┘ │ NULL NULL

That is, a linked list is a tree with a single branch per node.
A binary tree has two branches per node.
A trinary tree has three...
and so on.

Whether the nodes are doubly-linked or not is another implementation detail. For trees, it is usually less work to make it all singly-linked. For linked lists, however, it is often less work to make it doubly-linked.

Boost, like the C++ Standard Library (“STL” refers to HP/SGI’s C++ library, which is the direct ancestor of the C++ Standard Library), is not typically interested in any particular structure over consequence. The reason BSTs are taught is they are the basis for more powerful structures, like Red-Black trees.

Implementation is never irrelevant — it has direct consequences on the complexity and correctness of the code.

Hope this helps.

[jjordan33]

It helps tremendously. I think I have a pretty good foundation on bst's after all this.

I'm still confused about what maps are then, but I believe that's a topic for future Jeff. For now, I'm gonna see if I can just build my own using structs like that. It seems easier.

[jonnin]

The best way I know to describe a map is a 'poorly implemented hash table'.
Conceptually, that is what the map IS. It serves as a lookup table of <some key> to <some data> where you have the key, and can use it to find or add the data to it.

this is critical: ANY GENERIC CONTAINER supports the above idea: you can do it with an array, a tree, a list, a graph, whatever. So the MAP concept is IRRELEVANT to the underlying implementation, the CONCEPT is that you have that key to data "mapping" or relationship as your approach to getting and storing and handling the data. (non generic container in this context would be something like a stack where you are only supposed to be able to get to the top item).


And, this is a key point that is confusing you. The concept vs the implementation is critical to really understanding this material. A tree being used as a map is concept map, implementation tree. A list implemented in a vector is a list. A tree shoved into an array is a tree (and shoving them into vectors is really clean!). Etc.

[George P]

C++11 introduced 4 "unordered associative containers."

std::unordered_set / std::unordered_multiset & std::unordered_map / std::unordered_multimap

Unordered associative containers implement unsorted (hashed) data structures.

https://en.cppreference.com/w/cpp/container#Unordered_associative_containers

[jjordan33]

>> jonnin

Ohhh. That's what you meant by that. I'm with you now.

I think I'm going to be an expert at advanced data structures after all this haha.

I'm stuck on a linked list issue though( figured I'd start there then go to bst).

I'm using a destructor helper, that's recursively called in the destructor, but it never completes it's task. It seems to be in an infinite loop.

linkandzeldaList::~linkandzeldaList(){
    Node *temp = new Node;

    while(head != NULL){
        delete_item(temp -> name);
    }

}

void linkandzeldaList::delete_item(string q){

    Node *temp, *eraser;

    if(head == NULL){
        return;
    }

    else if(head -> name == q){ 
        eraser = head;
        head = head -> next;
        delete eraser;
    }

    else{
        temp = head;

        while(temp -> next != NULL && temp -> next -> name != q){
            temp = temp -> next; 
        }

        if(temp -> next != NULL){
            eraser = temp -> next;
            temp -> next = eraser -> next;
            delete eraser;
        }

    }

}

I would imagine the problem lies somewhere in all those conditions...

**edit***
I am no longer using recursive calls to the helper. I'm just letting the destructor handle it all. I think it's good now. Please correct me if I'm wrong.

cdCollection::~cdCollection(){
    Node *x = new Node;
    while (head != NULL) {
        x = head->next;
        delete head;
        head = x;
    }
}