Welcome to the Lounge

honey the codewitch wrote:

well, in fairness it's not often people have to search and sort 100000 items without using a database

_Node _Splay(_Node root, TKey key)
{
	// TODO: if this function wasn't recursive it could deal with more items
	int c;
	// Base cases: root is null or key is present at root 
	if (null==root || 0==(c = _comparer.Compare(root.Key, key)))
		return root;

	// Key lies in left subtree 
	if (0<c)
	{
		// Key is not in tree, we are done 
		if (null==root.Left)
			return root;
		c = _comparer.Compare(root.Left.Key, key);
		// Zig-Zig (Left Left) 
		if (0<c)
		{
			// First recursively bring the key as root of left-left 
			root.Left.Left = _Splay(root.Left.Left, key);

			// Do first rotation for root, second rotation is  
			// done after else 
			root = _Ror(root);
		}
		else if (0>c) // Zig-Zag (Left Right) 
		{
			// First recursively bring the key as root of left-right 
			root.Left.Right = _Splay(root.Left.Right, key);

			// Do first rotation for root.left 
			if (null!=root.Left.Right)
				root.Left = _Rol(root.Left);
		}

		// Do second rotation for root 
		return (null==root.Left) ? root : _Ror(root);
	}
	else // Key lies in right subtree 
	{
		// Key is not in tree, we are done 
		if (null==root.Right)
			return root;
		c = _comparer.Compare(root.Right.Key, key);
		// Zag-Zig (Right Left) 
		if (0<c)
		{
			// Bring the key as root of right-left 
			root.Right.Left = _Splay(root.Right.Left, key);

			// Do first rotation for root.right 
			if (null!=root.Right.Left)
				root.Right = _Ror(root.Right);
		}
		else if (0>c)// Zag-Zag (Right Right) 
		{
			// Bring the key as root of right-right and do  
			// first rotation 
			root.Right.Right = _Splay(root.Right.Right, key);
			root = _Rol(root);
		}

		// Do second rotation for root 
		return (null==root.Right ) ? root : _Rol(root);
	}
}

/* Iterative function for inorder tree 
   traversal */
void inOrder(struct Node *root) 
{ 
    stack<Node *> s; 
    Node *curr = root; 

<pre>
while (curr != NULL || s.empty() == false)