二叉排序树：也叫二叉搜索树

要求：每个节点都大于左子树的每个节点的值，小于等于右子树的每个节点值。

alt

这种二叉树很容易实现搜索算法：复杂度是最坏树的深度，最优是lg（n）

当x=该节点时，停止搜索

当x<该节点时，搜索左子树

当x>该节点时，搜索右子树

删除：比较复杂，因为要保证他的性质不发生变化

可以采用懒惰删除的方式进行删除：需要删除的元素添加一个标记，标识被删除，当插入该键时，恢复标记。

二叉平衡树：也叫AVL树

要求：是一种特殊的二叉排序树，左右子数都是平衡二叉树，且左右子数的高度差的绝对值<=1

优点：解决了二插排序树的链表结构的查找复杂度为n的情况，最优和最坏都是log（n）。

缺点：频繁的插入和删除会频繁的重新平衡（通过旋转），导致效率下降。

要求：1.每个节点非黑即红，2.红色节点的左右子节点都是黑的，3.根节点是黑的，4.每个叶子节点都是黑的， 5.任意一个节点到叶子节点的每条路径的黑色节点数相同。

特点：每个节点添加一个存储位来表示颜色，这样确保没有一条路径会比其他路径长出两倍，因此是一种非严格平衡二叉树，搜素，插入和删除较多的情况使用。 插入最多两次旋转，删除最多三次旋转

优点：插入删除查找都是log(n)，性能比较稳定，相当于是二叉平衡树的一种折中。