二叉搜索树（BST）

基本概念

• 概念

  对于二叉搜索树、平衡二叉树、红黑树，只需要了解背后的原理，暂时不要求掌握代码实现（例如二叉搜索树，虽然代码简单，但基本用不到，因为效率太低）

  二叉搜索树（Binary Search Tree），也称二叉排序树，简称BST。

  此二叉树若左子树非空，则左子树所有节点的值均小于根节点的值；此二叉树若右子树非空，则右子树所有节点的值均大于根节点的值。左右子树也是一颗二叉搜索树

  总结为 左 < 根 < 右。即二叉搜索树的中序遍历结果为升序，此性质红黑树也要用到

• 二叉搜索树的插入

  根据BST的特性，从根结点的位置一路向下查找，直到找到一个空位置，放入即可

  易知，时间复杂度也是树的高度h，极端情况下，时间复杂度为O(N)

  

• 二叉搜索树的删除

  删除操作分为三种情况：

  • 删除的结点为叶子结点

    直接删除即可

  • 删除的结点只有左子树或右子树

    让左子树或右子树，替代删除的结点

  • 删除的结点有左右子树

    • 方法一

      用左子树的最大结点替换，再删除左子树的最大结点

    • 方法二

      用右子树的最小结点替换，再删除右子树的最小结点

    注：

    • 无论是方法一还是方法二，本质都是找到离删除结点最近的结点，替换后，再删除

    • 最近的结点，指中序遍历的前后结点：

      

• 二叉搜索树的查找

  根据二叉搜索树的特性，一路向下查找即可

  根据查找的过程可知，查找算法的时间复杂度为树的高度h；若二叉搜索树分布比较均匀时，h的时间复杂度为 \(O(log(N))\)

• 二叉搜索树的意义

  创建BST其实并不是为了排序，而是为了快速插入、删除、查找元素。因为BST树不是那么极端的话，树高维持在 \(logN\) 的范围内。但是不能杜绝极端情况，故还需要学习其他种类的二叉树