二叉搜索树

二叉搜索树

• 二叉搜索树: 又称二叉查找树、二叉排序树,是应用非常广泛的一种二叉树,简称 BST,其有如下特点:
  • 任意一个节点的值都大于其左子树所有节点的值
  • 任意一个节点的值都小于其右子树所有节点的值
  • 它的左右子树也是一颗二叉搜索树
  • 二叉搜索树可以大大提高搜索数据的效率,二叉搜索树添加、删除、搜索的最坏时间复杂度均可优化至
  • 二叉树存储的元素必须具备可比较性,如果是自定义类型,需要制定比较方式
  • 不允许为 null

添加节点

• 找到父节点 parent
• 创建新节点 node
• parent.left = node 或者 parent.right = node
  遇到值相等的元素,建议覆盖旧值

元素的比较方案设计

1、允许外界传入一个 Comparator 自定义比较方案
2、如果没有传入Comparator,强制认定元素实现了 Comparable 接口

删除叶子节点

• 直接删除
  如果 node == node.parent.left , 设置 node.parent.left = null
  如果 node == node.parent.right, 设置 node.parent.right = null
  如果 node.parent == null,设置 root = null

删除度为 1 的节点

• 用子节点替代原节点的位置, child 是 node.left 或者 child 是 node.right, 用child 替代 node 的位置

如果 node 是左子节点: child.parent = node.parent, child.parent.left = child

如果 node 是右子节点: child.parent = node.parent, node.parent.right = child

如果 node 是根节点: root = child, child.parent = null

删除度为 2 的节点

• 先用先驱或者后继节点的值覆盖原节点的值
• 然后删除相应的前驱或者后继节点
• 如果一个节点的度为 2,那么它的前驱、后继节点的度只可能是 1 和 0