/*
 * Bartosz "WiedźMAC" Bednarczyk
 * Liceum Ogólnokształcące im. Władysława Broniewskiego w Strzelcach Opolskich
 * Klasa reprezentująca binarne drzewo przeszukiwań (BST)
 * www.algorytm.org
 */

#include <cstdio>
#define NIL 99999999

#ifndef BST_H
#define BST_H

class BSTNode
{
	public:

	int key;
	BSTNode *parent, *left, *right;

	BSTNode( int k = NIL )
	{
		parent = left = right = NULL;
		key = k;
	}
};

class BST
{
	public :

	BSTNode *Root;

	void PreorderTreeWalk( BSTNode *x )
	{
		if( x != NULL )
		{
			printf("%d ", x->key);
			PreorderTreeWalk( x->left );
			PreorderTreeWalk( x->right );
		}
	}

	void PostorderTreeWalk( BSTNode *x )
	{
		if( x != NULL )
		{
			PostorderTreeWalk( x->left );
			PostorderTreeWalk( x->right );
			printf("%d ", x->key);
		}
	}

	void InorderTreeWalk( BSTNode *x )
	{
		if( x != NULL )
		{
			InorderTreeWalk( x->left );
			printf("%d ", x->key);
			InorderTreeWalk( x->right );
		}
	}

	BSTNode* Max( BSTNode *x )
	{
		while( x->right != NULL )
		{
			x = x->right;
		}

		return x;
	}

	BSTNode* Min( BSTNode *x )
	{
		while( x->left != NULL )
		{
			x = x->left;
		}

		return x;
	}

	BSTNode* Search( BSTNode *x, int k )
	{
		if( x == NULL || x->key == k ) return x;

		if( k < x->key ) return Search( x->left, k );
		else return Search( x->right, k );
	}

	BSTNode* Successor( BSTNode *x )
	{
		if( x->right != NULL ) return Min( x->right );
		else
		{
			BSTNode *y = x->parent;

			while( y != NULL && x == y->right )
			{
				x = y;
				y = y->parent;
			}

			return y;
		}
	}

	BSTNode* Predessor( BSTNode *x )
	{
		if( x->left != NULL ) return Max( x->left );

		BSTNode *y = x->parent;

		while( y != NULL && x == y->left )
		{
			x = y;
			y = y->parent;
		}

		return y;
	}

	void Clear(BSTNode *x)
	{
		if( x != NULL )
		{
			Clear( x->left );
			Clear( x->right);
			delete x;
		}
	}

	void Insert(BSTNode *InsertNode)
	{
		BSTNode *y = NULL;
		BSTNode *x = Root;

		while( x != NULL )
		{
			y = x;

			if( InsertNode->key < x->key )
			{
				x = x->left;
			}
			else
			{
				x = x->right;
			}
		}

		InsertNode->parent = y;

		if( y == NULL )
		{
			Root = InsertNode;
		}
		else
		{
			if(InsertNode->key < y->key)
			{
				y->left = InsertNode;
			}
			else
			{
				y->right = InsertNode;
			}
		}
	}

	void Delete( BSTNode *DeleteNode )
	{
		BSTNode *y = NULL;
		BSTNode *x = NULL;

		if( (DeleteNode->left == NULL) || (DeleteNode->right == NULL) )
		{
			y = DeleteNode;
		}
		else
		{
			y = Successor(DeleteNode);
		}

		if( y->left != NULL )
		{
			x = y->left;
		}
		else
		{
			x = y->right;
		}

		if( x != NULL )
		{
			x->parent = y->parent;
		}

		if( y->parent == NULL )
		{
			Root = x;
		}
		else
		{
			if(y == y->parent->left)
			{
				y->parent->left = x;
			}
			else
			{
				y->parent->right = x;
			}
		}

		if( y != DeleteNode )
		{
			DeleteNode->key = y->key;
		}

		delete y;
		y = NULL;

	}

	BST(void)
	{
		Root = NULL;
	}

	~BST(void)
	{
		Clear( Root );
	}
};

#endif