向一個二叉查找樹b中插入一個節點s的算法，過程為：

1. 若b是空樹，則將s所指結點作為根節點插入，否則：
2. 若s->data等於b的根節點的數據域之值，則返回，否則：
3. 若s->data小於b的根節點的數據域之值，則把s所指節點插入到左子樹中，否則：
4. 把s所指節點插入到右子樹中。

                            

在二叉排序樹刪去一個結點，分三種情況討論：

1. 若*p結點為葉子結點，即PL(左子樹)和PR(右子樹)均為空樹。由於刪去葉子結點不破壞整棵樹的結構，則隻需修改其雙親結點的指針即可。
2. 若*p結點隻有左子樹PL或右子樹PR，此時隻要令PL或PR直接成為其雙親結點*f的左子樹（當*p是左子樹）或右子樹（當*p是右子樹）即可，作此修改也不破壞二叉排序樹的特性。
3. 若*p結點的左子樹和右子樹均不空。在刪去*p之後，為保持其它元素之間的相對位置不變，可按中序遍曆保持有序進行調整，可以有兩種做法：其一是令*p的左子樹為*f的左/右(依*p是*f的左子樹還是右子樹而定)子樹，*s為*p左子樹的最右下的結點，而*p的右子樹為*s的右子樹；其二是令*p的直接前驅（或直接後繼）替代*p，然後再從二叉排序樹中刪去它的直接前驅（或直接後繼）。

二叉查找樹性能分析

/*file:biTree.h*/
#ifndef CHIYX_BITREE
#define CHIYX_BITREE
#ifndef NULL
#define NULL 0
#endif
typedef int DataType;
//二叉樹的節點結構
typedef struct BiTreeNode {
	DataType data;
	struct BiTreeNode *parent;
	struct BiTreeNode *left;
	struct BiTreeNode *right;
}BiTreeNode, *BiTree;

//查找：返回第一個等於data域等於key的節點，不存在返回NULL
BiTreeNode *search(BiTree *biTree, DataType key);
//返回二叉樹的最小節點,空樹返回NULL
BiTreeNode *minImum(BiTree *biTree);
//返回二叉樹的最大節點,空樹返回NULL
BiTreeNode *maxImum(BiTree *biTree);
//返回節點x的後繼節點,不存在後繼（節點x為最大節點）返回NULL
BiTreeNode *successor(BiTreeNode *x);
//返回節點x的前驅節點，不存在前驅（節點x為最小節點）返回NULL
BiTreeNode *predecessor(BiTreeNode *x);
//將值data插入到二叉樹中（生成一個值為data的節點）
void insertNode(BiTree *biTree, DataType data);
//刪除一個值為data的節點
void deleteNode(BiTree *biTree, DataType data);
//中序遍曆二叉樹
void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node));
#endif

C語言實現代碼：

/*file:biTree.c*/
#include <stdlib.h>
#include "biTree.h"

//查找：返回第一個等於data域等於key的節點，不存在返回NULL
BiTreeNode *search(BiTree *biTree, DataType key) {
	BiTreeNode *curNode = *biTree;
	while (curNode != NULL && curNode->data != key) {
		if (key < curNode->data) {
			curNode = curNode->left;
		} else {
			curNode = curNode->right;
		}
	}
	return curNode;
}
//返回二叉樹的最小節點,空樹返回NULL
BiTreeNode *minImum(BiTree *biTree) {
	BiTreeNode *curNode = *biTree;
	while (curNode != NULL && curNode->left != NULL) {
		curNode = curNode->left;
	}
	return curNode;
}
//返回二叉樹的最大節點,空樹返回NULL
BiTreeNode *maxImum(BiTree *biTree) {
	BiTreeNode *curNode = *biTree;
	while (curNode != NULL && curNode->right != NULL) {
		curNode = curNode->right;
	}
	return curNode;
}

