HDU 4006 The kth great number AVL解法

HDU 4006 The kth great number AVL解法

給出動態更新數據，實時問第K個大的數值是什麼？

利用AVL數據結構做的一個統計數，比較高級的數據結構內容了。

不知道題目給出的數據值是否有重復，因為我下面的程序是可以處理出現數據重復的情況的。

其中的奧妙是增加了repeat的信息，可以知道出現了當前數組多少次。

主要是知道如何維護這些數據和如何查詢，維護數據的函數是pushUp，查詢函數是selectKth。

其他就是一般的AVL操作。個人覺得我的AVL寫的還算蠻清晰的，有需要的參考一下。

#include 

inline int max(int a, int b) { return a > b? a : b; }
inline int min(int a, int b) { return a < b? a : b; }

struct Node
{
	int key, h, size, repeat;	//repeat for record the repeated key times
	Node *left, *right;
	explicit Node(int val = 0) : left(NULL), right(NULL), 
		key(val), repeat(1), h(1), size(1){}
};

inline int getHeight(Node *n)
{
	if (!n) return 0;
	return n->h;
}

inline int getSize(Node *n)
{
	if (!n) return 0;
	return n->size;
}

inline int getBalance(Node *n)
{
	if (!n) return 0;
	return getHeight(n->left) - getHeight(n->right);
}

inline void pushUp(Node *n)
{
	if (!n) return ;
	n->size = getSize(n->left) + getSize(n->right) + n->repeat;
	n->h = max(getHeight(n->left), getHeight(n->right)) + 1;
}

inline Node *leftRotate(Node *x)
{
	Node *y = x->right;
	x->right = y->left;
	y->left = x;

	pushUp(x);
	pushUp(y);
	return y;
}

inline Node *rightRotate(Node *x)
{
	Node *y = x->left;
	x->left = y->right;
	y->right = x;
	
	pushUp(x);
	pushUp(y);
	return y;
}

inline Node *balanceNode(Node *n)
{
	if (!n) return n;

	int balance = getBalance(n);
	if (balance > 1)
	{
		if (getBalance(n->left) < 0) n->left = leftRotate(n->left);
		n = rightRotate(n);
	}
	else if (balance < -1)
	{
		if (getBalance(n->right) > 0) n->right = rightRotate(n->right);
		n = leftRotate(n);
	}
	return n;
}

Node *insert(Node *rt, int val)
{
	if (!rt) return new Node(val);

	if (rt->key == val) rt->repeat++;
	else if (rt->key < val) rt->left = insert(rt->left, val);
	else rt->right = insert(rt->right, val);

	pushUp(rt);
	return balanceNode(rt);
}

int selectKth(Node *rt, int k)
{
	int lSize = getSize(rt->left);
	if (k <= lSize) return selectKth(rt->left, k);
	else if (lSize + rt->repeat < k)
		return selectKth(rt->right, k - lSize - rt->repeat);
	return rt->key; // lSize < k <= lSize+rt->repeat
}

void deleteTree(Node *rt)
{
	if (rt)
	{
		if (rt->left) deleteTree(rt->left);
		if (rt->right) deleteTree(rt->right);
		delete rt; rt = NULL;
	}
}

int main()
{
	int n, k, val;
	char c;
	while (scanf("%d %d", &n, &k) != EOF)
	{
		Node *tree = NULL;
		for (int i = 0; i < n; i++)
		{
			getchar();// get rid of '\n'
			c = getchar();
			if ('I' == c)
			{
				scanf("%d", &val);
				tree = insert(tree, val);
			}
			else
			{
				printf("%d\n", selectKth(tree, k));
			}
		}
		deleteTree(tree);
	}
	return 0;
}