function to update height of a node

[SSDEEZ]

I'm trying to create a function that can return a node at a given key after inserting into a binary search tree, I've done that part, but I want to update the height of each node as it gets inserted, so when I return a node, it will give me the correct height of that node as well. I'm having trouble figuring out how to do this.

Any ideas?

struct node{
    node(int k = 0){
        key = k;
        height = 0;
        right = NULL;
        left = NULL;
    }
    int key;
    int height;
    node *left;
    node* right;
};

node *insert(node*root, int k){
    
    if(root == NULL){
        node*p = new node(k);
        p->key = k;
        root = p;
    }

    if(k < root->key){
        root->left = insert(root->left, k);
        if(root->left != NULL){
            root->height = root->height + 1;
        }
        
    }
    if(k == root->key){
        ;
    }
    if(k > root->key){
        root->right = insert(root->right, k);
        if(root->right != NULL){
            root->height = root->height + 1;
        }

    }

    return root;
}

[keskiverto]

1. What does the "height" mean?
If we have this tree, what are the heights of the nodes:

   c
 b   e
a   d f

2. Why the:

        node*p = new node(k);
        p->key = k;
        root = p;

Your node has a constructor that does already set the key. Why do you set it again?
You could as well simply return new node(k);


3. The constructor can use member initializer list syntax:

node(int k = 0)
 : key{k}, height{0}, right{nullptr}, left{nullptr}
{
}

[TheIdeasMan]

also use nullptr throughout instead of NULL. As keskiverto shows in the snippet.

[markyrocks]

The easiest way I can describe to do this is to keep track of the head and the tail and only insert at one end or the other so that the head and tail are always prev/next. have a constructor that takes node(prev,next,value,etc); when it's called use it like node* n=new node(tail,head,k,etc) THEN
tail->next=n; //this could result in nullptr so maybe try, catch?
tail=n;
head=head?head:n; something like that it can get very confusing. Then to find the position wou be something like

int pos(node* n, node* h){
      if(n==h){return 0;}
int i=0;
node* cur=n;
      while(cur!=h){
             cur=cur->prev;  //can be issues with deref nullptr!!
             i++;
      }
      return i;
}

It's a royal pita but worth it to get your mind around it. I found it useful to populate a bigger node array and set all the pointers up in one pass and then simply rearrange them... the empty ones just get pushed past the end, this may or may not be possible. It's definitely mental gymnastics.

[markyrocks]

O and I think what you want is a map.

[markyrocks]

this all seems to be working with simple testing... could use cleanup. pita to say the least. But it is worthwhile understanding how this works bc its much cheaper to rewire pointers than it is to actually swap elements around.

#include <iostream>
#include<map>
#include<sstream>

using namespace std;
struct node {
    node* prev;
    node* next;
    int val, key;
    node(node* prev=nullptr,node* next=nullptr,int key=NULL,int val=NULL)
        :prev{ prev }, next{ next }, val{ val }, key{ key } {}

};

struct cache {
    int cp;
    node* head;
    node* tail;
    map<int, node*> mp;

    cache(int capacity = NULL) : cp(capacity), head{ nullptr }, tail{ nullptr }{}

    void set(int key, int val) {
        auto f = mp.find(key);
        if (f != mp.end()) { mp[key]->val = val; moveToTail(mp[key]); }
        else if (mp.size() < cp) {
            if (!head) {
                head = new node(nullptr, nullptr, key, val);
                mp[key] = head;
            }
            else if (!tail) {
                tail = new node(head, head, key, val);
                head->next = tail;
                head->prev = tail;
                mp[key] = tail;
            }
            else {
                node* n = new node(tail, head, key, val);
                tail->next = n;
                tail = n;
                head->prev=n;
                mp[key] = n;
            }//probably need a scenario where cp is only 1... but im not doing it...
        }
        else { //capacity is reached....shift head to the rear
            auto f = mp.find(head->key);
            mp.erase(f);
            tail = head;
            head = tail->next;
            tail->key = key;
            tail->val = val;
            mp[key] = tail;
        }

    }

    void moveToTail(node* n) {
        if (n == tail) { return; }
        else if (n == head) {
            tail = head;
            head = tail->next;
        }
        else {
            n->prev->next = n->next; //removes itself from old positiion
            n->next->prev = n->prev;

            n->next = head; //inserts itself in new postion
            n->prev = tail;

            tail->next = n; //updates the nodes on both sides
            head->prev = n;

            tail = n; //updates the tail
        }
    }

    int get(int key) { //push newest hits to the back
        auto f = mp.find(key);
        if (f == mp.end()) { return -1; }
        moveToTail(mp[key]);
        return tail->val;
    }

    void printptrs() {
        for (auto& n : mp) {
            cout << " prev = " << n.second->prev << " current = " << n.second << " next = " << n.second->next << "\n";
        }
    }
    void printMap() {
        for (auto& m : mp) {
            cout << "key = " << m.first << " val = " << m.second->val << "\n";
        }
    }
    void printMapOrdered() {
        node* n = head;
        do {
            cout << "key = " << n->key << " val = " << n->val << "\n";
            n = n->next;
        } while (n != head);

        
    }

};



int main()
{
   stringstream ss;
    ss << "4 0 1 2 3 4 5 6 7 8 9"; //simple test case 
    int n,k,v;
    ss >> n;
    
    cache c(n);

   while(ss>>k>>v){
       c.set(k, v);
//printptrs();

    }
   c.get(4);
   c.printMap();
cout << " \n\n";
   c.printMapOrdered();

}