二分搜索树结构性质，比根节点大的放到右子树，小的放到左子树，相等的去替换，依次递归，时间复杂度O^log(n)级别
当数据为有序时，时间复杂度会退化成O^n
为避免有序数据的出现 -->平衡二叉树：红黑树
template<typename Key,typename Value> class BST{ private: struct Node{ Key key; Value value; Node *left; Node *right; Node(Key key,Value value){ this->key = key; this->value = value; this->left = this->right = NULL; } Node(Node *node){ this->key = node->key; this->value = node->value; this->left = node->left; this->right = node->right; } }; Node *root; int count; public: BST(){ root=NULL; count=0; } ~BST(){ destroy(root); } int size(){ return count; } bool isEmpty(){ return count==0; } void insert(Key key,Value value){ root = insert(root,key,value) } bool contain(Key key){ return contain(root,key); } Value* search(Key key){ return search(root,key); } //前序遍历 void preOrder(){ preOrder(root); } //中序遍历 void inOrder(){ inOrder(root); } //后序遍历 void postOrder(){ postOrder(root); } //层序遍历 void levelOrder(){ queue<Node*> q; q.push(root); while (!q.empty()) { Node *node = q.front(); q.pop(); count<<node->key<<endl; if(node->left) q.push(node->left); if(node->right) q.push(node->right); } } //寻找最小键值 Key minimum(){ assert(count !=0); Node* minNode = minimum(root); return minNode->key; } //寻找最大键值 Key maximum(){ assert(count !=0); Node* maxNode = maximum(root); return maxNode->key; } void removeMin(){ if(root) root = removeMin(root); } void removeMax(){ if(root) root = removeMax(root); } void remove(Key key){ root = remove(root,key) } private: //向以node为根的二叉搜索树中，插入节点（key,value） //返回插入新节点后的二叉搜索树的根 Node* insert(Node *node,Key key,Value value){ if(node==NULL){ count ++; return new Node(key,value); } if(key==node->key) node->value = value; else if(key <node->key) node->left = insert(node->left,key,value); else node->right = insert(node->right,key,value) return node; } //查看以node为根的二叉搜索树中是否包含键值为key的节点 bool contain(Node* node,Key key){ if(node == NULL) return false; if(key== node->key){ return true; } else if(key < node->key) { return contain(node->left,key); }else { return contain(node->right,key); } } Value* search(Node* node,Key key){ if(node == NULL) return NULL; if(key == node->key) return &(node->value); else if(key < node->key) return search(node->left,key) else return search(node->right,key); } void preOrder(Node* node){ if(node!=NULL){ count<<node->key<<endl; preOrder(node->left); preOrder(node->right); } } void inOrder(Node* node){ if(node !=NULL){ inOrder(node->left); count<<node->key<<endl; inOrder(node->right); } } void postOrder(Node* node){ if(node !=NULL){ postOrder(node->left); postOrder(node->right); count<<node->key<<endl; } } //释放空间 void destroy(Node* node){ if(node !=NULL){ destroy(node->left); destroy(node->right); delete node; count --; } } //查找最小值 Node* minimum(Node* node){ if(node->left==NULL) return node; return minimum(node->left); } //查找最大值 Node* maximum(Node* node){ if(node->right==NULL) return node; return maximum(node->right); } Node* removeMin(Node* node){ if(node->left ==NULL){ Node* rightNode = node->right; delete node; count --; return rightNode; } node->left = removeMin(node->left); return node; } Node* removeMax(Node* node){ if(node->left ==NULL){ Node* leftNode = node->left; delete node; count --; return leftNode; } node->right = removeMax(node->right); return node; } Node* remove(Node* node,Key key){ if(node == NULL) return NULL; if(key<node->key){ node->left = remove(node->left,key); return node; } else if(key > node->key){ node->right=remove(node->right,key) return node; }else{ if(node->left ==NULL){ Node *rightNode = node->right; delete node; count --; return rightNode; } if(node->right ==NULL){ Node *leftNode = node->left; delete node; count --; return leftNode; } Node *successor = new Node(minimum(node->right)); count ++; successor->right = removeMin(node->right); successor->left = node->left; delete Node; count --; return successor; } } };