二叉搜索树概念与操作二叉搜索树的概念二叉搜索树又称二叉排序树若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别未二叉搜索树。也可以是一颗空树。int a[] { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };二叉搜索树的操作查找迭代123456789101112131415161718192021Node* Find(constK key){Node* cur _root;while(cur){if(cur-_key key){cur cur-_right;}elseif(cur-_key key){cur cur-_left;}else{returncur;}}returnnullptr;}递归123456789101112Node* _FindR(Node* root,constK key){if(root nullptr)returnnullptr;if(root-_key key)return_FindR(root-_right, key);elseif(root-_key key)return_FindR(root-_left, key);elsereturnroot;}插入树为空则直接插入树不为空按二叉搜索树性质查找插入位置插入新节点迭代1234567891011121314151617181920212223242526272829303132333435363738394041boolInsert(constK key){if(_root nullptr){_root newNode(key);returntrue;}//查找要插入的位置Node* parent nullptr;Node* cur _root;while(cur){if(cur-_key key){parent cur;cur cur-_right;}elseif(cur-_key key){parent cur;cur cur-_left;}else{returnfalse;}}cur newNode(key);if(parent-_key cur-_key){parent-_right cur;}else{parent-_left cur;}returntrue;}递归1234567891011121314151617181920212223bool_InsertR(Node* root,constK key){if(root nullptr){root newNode(key);returntrue;}else{if(root-_key key){return_InsertR(root-_left, key);}elseif(root-_key key){return_InsertR(root-_left, key);}else{returnfalse;}}}删除首先查找元素是否在二叉搜索树中如果不存在则返回否则要删除的结点可能分下面四种情况要删除的结点无孩子结点要删除的结点只有左孩子结点要删除的结点只有右孩子结点要删除的结点只有左、右结点实际情况中1和2或3可以合并因此真正的删除过程如下删除该结点且使被删除结点的双亲结点指向被删除结点的左孩子结点删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点替代法。在它的右子树中寻找中序下的第一个结点关键码最小用它的值填补到被删除结点中再来处理该结点的删除问题。迭代123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384boolErase(constK key){Node* parent nullptr;Node* cur _root;while(cur){if(cur-_key key){parent cur;cur cur-_right;}elseif(cur-_key key){parent cur;cur cur-_left;}else{//删除if(cur-_left nullptr){if(cur _root){_root cur-_right;}else{if(cur parent-_left){parent-_left cur-_right;}else{parent-_right cur-_right;}}deletecur;}elseif(cur-_right nullptr){if(cur _root){_root cur-_left;}else{if(cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}}else{//找到右树最小节点去替代删除Node* minRightParent cur;Node* minRight cur-_right;while(minRight-_left){minRightParent minRight;minRight minRight-_left;}cur-_key minRight-_key;if(minRight minRightParent-_left)minRightParent-_left minRight-_right;elseminRightParent-_right minRight-_right;deleteminRight;}returntrue;}}returnfalse;}递归1234567891011121314151617181920212223242526272829303132333435363738394041424344bool_EraseR(Node* root,constK key){if(root nullptr)returnfalse;if(root-_key key){return_EraseR(root-_right, key);}elseif(root-_key key){return_EraseR(root-_left, key);}else{//删除Node* del root;if(root-_left nullptr){root root-_right;}elseif(root-_right nullptr){root root-_left;}else{//替代法删除Node* minRight root-_right;while(minRight-_left){minRight minRight-_left;}root-_key minRight-_key;//转换成递归在右子树中删除最小节点return_EraseR(root-_right, minRight-_key);}deletedel;returntrue;}}二叉搜索树的应用1.K模型K模型即只有key作为关键码结构中只需要存储key即可关键码即为需要搜索到的值。比如给一个单词word判断该单词是否拼写正确。具体方法如下1.以单词集合中的每个单词作为key构建一棵二叉搜索树。2.在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。2.KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见比如英汉词典就是英语与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。比如实现一个简单的英汉词典dict可以通过英文找到与其对应的中文具体实现方式如下1.单词中文含义为键值对构造二叉搜索树注意二叉搜索树需要比较键值对比较时只比较Key。2.查询英文单词时只需要给出英文单词就可快速找到与其对应的Key。123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201namespaceKEY_VALUE {templateclassK,classVstructBSTreeNode{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _value;BSTreeNode(constK key,constV value):_left(nullptr),_right(nullptr),_key(key),_value(value){}};templateclassK,classVclassBSTree {typedefBSTreeNodeK, V Node;public:V operator[](constK key){pairNode*,bool ret Insert(key, V());returnret.first-_value;}pairNode*,bool Insert(constK key,constV value){if(_root nullptr){_root newNode(key, value);returnmake_pair(_root,true);}//查找要插入的位置Node* parent nullptr;Node* cur _root;while(cur){if(cur-_key key){parent cur;cur cur-_right;}elseif(cur-_key key){parent cur;cur cur-_left;}else{returnmake_pair(cur,false);}}cur newNode(key, value);if(parent-_key cur-_key){parent-_right cur;}else{parent-_left cur;}returnmake_pair(cur,true);}Node* Find(constK key){Node* cur _root;while(cur){if(cur-_key key){cur cur-_right;}elseif(cur-_key key){cur cur-_left;}else{returncur;}}returnnullptr;}boolErase(constK key){Node* cur _root;Node* parent nullptr;while(cur){if(cur-_key key){parent cur;cur cur-_right;}elseif(cur-_key key){parent cur;cur cur-_left;}else{//删除if(cur-_left nullptr){if(cur _root){_root cur-_right;}else{if(cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_right;}}deletecur;}elseif(cur-_right nullptr){if(cur _root){_root cur-_left;}else{if(cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_right;}}deletecur;}else{//找到右树最小结点去替代删除Node* minRightParent cur;Node* minRight cur-_left;while(minRight-_left){minRightParent minRight;minRight minRight-_left;}cur-_key minRight-_key;if(minRight minRightParent-_left)minRightParent-_left minRight-right;elseminRightParent-_right minRight-_right;deleteminRight;}returntrue;}}returnfalse;}voidInOrder(){_InOrder(_root);cout endl;}private:void_InOrder(Node* root){if(root nullptr){return;}_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}private:Node* _root nullptr;};}1234567891011121314151617181920212223242526272829voidTest2(){KEY_VALUE::BSTreestring, string dict;dict.Insert(sort,排序);dict.Insert(insert,插入);dict.Insert(tree,树);dict.Insert(right,右边);string str;while(cin str){if(str q){break;}else{auto ret dict.Find(str);if(ret nullptr){cout 拼写错误请检查你的单词 endl;}else{cout ret-_key - ret-_value endl;}}}}12345678910111213141516171819202122232425voidTest3(){//统计字符串出现次数也是经典key/valuestring str[] {sort,sort,tree,insert,sort,tree,sort,test,sort};KEY_VALUE::BSTreestring,int countTree;//for (auto e : str)//{// auto ret countTree.Find(e);// if (ret nullptr)// {// countTree.Insert(e, 1);// }// else// {// ret-_value;// }//}for(auto e : str){countTree[e];}countTree.InOrder();}二叉树的性能分析插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深比较的次数越多。但对于同一个关键码集合如果关键码插入的次序不同可能得到不同结构的二叉搜索树最优情况下二叉搜索树为完全二叉树其平均比较次数为logN最差情况下二叉搜索树退化为单支树其平均比较次数为N/2