基本算法|图解各种树（二）

—

二叉搜索树

二叉搜索树，又称为二叉排序树，简写为 BST，它与线性表，链表，二叉树间的关系，二维链表近似是二叉树，BST继承了二叉树，同时个性化的东西是实现了有序线性表（sorted vector）, 如下所示：

继承BST的一种平衡树是BBST，平衡二叉搜索树，会在之后介绍它的几种典型代表。

BST长得样子：

这是BST：

这不是BST（因为右子树的某个节点2小于3）：

因此，BST的严格定义：任一节点不小于/不大于其左/右后代；

任一节点不小于/不大于其左/右孩子，这是错误的！

在以上讨论基础上，再加一个限制，不允许有重复的词条。

—

BST的增删查

BST的查找一个关键码和增加一个关键码的操作相对容易，不再详述。

BST删除一个关键码，与以上两个操作相比，略显复杂。

分两步：

第一步，交换36和右子树的最小节点（最左节点）

第二步，可以看到经过第一步后，一定可以转化为单分支的情况，

因此按照第一种情况的处理方法：

—

BST问题

我们关心二叉树的高度，BST的平均高度是n^0.5，n是节点个数，极端情况退化为n。

而我们期望树的理想高度是logn，如何实现呢？

—

二叉树的平衡

二叉树实现高度平衡的秘诀是什么？

两种旋转变换：zig 和 zag

zig变换：

zag变换：

两种变换，变化前后，中序遍历次序保持不变。

后续推送

平衡二叉树，其实现方法，包括：AVL树，伸展树，红黑树，还有平衡的多叉树：B-，B+，B*。