二叉搜索树介绍与实现
一、引言
ps：文中对数均以2为底！
要实现搜索，插入，删除三个功能，你会使用什么数据结构呢？
A说：那不简单吗，直接用数组啊！
B说：那还用问！肯定是链表啊！
我们来看看他们说的情况是什么样子的。
可以看到，这三个操作他们的时间复杂度。
对于未排序的数组，搜索需要遍历数组，最坏的情况是O（n），删除是搜索到再删除，并且可能需要移动其他元素所以时间复杂度最坏为O（n），插入直接插在尾部为O（1）。
对于链表其实和数组大差不差。插入插在头部为O（1）。检索和删除依然需要遍历。
这里的查询需要花费大量时间！比如查询一亿的数据，而每次查询需要一毫秒，那么相乘一下就非常恐怖了。🐧
这个时候，C站出来了！他说：你这数组不对劲啊！如果我用已经排好的数组来呢！
搜索的log_2代表以2为底的对数！
我们对数组的查询使用的是二分查找，也就是从右往左查找，相当于对半分。比如要插入个3，只要end指针检索到比3大的第一个数字也就是4，就找到了他要的位置（索引3的位置）。
但是插入和删除依然是O（n），因为都关联到了元素像后移动！
很显然，这三种数据结构都有各自的痛点，所以今天的主角就出来了！
二、二叉搜索树介绍
二叉搜索树（BST——Binary Search Tree）对于上面三个操作方式的时间复杂度都是O（log_2(n)），这相当好！
比如总数据量是2的31次方，那么O（n）依旧要查询天文数字，而我们利用BST只需要查31次！
但是二叉搜索树有个前提——必须保证数平衡！（平衡指的是左子树和右子树的高度差小于等于1，忘了可以看看我的关于二叉树的文章！😡）
二叉搜索树的性质：是一种二叉树，其中的每一个节点，所有左子树的节点值都比他小或相等，右子树都比他大！
举个栗子。
我们来修改一下，看看是否还是合理的？
我将左边的一颗节点改为了16，这还合理吗？
对于圈圈里的10节点来说，依然满足条件！但是对于跟节点15来说，左子树里面有一个比他大的值——16！所以这不符合二叉搜索树！
如果我们将这颗树放在数组里面，是可以二分查找的！
（上面图片的16忘记换过来了，卧槽！我的！记住16改成12！）
比如我们要搜索10，就可以从右边end指针动手（ps：我们用start和end指针标记搜索空间）。
我们将需要搜索的值和搜索空间中间的值也就是15作比较，如果比15小，那么我们会缩减一半我们的搜索空间！
也就是end指针跑到了12的位置，接着继续重复直到搜索到与要搜索的值一致。
也就是说，这样的二分查找，搜索空间会经历：n->n/2->n/4······的变化。
n/2/2/2/2/2······=1，总共k个2，也就是2**k=n，k=log_2(n)，k为搜索次数！
我们用这个图里的二叉树模拟一下。
从根节点开始，与要搜索的值进行比较，比如我们要查12，12比15小，那么就会去查左子树。实现了第一个对半分。
这样搜索空间就只有三个节点（10，8，12），接着和10节点比较，12大，那么查右子树，又是一个对半分。
这样搜索空间就变成了只有一个节点，我们也就找到了12！
每一步我们不是往左就是往右所以能实现砍一刀的效果。
三、不能利用性质的二叉搜索树
这是一颗二叉搜索树，但是他不平衡！所以就相当于一个普通的链表，无法利用二分查找。
这张则是平衡的二叉搜索树，完全可以利用性质！
所以我们平常追求的还是满（完美）二叉树，美观又美观又美观又好用🫨
我们来演示一下插入
插入19会先跟root比，比他大走右边，接着跟20比，再和17比，17没有右孩子，所以在此创建😎
注意二叉搜索树在插入删除的途中，可能会造成不平衡！这个我们日后再谈🫡
四、cpp实现
首先是创建节点，这个我们在之前已经演示过了，注意要在堆里面创建哦！
我们将一直保存根节点的地址！
struct BstNode{ int data; BstNode* left; BstNode* right;};现在我们要插入几个节点组成二叉搜索树
void Insert(BstNode *root,int data){
}int main(){ BstNode *root =NULL;//创建一个空树 Insert(root,15); Insert(root,10); Insert(root,20);}很显然，我们要实现插入函数！
首先，我们先来实现一个创建新节点的函数！
BstNode* GetnewNode(int data){ BstNode* newNode=new BstNode();//在堆上面申请内存,地址保存在指针里面，方便我们操作 newNode->data=data; newNode->left=NULL; newNode->right=NULL; return newNode;}接着撰写inset函数
BstNode* Insert(BstNode *root,int data){ if(root==NULL){//处理空树的情况 BstNode* newNode=GetnewNode(data); root = newNode; return root;//返回的是堆里面的地址 }}我们在这里返回了root！因此main函数得传入root
int main(){ BstNode *root =NULL;//创建一个空树 root=Insert(root,15); root=Insert(root,10); root=Insert(root,20);}为什么要传入root？因为在insert函数里对root的操作是在栈上的，函数一结束就会被回收！
并且在main函数里必须要用root接收！要不然会内存泄漏，丢失节点！
int main(){ BstNode *root =NULL;//创建一个空树 root=Insert(root,15); Insert(root,10);//比如这里没接受 print(); root=Insert(root,20);}在第四行没接收到root，相当于直接丢失了含有10这个节点的插入链接（形参root被修改，但是main里的root没有被修改）。
（ps：这里可能会弄混我在c指针里讲的函数返回指针，如果新调用了一个函数，可能会内存泄漏。你觉得这里会吗？答案是不会！为什么？因为我们在Insert函数里创建的node是new出来的，root也是指向它的，不会被覆盖掉！）
其他实现操作root的方式还有
传入root的地址，这样insert函数也得被修改。这个方法较为复杂，需要你对指针非常熟练
void Insert(BstNode **root,int data){ if(root==NULL){//处理空树的情况 BstNode* newNode=GetnewNode(data); *root = newNode; }}int main(){ BstNode *root =NULL;//创建一个空树 root=Insert(&root,15); }接着就是利用全局变量，这个不多说了，生产环境里很少用。
好了！在空树的情况下走一遍Insert函数会变成如下情况。
接着我们来解决插入左右子树的问题，这里使用的方法是递归！递归在树形结构里面是非常常用的！
BstNode* Insert(BstNode *root,int data){ if(root==NULL){//处理空树的情况，也是链接的关键（左孩子或者右孩子为空也走这个入口） BstNode* newNode=GetnewNode(data); root = newNode; return root; } else if(data<=root->data){ root->left=Insert(root->left,data); } else{ root->right=Insert(root->right,data); } return root;}我们再插入一个10，模拟一下。
这里利用递归的特性链接了节点，控制流如上图。底下的Insert走完后，会把连接上的新节点地址（也就是150返回给上一个函数调用，上一个函数调用接受了地址，并把他作为当前节点的左孩子地址！）
我们再写一个在BST里查询数据的函数。
完整cpp代码
#include<iostream>using namespace std;struct BstNode{ int data; BstNode* left; BstNode* right;};BstNode* GetnewNode(int data){ BstNode* newNode=new BstNode();//在堆上面申请内存,地址保存在指针里面，方便我们操作 newNode->data=data; newNode->left=NULL; newNode->right=NULL; return newNode;}bool Search(BstNode* root,int data){ if(root==NULL)return false; else if(root->data==data)return true; else if(data<=root->data)return Search(root->left,data); else return Search(root->right,data);}BstNode* Insert(BstNode *root,int data){ if(root==NULL){//处理空树的情况 BstNode* newNode=GetnewNode(data); root = newNode; return root; } else if(data<=root->data){ root->left=Insert(root->left,data); } else{ root->right=Insert(root->right,data); } return root;}int main(){ BstNode *root =NULL;//创建一个空树 root=Insert(root,15); root=Insert(root,10); root=Insert(root,20); int number; cout<<"please input number"; cin>>number; if(Search(root,number)==true)cout<<"found"; else cout<<"not found";}部分信息可能已经过时