7.3.1二叉排序树
知识总览：
二叉排序树定义：
又叫二叉查找树BST，满足左子树节点值<根节点值<右子树节点值，根节点的值>所有左子树的节点值，右子树的任何一个节点值>根节点值，各个子树又递归满足左子树节点值<根节点值<右子树节点值，进行中序遍历时左根右，则可以得到一个递增序列
二叉排序树的查找：
while循环非递归方式查找：
传入根节点指针+目标值，如果目标值和当前节点的值不匹配，值<当前节点值向该节点的左子树找即向左找，否则向右找，直到找到目标值或节点为空跳出循环
空间复杂度：需要常数级的辅助空间，效果更好更推荐
递归方式查找：
根节点为空---》直接返回失败，不为空比较根节点关键字大小是否和目标值相等，相等直接返回，不相等判断目标值<根节点关键字，则向根节点的左子树查找，否则向根节点的右子树查找
空间复杂度：递归算法取决于树的高度，一棵树有多高可能递归算法就要深入基层，每一层的递归都要在函数调用栈里多分配一块空间，即空间复杂度为O(h)和树的高度有关
二叉排序树的插入：
即插入一个元素还要满足左子树节点值<根节点值<右子树节点值
如插入12：判断当前树根节点不为空，则判断当前根节点值T=19>12(二叉树里边不允许2个节点的值相等，如果二叉树里边已经有目标值了即当前节点的值和目标值相等，则插入失败返回0)，则要把12插入左子树，即下一轮T->lchild=13，T不为空，判断T=13>12，则要把12插入13的左子树，即T->lchild=11,下一轮T不为空，判断T=11<12，则要把12插入11的右子树，即T->rchild=null,下一轮T为空则malloc申请一片空间，T->key=k即让申请的空间的key值==目标值，并让目标值左子树、右子树指针都设为null，再返回1表示插入成功
每次插入的新节点都是叶子节点，递归算法插入新节点最坏时间复杂度为树的高度即O(h)
二叉排序树的构造：
给定序列构造二叉排序树：
按照序列依次调用上边的插入节点的操作构造二叉排序树，不同的关键字序列(关键字的顺序不同)构造时可能得到相同的二叉排序树，也可能得到不同的二叉排序树
二叉排序树的删除：
1.先找到目标节点
(1)如果目标节点是叶子节点，则直接删除，仍能保证左子树节点<根节点<右子树节点
(2)如果目标节点z不是叶子节点，且目标节点z只有左子树或右子树，则删除该节点z之后，让该节点z的子树成为z的父节点的子树，代替z的位置，来满足左子树节点值<根节点值<右子树节点值
(3)如果目标节点z不是叶子节点，且目标节点z有左子树+右子树，则需要从删除的节点中的剩余子树里选出一个节点来代替目标节点根节点的位置，使之满足左子树节点<新节点<右子树节点值，
11》即新节点从z节点的右子树选，选右子树中最小的节点值，即右子树最左位置节点。即可中序遍历目标节点z的右子树(中序遍历可以得到一个递增序列)，则选择遍历的第一个节点值即最左边的位置一定<该右子树其他任意一个节点且>左子树任意节点值，选择该最左节点之后，因为是最左位置节点，所以该节点的子树中一定没有左子树(有了就不是最左位置了)，所以该节点只有右子树或没有右子树即是叶子节点
如下删除50,50既有左子树又有右子树，则采用50的右子树的最左边的一个节点即60在删除50后代替50的位置，然后相当于60又被删除，60是只有右子树的节点则回到情况(2)，删除后直接让63代替60的位置即可
22》即新节点从z节点的左子树选，选左子树中最大的节点值，即中序遍历目标节点z的左子树(中序遍历可以得到一个递增序列)选择遍历的最后一个节点值即最左边的位置，则满足一定<该右子树其他任意一个节点且>左子树任意节点值，选择该最右节点之后，因为是最右位置节点，所以该节点的子树中一定没有右子树(有了就不是最右位置了)，所以该节点只有左子树或没有左子树即是叶子节点
如下删除50,50既有左子树又有右子树，则采用50的左子树的最右边的一个节点即30，在删除50后代替50的位置，然后相当于30又被删除，30一定没有右子树，此时30是叶子节点，则回到情况(1)直接把30放到50位置即可
查找效率分析：
查找长度等同于时间复杂度，查找长度指的是在查找运算中找到目标值的过程中进行了几次关键字比较，每比较一次关键字相当于进行了一次循环或递归，所以查找长度的数量级应该和时间复杂度的数量级相同
查找成功ASL：
如下找关键字70经过了50、66、70的比较最终找到目标关键字，比较次数为3即该节点70的查找长度为3
整个二叉排序树的查找效率可以用平均查找长度ASL(成功)评估，一般认为各节点的查找概率相同
整个二叉排序树的ASL平均查找长度计算：认为每一个节点的查找概率相等，计算每层的节点的查找长度*节点个数，对其所有节点的查找长度求和再/节点个数=整个二叉排序树的ASL
如下图2的左1ASL：一共有8个节点，即每个节点被查找的概率为1/8。第一层节点只有50，比较关键字次数1即1*1，第2层2个节点26、66，需要各自都比较2次才能找到各自(如查找26，先比较50，再比较26)即2*2，第3层4个节点需要比较3次即查找长度为3才能找到该层目标值，即3*4，第4层1个节点需要比较4次即查找长度为4，即4*1，即ASL=(1*1+2*2+3*4+4*1)/8=2.625，很明显每层的关键字比较次数是相同的
如下图2的右1成功ASL：上同，ASL=3.75>2.625左一的ASL，则左1的查找效率>右2
查找长度即关键字对比的次数一定不会超过树的高度，即查找操作的时间复杂度最坏的数量级也就是和树高h相同，因此二叉排序树的查找效率很大程度上取决于树高是多少
对于有n个节点的二叉树，树高最小是log2n向下取整后再+1，最坏情况即树高最大情况是单支情况即树高h=n节点数，即平均查找长度为O(n)，则尽量让树高保持在log2n数量级是最好的，即让二叉树保持左子树和右子树的树高相差不超过1就能保持树高维持在log2n情况
查找失败情况ASL：
查找失败情况只能是在不存在的节点上，即首先把二叉树的不存在节点画上，即在二叉树的叶子节点上补充上不存在的节点，然后和存在的关键字比较来得出比较次数
如下最后一张图左1：把失败的节点画上，如图一共有9个不存在的节点，认为每个不存在的节点的概率相同即1/9。则开始判断第一层(二叉树中第4层)7个节点的关键字比较次数为3(如查找22，依次和50、26、21比较得出查找失败结论，其他同)，即3*7，第5层2个节点关键字比较次数为4(如查找69，依次和50、66、70、68比较得出查找失败结论，其他同)，即4*2，即整个二叉排序树的失败的ASL=(3*7+4*2)/9=3.22
如下最后一张图右1：上同ASL失败=4.22>3.22即左1失败效率更好，矮胖的效率更好
知识回顾：
又水一篇，不知道在写啥。。。。。。。。。。。。。。