二叉搜索树的复杂度为(lgN)， 二叉搜索树就是已排序数列的二叉树表示法。
二叉搜索树的定义是： 父节点大于等于左孩子，右孩子大于父节点。因此，若是遍历次序为(中序)：左孩子，父节点，右孩子，那么我们得到的将是元素从小到大的排列。同时，最左结点最小结点，最右结点是最大结点。
二叉搜索树还有定义的操作便是求前驱结点和后继结点。
以后继结点为例： 若有右子树，则后继结点为右子树的最小结点；若无右子树，则后继结点为某个祖先父节点，其祖先结点(包括自身)为父节点的左孩子。
以前驱为例： 若有左子树，则前驱结点为左子树的最大结点； 若无左子树，则前驱结点为某个祖先父节点，其祖先结点(包括自身)为父节点的右孩子。
插入操作，则需要一层层比较，大于，走右；小于，走左；
删除操作，若该结点任一左右孩子为空，则直接把左/右孩子的子结点作为该结点新的左/右结点； 若左右子树都满，则交换该结点和其后继结点的值，调整连接关系。
注意点：就是要小心下边界条件。
下面插入代码：
1 #ifndef MY_BISEARCH_TREE_H 2 #define MY_BISEARCH_TREE_H 3 #include4 #include 5 using namespace std; 6 template 7 struct Node{ 8 T datum; 9 Node * parent; 10 Node * left; 11 Node * right; 12 Node(const T& x=T()) : datum(x),parent(NULL),left(NULL),right(NULL){} 13 ~Node(){parent=right=left = NULL;} 14 }; 15 16 template 17 class bisearchTree{ 18 protected: 19 Node * root; 20 int size; 21 public: 22 bisearchTree() : size(0) { root = new Node ();} 23 ~bisearchTree(); 24 void destroy(); 25 Node * rt() const { return root->right;} 26 Node * maxmember(Node * n) const; 27 Node * minmember(Node * n) const; 28 Node * search(const T& x) const; 29 Node * succeed(Node * n) const; 30 Node * presucceed(Node * n) const; 31 void inorderwalk(const Node * n) const; 32 bisearchTree & insert(const T& key); 33 Node * del(Node * n); 34 bool isEmpty() const { return size == 0;} 35 int length() const { return size;} 36 }; 37 38 template 39 bisearchTree ::~bisearchTree(){ 40 destroy(); 41 delete root; 42 } 43 template 44 void bisearchTree ::destroy() 45 { 46 Node * p = root->right; 47 Node * d; 48 while(p!=NULL){ 49 d = del(p); 50 delete d; 51 d = NULL; 52 p = root->right; 53 } 54 assert(isEmpty()); 55 } 56 57 template 58 Node * bisearchTree ::maxmember(Node * n) const 59 { 60 Node * c = n; 61 while(c!=NULL){ 62 n = c; 63 c = c->right; 64 } 65 return n; 66 } 67 template 68 Node * bisearchTree ::minmember(Node * n) const 69 { 70 71 Node * c = n; 72 while(c!=NULL){ 73 n = c; 74 c = c->left; 75 } 76 return n; 77 } 78 template 79 Node * bisearchTree ::search (const T& x) const 80 { 81 Node * p = root->right; 82 while(p != NULL && p->datum != x){ 83 if (p->datum > x) { 84 p = p->left; 85 }else{ 86 p = p->right; 87 } 88 } 89 return p; 90 } 91 template 92 Node * bisearchTree ::succeed(Node * n) const 93 { 94 if ((n!=NULL) && (n->right!=NULL)) { 95 return minmember(n->right); 96 } 97 Node * p = n->parent; 98 while(p!=NULL && p->right == n){ 99 n = p;100 p = p->parent;101 }102 return p;103 }104 template 105 Node * bisearchTree ::presucceed(Node * n) const106 {107 if ((n!=NULL) && (n->left!=NULL)) {108 return maxmember(n->left);109 }110 Node * p = n->parent;111 while(p!=NULL && p->left == n){112 n = p;113 p = p->parent;114 }115 return p;116 }117 template 118 void bisearchTree ::inorderwalk (const Node * n) const119 {120 if(n != NULL){121 inorderwalk (n->left);122 cout << n->datum << " ";123 inorderwalk (n->right);124 }125 }126 template 127 bisearchTree & bisearchTree ::insert(const T& key)128 {129 Node * p = root->right;130 if(p == NULL){131 root->right = new Node (key);132 root->right->parent = NULL;133 ++size;134 return *this;135 }136 Node * r = p;137 while(p!=NULL){138 r = p;139 if(p->datum > key){140 p = p->left;141 }else{142 p = p->right;143 }144 }145 if(r->datum > key){146 r->left = new Node (key);147 r->left->parent = r;148 }else{149 r->right = new Node (key);150 r->right->parent = r;151 }152 size++;153 return *this;154 }155 template 156 Node * bisearchTree ::del(Node * n)157 {158 Node * d = NULL;159 if(n->left==NULL || n->right==NULL){160 d = n;161 }else{162 d = succeed(n);163 }164 Node * x;165 if(d->left != NULL){166 x = d->left;167 }else{168 x = d->right;169 }170 if( x != NULL)171 x->parent = d->parent;172 if( d->parent == NULL)173 root->right = x;174 else if(d == d->parent->left){175 d->parent->left = x;176 }else{177 d->parent->right = x;178 }179 if(d != n){180 n->datum = d->datum;181 }182 size--;183 return d;184 }185 186 #endif