BST的安插和删除

BST的插入和删除
Binary Search Tree
由于经常的插入删除操作会变得越来越不平衡，导致运行效率低下，但删除操作还是蛮漂亮的。
本代码来自《算法导论》，也可以用递归做，但肯定没有迭代效率高。

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;elsex = x->right;}z->parent = y;if (y == NULL)T = z;else if (y->key > z->key)y->left = z;elsey->right = z;}// x的parent => y的parentvoid Transplant(BST T, Node *x, Node *y){if (x->parent == NULL)T = y;else if (x == x->parent->left)x->parent->left = y;elsex->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 childif (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;}}