一、概述，循关键码访问
二叉搜索树是一种树形结构，可以说是vector和list的结合版，简称BST，平衡二叉搜索树是其中的一种，简称BBST。与其他数据结构一样，二叉搜索树也是有一组数据项所构成的集合，但与其他数据结构不同，二叉搜索树的访问方式采用的是循关键码访问（call-by-key)其中每一个数据项都拥有一个关键码key，每一个key也有与其对应的value.每一个数据项都有其唯一代表的值，称为关键码，通过关键码访问数据的方式我们称作循关键码访问。关键码支持比较和比对，数据集合中的每一个数据项都可以统一的表示和实现为词条（key,value)的形式,，词条也可以进行比较和比对，如果此树不能，那么就要进行操作符重载。这样一来，每一个数据项就有了其对应的三个要素：key-词条-关键码。
二、单调性和有序性，查找操作
另外，二叉搜索树为了方便搜索，其整棵树具有有序性和单调性，也就是说，每一个节点都不大于他的右后代，不小于他的左后代（不能是孩子），正是因为有了这样的规律，才使得每一颗二叉树的中序遍历具有单调递增性，我们可以发现，此时他已经变为了一个数组，这也是为什么我们刚才说BST是vector和list的结合，
二叉搜索树是用来查找，插入，和删除的，查找时秩只需比较查找的关键码和当前节点关键码即可。当需查找的关键码不小于当前关键码，则前往他的右孩子，反之亦然。当查找成功（关键码成功匹配时）或查找失败（其到达叶节点时查找结束)。
hot
不得不提的是，二叉搜索树中有一个常见的接口，其在插入操作，删除操作或其他的操作中经常用到，就是高度指向，也叫深度指向，其意思顾名思义就是指向当前深度的变量，一般写作_hot,hot是引用值类型当查找成功时，将返回想要查找的点的父节点，为了使语义统一，失败时将构造一个当前节点，再返回其父节点，也就是当前路径上最后一个真实存在的结点…。
三、插入和删除
插入操作较为简单，只需要依照查找的步骤找到需要插入的位置，随即进行插入就好了。
而删除操作就较为复杂了，其关键在于如何在删除以后继续保持树内部的有序性和单调性。
一般分为三种情况：
1，无后代
需要删除的结点是叶节点，没有孩子，其直接删除即可，不用维护。
2、单分支
需要删除的结点只有左后代或只有右后代，操作也比较简单。删除此节点后只需将他的父节点和他的子节点直接连接即可
3、双分支
就是需要删除的结点既有左孩子也有右孩子。我们可以通过一个很巧妙的方法将其删除，既然删除单分支结点如此简单，那么我们可以把问题化繁为简，也就是说，把双分支化为单分支，那么如何确定哪个结点一定是单分支呢，我们通过前面讲的二叉搜索树的中序遍历有序性可以不难得出，此节点的最近后继和前继一定是单分支结点，这样我们可以让需要删除的结点和其任意一个交换，再利用单分支结构的删除方法，将其删除即可，下面给出图示：
至于交换后树为何还能保持一颗BST，利用其中序遍历的单调性不难证明。
四、复杂度
二叉树虽然是一个很方便的树形结构，但却不够紧凑，其很难维护成比较方便的平衡二叉查找树，而如果树的形态维护的不够好的话，就会使其效率大打折扣。比如最坏情况下，树就会变成标准的一位链表，这时不论查找插入删除都打不到我们希望的O(logn).这个时候，我们需要对树的形态进行维护，如果变成一颗BBST，那么维护成本太高，也很难继续保持，这种形态是可遇不可求的，此时我们引进了一种新的概念，叫适度平衡，其维护成本不高，平均复杂度也能渐进达到我们所期望的的效果，但与BBST还是无法相比，其适度平衡树，是指树保持一定的平衡，其维护成本很低的树的形态，代表有AVL树（下篇会讲），红黑树等…。