数字搜索树如何工作？

How Digital search trees Work?

我尝试了很多在线资源，但我无法理解数字二叉搜索树 works.Below Link 的示例，供您参考 (LINK: http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec15/lec15-10.html)

是否有人使用这些值构建了一棵树并详细说明了它是如何工作的？

A   00001
S   10011
E   00101
R   10010
C   00011
H   10100

树的构造方式是键的二进制表示 (A,S,E,R,C ,H) 可用于将它们定位到树中。在每个搜索步骤中，将关键字与当前节点（当前搜索三个节点的根）进行比较。如果密钥不是根，则密钥二进制表示的最高有效位用于 select 左子树（如果该位为 0）或右子树（如果该位为 1).更详细地解释了此过程 here。

在您提供的示例中，密钥H（二进制表示10100）可以如下找到。

  1. 第一步，根是节点A。由于A不等于H，所以使用1位，表示应该选择右子树。因此，我们考虑节点 S 和位串 0100，它们是通过省略最高有效位从原始二进制表示中产生的。

  2. 由于A不等于H，我们使用最高位，即0，表示左子树的选择。我们考虑节点 R 和位串 100.

  3. 由于R不等于H，我们再次使用最高有效位，即1，这意味着右子树是选择。我们考虑节点 H 和位串 00.

  4. 由于 H 等于 H，我们找到了所需的键，搜索终止。

DST 的工作方式类似于逐级检查位。如果 o 然后向左移动或向右移动，则检查位的开始。同时它将位位置与电平进行比较。

例如：
Root在O级，

  • 如果要插入的位在第 1 级，则检查第 1 位，
  • 如果为 0 则在左侧插入，如果为 1 则在右侧插入。

与第二层类似，检查要插入的第二位，并像这样对其余层进行操作。

在给定的例子中；

首先A(00001)为根节点，然后S(10011)从1开始，向右移动插入。

接下来是E(00101)，因为0向左移动插入，所以序列中接下来是R(10010)，因为1向右移动，所以第二个位置的位是0所以插入作为 S.

的左 child

序列中next是C(00011),0所以向左移动因为第2位是0插入左边,next是H(10100),因为是从1开始向右移动,所以必须作为第 3 级插入，因此请检查第 3 位位置是否为 1，它插入在右侧。

希望这会消除您的疑虑。 所以最终的夏令时看起来像这样 [夏令时] [1]: https://i.stack.imgur.com/Iet4n.gif