BST的插入和删除

[b]Binary Search Tree[/b]

由于經常的插入删除操作會變得越來越不平衡，導緻運作效率低下，但删除操作還是蠻漂亮的。

本代碼來自《算法導論》，也可以用遞歸做，但肯定沒有疊代效率高。

typedef int ElementType;

typedef struct TreeNode
{
	ElementType key;
	struct TreeNode *parent;
	struct TreeNode *left;
	struct TreeNode *right;
} Node, *BST;

// T:root, z:指向要插入節點的指針
void Insert(BST T, Node *z)
{
	Node *x = T;
	Node *y = NULL;

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

	z->parent = y;

	if (y == NULL)
		T = z;
	else if (y->key > z->key)
		y->left = z;
	else
		y->right = z;
}

// x的parent => y的parent
void Transplant(BST T, Node *x, Node *y)
{
	if (x->parent == NULL)
		T = y;
	else if (x == x->parent->left)
		x->parent->left = y;
	else
		x->parent->right = y;

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

// z:指向要删除節點的指針
void Delete(BST T, Node *z)
{
	if (z->left == NULL)
		Transplant(T, z, z->right);
	else if (z->right == NULL)
		Transplant(T, z, z->left);
	else
	{
		Node *y = FindMin(z->right); // y not have left child

		if (y->parent != z) {
			Transplant(T, y, y->right);
			y->right = z->right;
			y->right->parent = y;
		}

		Transplant(T, z, y);
		y->left = z->left;
		y->left->parent = y;
	}
}