update the root in avt tree

I am learning avl trees but i cannot manage to update the root after a rotation, in this code i only wrote the left rotation and it works but when it returns the root doesn't update to "y". I will only write the add and rotate function, number i add are 100 150 and 160

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  Node* rotateleft(Node*x){
	Node*y = x->high;
	Node*t = y->low;
	y->low = x;
	x->high = t;
	x->height = findheight(x);
	y->height = findheight(y);
	return y;
}

Node* add(Node*p, int num){
	if (p == NULL)p = getnew(num);
	else if (num <= p->data)p->low = add(p->low, num);
	else p->high = add(p->high, num);
	p->height = findheight(p);
	if (balance(p) < -1)rotateleft(p);
	return p;
}


and the complete code(only left rotation):

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
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;

struct Node{
	int data;
	int height;
	Node* high;
	Node* low;
};

Node* root = NULL;

Node* getnew(int num){
	Node* temp = new Node;
	temp->data = num;
	temp->height = 0;
	temp->high = NULL;
	temp->low = NULL;
	return temp;
}

void print(Node*p){
	if (p == NULL)return;
	print(p->low);
	cout << p->data << "  ";
	print(p->high);
}

void print2(){
	queue<Node*>q;
	q.push(root);
	while (!q.empty()){
		Node* temp = q.front();
		cout << temp->data << "  ";
		if (temp->low != NULL)q.push(temp->low);
		if (temp->high != NULL)q.push(temp->high);
		q.pop();
	}
}

int findheight(Node*p){
	if (p == NULL)return -1;
	return max(findheight(p->low), findheight(p->high)) + 1;
}

int balance(Node*p){
	int hlow = findheight(p->low);
	int hhigh = findheight(p->high);
	return hlow - hhigh;
}

Node* rotateleft(Node*x){
	Node*y = x->high;
	Node*t = y->low;
	y->low = x;
	x->high = t;
	x->height = findheight(x);
	y->height = findheight(y);
	return y;
}

Node* add(Node*p, int num){
	if (p == NULL)p = getnew(num);
	else if (num <= p->data)p->low = add(p->low, num);
	else p->high = add(p->high, num);
	p->height = findheight(p);
	if (balance(p) < -1)rotateleft(p);
	return p;
}

int main(){
	root = add(root, 100);
	root = add(root, 150);
	root = add(root, 160);
	//root = add(root, 180);
	print(root);
	cout << "\n\n";
	print2();
}
Should line 70 be if (balance(p) < -1) p = rotateleft(p);?
yes, thanks
Topic archived. No new replies allowed.