【5.4】二叉搜索树

一、二叉搜索树

Binary Search Tree(BST)

  • 或者是一棵空树;
  • 或者是具有下列性质的二叉树:
    • 对于任何一个结点,设其值为K
    • 则该结点的 左子树(若不空)的任意一个结点的值都 小于 K;
    • 该结点的 右子树(若不空)的任意一个结点的值都 大于 K;
    • 而且它的左右子树也分别为BST

性质: 中序遍历是正序的(由小到大的排列)

BST示意图:

二、例子

检索 19

  • 只需检索二个子树之一
    • 直到 K 被找到
    • 或遇上树叶仍找不到,则不存在

插入17

  • 首先是检索,若找到则不允许插入
  • 若失败,则在该位置插入一个新叶
  • 保持BST性质和性能!

BST删除(值替换)

找rt右子树中最小结点,并删除

三、二叉搜索树总结

  • 组织内存索引
    • 二叉搜索树是适用于内存储器的一种重要的树形索引,常用红黑树、伸展树等,以维持平衡
    • 外存常用B/B+树
  • 保持性质 vs 保持性能
    • 插入新结点或删除已有结点,要保证操作结束后仍符合二叉搜索树的定义

思考

怎样防止BST退化为线性结构?

允许重复关键码吗?(插入、检索、删除)

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学