二叉搜索树总结

二叉树->二叉搜索树->B树／B＋树／红黑树。

二叉树：每个节点最多两个子节点。

二叉搜索树：二叉树，且满足如下性质：

设x为二叉搜索树中的一个节点，如果y是x左子树的一个节点，则y.key <= x.key；如果y是x右子树的一个节点，则y.key >= x.key。

二叉搜索树的遍历：

先序遍历：先访问当前节点x，再访问x的左子树x.left，最后访问x的右子树x.right。

中序遍历：先访问当前节点x的左子树x.left，再访问当前节点x，最后访问x的右子树x.right。

后序遍历：先访问当前节点x的左子树x.left，再访问当前节点的右子树x.rgith，最后访问x。

遍历二叉搜索树其实就是遍历二叉树，因为根本就没用到二叉搜索树的特性。根据二叉搜索树的特性，中序遍历得到的就是从小到大排序的结果。如果用递归算法完成遍历，其时间复杂度为O(n)，n为二叉搜索树的节点个数。

二叉搜索树BST是一棵排好序的节点序列，若要查找节点元素z，则从BST的根节点root开始查找，算法的时间复杂度为O(h)，h为二叉搜索树的高度。

与一般二叉树不同，二叉搜索树本身有序，所以，它还提供了查找最大值、查找最小值、查找某个元素x的前驱、查找某个元素x的后继等。

查找最大值：

算法的时间复杂度为O(h)，h为二叉搜索树的高度。

查找最小值：

算法的时间复杂度为O(h)，h为二叉搜索树的高度。

查找前驱：

算法的时间复杂度为O(h)。

查找后继：

算法的时间复杂度为O(h)。

节点插入：

对于任何值的节点，都可以作为叶子节点插入。

节点插入的复杂度为O(h)。

节点删除：

对于删除函数，其复杂度由左右子树均为非空情况中的行决定，其复杂度为O(h)。

【广告时间：阿里云小站官方上云，近期优惠就用阿里云ECS云服务器。】