首页 文章

为二叉搜索树创建随机密钥

提问于
浏览 次
2

我的目标是为伪帕斯卡代码的编译器创建一个BST（二进制搜索树） .

据我所知，BST的工作原理如下：我有一个根，它有一些关键 - 依赖于我的生成密钥（如果它大于或小于根密钥）我从根向左或向右插入一个节点 .

显然，如果我使用数字作为键，树将会像：

1
 \
  2
   \
    3

我想要的是 balancer 的BST，如下所示：

1
 / \
2   3
... etc.

这些钥匙显然不会发生这种情况 . 当我想要实现这种结构时，节点的键应该如何？有没有办法在不记住最后插入的密钥的情况下执行此操作？

这也让我想到了什么“关键”应该用于树的绝对根？所以我可以从左边和右边添加按键？

binary-tree

2 回答

  • 1

    插入节点时，从根节点向下移动以找到正确的插入点：

    1     1     1
       \     \
        2     2
               \
                3

    插入后，当您返回到root时，在检查每个左右节点是否足够 balancer 的路上 . 如果没有，你可以旋转它们：

    1         2
 \       / \
  2     1   3
   \
    3

    这意味着更深分支的第一个节点到达新的根节点，旧的根节点将成为该节点的子节点 .

    因此，根节点将在必要时更改，并始终具有“最中间”值 .

    回复于
  • 2

    应用 AVL tree 的概念来 balancer 树结构 .

    根据您的要求：

    1
   / \
  2   3

    上面的树是在考虑 binary tree 而不是 binary Search Tree 的情况下构建的 .

    然而，上面提到的树可以通过从上到下和从左到右的方式构建 .

    回复于

相关问题