二叉搜索树可以只有两个分支吗？

Question

根据 GeeksForGeeks，二叉树在以下情况下是 BST：

节点的左子树仅包含键小于该节点键的节点。
节点的右子树仅包含键大于该节点键的节点。
左右子树也必须是二叉搜索树。

我想知道像下面这样的树是否仍然可以被认为是BST？

     3
   2   4
 1       5
0

Answer 1

一句话——是的。不要求树是“完整的”（即每个节点都应该有两个子节点。

Answer 2

是的，它满足要求，所以它是一棵二叉搜索树。即使这种退化的情况仍然是二叉搜索树：

        4
       /
      3
     /
    2
   /
  1 

出于效率的原因，可以更新（插入或删除）的二叉搜索树通常会重新平衡，以最小化它们的高度。存在不同的技术来平衡二叉搜索树。请参阅自平衡二叉搜索树。

Answer 3

要使树成为二叉树，每个节点必须具有至多两个子子节点（注意允许零个和一个子节点），叶节点（没有子节点的最后一个节点）必须指向NULL，节点不能创建循环引用（即它们不能链接到父节点）并且必须有一个根节点，这是树的开始。

要使二叉树成为二叉搜索树，节点的“左”分支应仅包含值较小的节点，“右”分支（子树）应仅包含值较大的节点。

要使二叉搜索树成为平衡二叉搜索树，需要考虑树的结构和高度。如前所述，这是一个有效的退化二叉搜索树：

1
 \
  3
   \
    4
     \
      10

但它与单链表没有什么不同，并且搜索具有线性复杂度，并且实际上甚至比数组遍历还要慢，原因有几个，例如节点在连续内存中未对齐并且可能在动态内存中分配以及。 平衡（例如使用自动平衡 AVL 二叉搜索树）或 DSW 平衡算法解决了这个问题，通过执行一系列左或右旋转操作，最终将两个分支的高度降低到 1 或 1 的高度差0. 节点的高度是从该节点到根的链接数（直观地表示为实线，正式称为“边”，尽管我确实发现这个术语有点含糊）。我提到的示例有 4 个节点和 3 个“边”，因此高度为 (h=4)。如果树是平衡的，它可能看起来像这样： 3 /
1 4
10

根部左枝（3）的高度为2，根部右枝（3）的高度为2，总高度差为1，保持了树的平衡。