//返回節點x的後繼節點,不存在後繼（節點x為最大節點）返回NULL
BiTreeNode *successor(BiTreeNode *x) {
         if (x == NULL) return NULL;
	//存在右子樹，則後繼節點為其右子樹中最小的節點
	if (x != NULL && x->right != NULL) {
		return minImum(&(x->right));
	}
	while (x->parent != NULL && x->parent->right == x) {
		x = x->parent;
	}
	return x->parent; //錯誤版本為 x， 此處應該返回父結點
}
//返回節點x的前驅節點，不存在前驅（節點x為最小節點）返回NULL
BiTreeNode *predecessor(BiTreeNode *x) {
         if (x == NULL) return NULL;
	//存在左子樹，則後繼節點為其左子樹中最大的節點
	if (x != NULL && x->left != NULL) {
		return maxImum(&(x->left));
	}
	while (x->parent != NULL && x->parent->left == x) {
		x = x->parent;
	}
	return x->parent; //錯誤版本為 x， 此處應該返回父結點

}

void insertNode(BiTree *biTree, DataType data) {
	//創建節點
	BiTreeNode *targetNode;

	targetNode = (BiTreeNode *)malloc(sizeof(BiTreeNode));
	//沒有足夠內存
	if (targetNode == NULL) return;
	targetNode->data = data;
	targetNode->parent = NULL;
	targetNode->left = NULL;
	targetNode->right = NULL;

	BiTreeNode *p, *y; 
	p = *biTree;
	y = NULL;
	while (p != NULL ) {
		y = p;
		if (targetNode->data < p->data) {
			p = p->left;
		} else {
			p = p->right;
		}
	}
	//空樹，將新節點置為樹根
	if (y == NULL) {
		*biTree = targetNode;
	} else {
		if (targetNode->data < y->data) {
			y->left = targetNode;
		} else {
			y->right = targetNode;
		}
	}
	targetNode->parent = y;
}
//刪除一個值為data的節點
void deleteNode(BiTree *biTree, DataType data) {
	//查找待刪除的節點
	BiTreeNode *targetNode, *x, *y;

	targetNode = search(biTree, data);
	if (targetNode == NULL) return;
	//找出真正的刪除節點，如果目標節點最多隻有一個子樹，則其為真正刪除的節點
	//否則其後繼節點（最多隻有一個子樹，想想為什麼）為真正刪除的節點，然後將後繼節點的值賦給目標節點
	if (targetNode->left == NULL || targetNode->right == NULL) {
		y = targetNode;
	} else {
		y = successor(targetNode);
	}

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

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

	//如果y是根節點, 則根節點變為x
	if (y->parent == NULL) {
		*biTree = x;
	} else {
		if (y->parent->right == y) {
			y->parent->right = x;
		} else {
			y->parent->left = x;
		}
	}

	if (y != targetNode) {
		targetNode->data = y->data;
	} 
	//釋放y占有的空間
	free(y);
}
//中序遍曆二叉樹
void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node)) {
	BiTreeNode *curNode;

	curNode = *biTree;
	if (curNode != NULL) {
		//遍曆左子樹
		inorderTraversal(&(curNode->left), visitor);
		//訪問節點
		visitor(curNode);
		//遍曆右子樹
		inorderTraversal(&(curNode->right), visitor);
	}
}

#include <stdio.h>
#include <stdlib.h>
#include "biTree.h"
#define N  10
void printNode(BiTreeNode *node);

int main(int argc, char *argv[]) {
	BiTreeNode *root;
	int i;

	root = NULL;
	int data[N] = {10, 23, 11, 98, 111, 87, 34, 11, 33, 8};
	for (i = 0; i < N; i++) {
		insertNode(&root, data[i]);
	}
	printf("before delete:\n");
	inorderTraversal(&root, printNode);
	printf("\n");
	deleteNode(&root, 11);
	deleteNode(&root, 8);
	printf("after delete:\n");
	inorderTraversal(&root, printNode);
	printf("\n");
	exit(0);
}
void printNode(BiTreeNode *node) {
	printf("%d\t", node->data);
}

二叉查找樹優化

1. Size Balanced Tree(SBT)
2. AVL樹
3. 紅黑樹（紅黑樹係列文章）
4. Treap(Tree+Heap)

這些均可以使查找樹的高度為。

後續再更！