SDITSAVL.cpp

#include <iostream>
using namespace std;

int Q;
void insert(int x);
int  find(int x);
void init();

struct Node
{
	int x, height, numLeft, numRight;
	Node *left, *right;
};

Node *root;

int  height(Node *p);
void fixHeight(Node *p);
void fixNumLeft(Node *p);
void fixNumRight(Node *p);
int  balanceFactor(Node *p);

Node* initNode(int x);
Node* insert(Node *p, int x);
Node* findMin(Node *p);
Node* removeMin(Node *p);
Node* rotateLeft(Node *p);
Node* rotateRight(Node *p);
Node* balance(Node *p);
int   findOrder(Node *p, int x, int offset);

int main()
{
//	freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	init();
	cin >> Q;
	for(int q = 0; q < Q; q++)
	{
		int type, x, k;
		cin >> type >> x;
		switch (type)
		{
		case 1:
			insert(x);
			break;
		case 2:
			k = find(x);
			if(k < 0) cout << "Data tidak ada" << endl;
			else cout << k << endl;
			break;
		default:
			cout << "There is something wrong" << endl;
			break;
		}
	}
}

void init()
{
	root = 0;
}

void insert(int x)
{
	root = insert(root, x);
}

int  find(int x)
{
	return findOrder(root, x, 0);
}

int height(Node *p)
{
	return p ? p->height : 0;
}

void fixHeight(Node *p)
{
	int hr = height(p->right);
	int hl = height(p->left);
	p->height = (hr > hl ? hr : hl) + 1;
}

void fixNumLeft(Node *p)
{
	if(p->left) p->numLeft = p->left->numLeft + p->left->numRight + 1;
	else p->numLeft = 0;
}

void fixNumRight(Node *p)
{
	if(p->right) p->numRight = p->right->numLeft + p->right->numRight + 1;
	else p->numRight = 0;
}

int balanceFactor(Node *p)
{
	return height(p->right) - height(p->left);
}

Node* initNode(int x)
{
	Node* newNode = new Node;
	newNode->x = x;
	newNode->height = 1;
	newNode->numLeft = 0;
	newNode->numRight = 0;
	newNode->left = 0;
	newNode->right = 0;
	return newNode;
}

Node* insert(Node *p, int x)
{
	if(!p)
		return initNode(x);

	if(x < p->x)
	{
		p->left = insert(p->left, x);
		fixNumLeft(p);
	}
	else if(x > p->x)
	{
		p->right = insert(p->right, x);
		fixNumRight(p);
	}
	return balance(p);
}

Node* findMin(Node *p)
{
	if(!p) return 0;
	if(p->left == 0) return p;
	return findMin(p->left);
}

Node* removeMin(Node *p)
{
	if(!p) return 0;
	if(p->left == 0) return p->right;
	p->left = removeMin(p->left);
	return balance(p);
}

Node* rotateLeft(Node *p)
{
	Node *q = p->right;
	p->right = q->left;
	q->left = p;
	fixHeight(p);
	fixHeight(q);
	fixNumRight(p);
	fixNumLeft(q);
	return balance(q);
}

Node* rotateRight(Node *p)
{
	Node *q = p->left;
	p->left = q->right;
	q->right = p;
	fixHeight(p);
	fixHeight(q);
	fixNumLeft(p);
	fixNumRight(q);
	return balance(q);
}

Node* balance(Node *p)
{
	fixHeight(p);
	fixNumLeft(p);
	fixNumRight(p);

	if(balanceFactor(p) == 2)
	{
		if(balanceFactor(p->right) < 0)
			p->right = rotateRight(p->right);
		return rotateLeft(p);
	}

	if(balanceFactor(p) == -2)
	{
		if(balanceFactor(p->left) > 0)
			p->left = rotateLeft(p->left);
		return rotateRight(p);
	}

	return p;
}

int findOrder(Node *p, int x, int offset)
{
	if(!p) return -1;
	if(p->x == x) return offset + p->numLeft + 1;
	
	if(p->x > x)
		return findOrder(p->left, x, offset);

	if(p->x < x)
		return findOrder(p->right, x, offset + p->numLeft + 1);
}