function to update height of a node

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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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;
}
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:
1
2
3
        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:
1
2
3
4
node(int k = 0)
 : key{k}, height{0}, right{nullptr}, left{nullptr}
{
}
Last edited on
also use nullptr throughout instead of NULL. As keskiverto shows in the snippet.
Last edited on
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

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

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.
O and I think what you want is a map.
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

#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();

}
Last edited on
Registered users can post here. Sign in or register to post.