二叉搜索树

二叉搜索树(Binary Search Tree) link

graph TB
subgraph Binary Search Tree
  direction TB
  A((50))-->B((30))
  A-->C((70))

  B-->D((20))
  B-->E((40))
  C-->F((60))
  C-->G((80))
end

每个节点的左子树仅包含小于节点值的节点，右子树仅包含大于节点值的节点的树称为二叉搜索树(Binary Search Tree)。二叉搜索树具有以下特点：

• 二叉搜索树适用于存储有序列，它能以$O(H)$时间复杂度完成插入、删除、搜索、最值操作。
• 最坏情况下节点完全向一方倾斜，退化成链表时树高以$O(n)$为上界，操作的时间复杂度为$O(n)$。
• 最好情况下节点平衡因子小于等于1，平衡二叉树高以$O(\log n)$为下界，操作时间复杂度为$O(\log n)$。

自平衡二叉搜索树(Self-balancing BST)是一类在二叉搜索树插入和修改操作后通过轮换保持平衡性质以控制树高优化查询性能的树，常用的自平衡二叉搜索树有AVL树和红黑树。

二叉搜索树的插入和删除 link

二叉搜索树的插入操作一定在叶子结点，操作的步骤即根据二叉搜索树的从根节点向下寻找适合的叶子节点进行插入。

• 从根节点开始往下搜索，若数据小于当前节点则移动到左子树，若数据大于当前节点则移动到右子树。
• 若搜索期间发现数据等于当前节点说明数据已存储于二叉树中，中断插入流程返回。
• 寻找到最底部的叶子节点并插入数据，设置左节点还是右节点取决于当前数据与叶子节点的值。

二叉搜索树的删除操作需要从根节点向下搜索寻找待删除节点，根据待删除节点的子节点数量分三种情况处理：

• 待删除节点有0个子节点：其父节点的左或右指针置空后直接删除。
• 待删除节点有1个子节点：其父节点的左或右指针指向待删除节点的子节点后直接删除。
• 待删除节点有2个子节点：寻找其右子树中的最小值节点(右子树中最靠左且没有左子树的节点)覆盖待删除节点的值，然后按0或1个子节点的情况删除最小值节点。

二叉搜索树的封装 link