tree-balancing_编程技术问答社区_程序员问答知识库

以下是关于 tree-balancing 的编程技术问答

语法平衡问题

是否可以强制 boost.spirit qi 以这种方式行事，生成的语法将根据一些运行时间计算条件/规则/速率调整?例如，输入由语言构造组成，导致在解析过程中不同的替代方案，更频繁地，其他人 - 少.但替代方案的顺序会影响效率，即语法的运行时最优性.在某些情况下，不可能预先确定在任意输入的情况下更常用的替代方案(可能是强烈聚类). 我知道，可以在运行时将符号附加到qi::symbols，但是对于一些其他解析器来说是期望类似的行为. 解决方案你可悲地忘记(?)包括样本语法.所以我自己构成了.它解析了这样的语言: begin declare x : int; declare y : string; let x = 42; let y = "Life the universe and everything"; for(ch : y) begin if (call is_alpha(ch))

10 2023-01-28 编程技术问答社区 c++ boost-spirit boost-spirit-qi tree-balancing

左侧平衡二叉树

我正在阅读数据结构上的书，它说左平衡二叉树是一棵树，其中叶子只占据最后一个级别的最左边的位置. 这对我来说似乎有点含糊.这是否意味着叶子仅在根的左侧并且在整个级别的左侧分布，或者仅在整个树的左侧存在.究竟是什么构成左平衡? 我不确定我的猜测甚至涵盖了任何答案，所以如果有人可以提供帮助，那就会非常感谢: - ). 解决方案您可以将左平衡二叉树视为平衡二叉树，其中每个节点的左子树填充在右子树之前.在更惯常的术语中，这是一个树，其中底部最级别的节点都在整个树的左侧. 拍摄此树: 这棵树是平衡的，但不是留下平衡.但是，如果删除节点67，则树将是左平衡的. 其他解决方案在我看来，左平衡二叉树的定义是完整的二叉树的定义. 其他解决方案我真的不知道答案，但基于书中的描述它听起来像这样... 为初学者，让我们以这种方式想到它.树中的每个"行"有一个数字，从零开始并计数.数字最高的行被认为是最后一个级别. 记住，叶节点是没有任何孩子的节点.

56 2023-01-27 编程技术问答社区 binary-tree tree-balancing

计算二进制搜索树中高度的最佳方法？ (平衡AVL-树)

我正在寻找计算节点平衡的最佳方法.我以为我可以工作，但是经过一些大量的插入/更新后，我可以看到它无法正常工作(根本无法正常工作). 这是一个分为两部分的问题，第一部分是如何计算子树的高度，我知道定义"节点的高度是最长的向下路径的长度从该节点上的叶子." 我理解，但是我无法实现它.为了进一步让我感到困惑，可以在树上的wikipedia上找到"常规上，值-1对应于无节点的子树，而零则对应于带有一个节点的子树./p> 第二部分是在AVL树中获得子树的平衡因子，我毫无疑问地理解了这个概念，"获得L和R sub-的高度从L" "中减去R.这被定义为这样的东西:BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT] 在Wikipedia上阅读在前几行中说明了插入AVL树的前几行:"如果平衡因子变为-1、0或1，则该树仍处于AVL形式，无需旋转." 然后继续说，这"如果平衡因子变为2或-2，则扎根于该节点的树是不平衡的，并且需要树旋转.最多需要单个或双

18 2023-01-27 编程技术问答社区 algorithm data-structures binary-tree avl-tree tree-balancing

在函数式编程中，什么自平衡树是最简单的？

我正在Haskell设计一棵自我平衡树.作为练习，因为很高兴有您的背手. 以前在C和Python中，由于简单的平衡规则，我更喜欢Treaps和splay树.我总是不喜欢R/B树，因为它们的工作似乎比他们值得更多. 现在，由于哈斯克尔的功能性质，事情似乎已经改变了.我可以在10行代码中编写R/B插入功能.另一方面，TREAP需要包装来存储随机数生成器，而张开的树是自上而下的痛苦. 所以我问您是否有其他类型的树木经验? 哪些更好地利用功能语言的模式匹配和自上而下的性质? 解决方案好吧，我想回答这个问题没有很多参考或研究.相反，我花了一些时间尝试您的不同想法和树木.我没有发现比RB树更好的东西，但这也许只是搜索偏见. RB树可以(插入)用四个简单规则平衡，如 Chris Okasaki 显示: balance T (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d) balance T (T

28 2022-10-29 编程技术问答社区 haskell functional-programming tree tree-balancing

Prolog-平衡树或不平衡树

我想编写一个程序来告诉我一棵树是否平衡.在这种情况下，平衡意味着相同的高度或 1 的高度差. 这是我目前所写的，但对于 1 的高度差不起作用.为什么? balanced(l(_)). balanced(b(B1, B2)):- height(B1,H), height(B2,H), balanced(B1), balanced(B2). balanced(b(B1,B2)):- height(B1,H + 1), height(B2,H), balanced(B1), balanced(B2). balanced(b(B1,B2)):- height(B1,H), height(B2,H + 1), balanced(B1), balanced(B2). 解决方案如果你不告诉 Prolog 进行算术评估，H + 1 不会被评估为 H 的值加一；相反，Prolog 用 + 作

72 2022-08-15 编程技术问答社区 prolog tree-balancing

AVL树形平衡

我正在处理一项要求我实现 AVL 树的任务.我很确定我的轮换方法是正确的，但我无法确定何时使用它们. 例如，书中的解释说我应该爬上与插入节点/元素相同的路径.但是，我不能有任何父指针. 最新代码: public BinaryNode insert(BinaryNode node) { if (this.getElement().compareTo(node.getElement()) > 0) { if (this.getLeftChild() != null) { BinaryNode b = this.getLeftChild().insert(node); if(!this.isBalanced()) { this.balance(); } return b; } else {

142 2022-08-15 编程技术问答社区 java avl-tree tree-balancing

AVL二进制堆(平衡性测试)

我正在尝试测试一棵树是否是 AVL 树或不使用 prolog. 我做了一个高度测试，适用于我目前所做的测试，但我的平衡测试仍然不强. 这是我目前的工作: avl('Branch'(LeftBranch,RightBranch)) :- height(LeftBranch,H1), height(RightBranch,H2), abs(H1-H2) =

124 2022-08-15 编程技术问答社区 tree prolog heap balance tree-balancing

计算二进制搜索树中高度的最佳方法？ (平衡AVL-树)

我正在寻找在 AVL-tree 中计算节点余额的最佳方法.我以为我可以正常工作，但是经过一些繁重的插入/更新后，我可以看到它(根本)无法正常工作. 这是一个两部分的问题，第一部分是如何计算子树的高度，我知道定义“节点的高度是最长向下路径的长度到那个节点的叶子." 我理解它，但我未能实现它.为了让我更加困惑，这句话可以在 wikipedia on tree-heights 上找到 “通常，值 -1 对应于没有节点的子树，而 0 对应于具有一个节点的子树." 第二部分是获取AVL树中子树的平衡因子，我理解这个概念没有问题，“获取你的L和R子的高度-树并从 L" 中减去 R.这被定义为:BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT] 阅读维基百科在描述插入 AVL 树的前几行中这样说:“如果平衡因子变为 -1、0 或 1，则树仍处于 AVL 形式，不需要旋转." 然后继续说这个“如果平衡因子变为2或-2，则以该节点为根的树是不平衡的

3404 2022-07-19 编程技术问答社区 algorithm data-structures binary-tree avl-tree tree-balancing

在没有轮换的情况下保持avl树的平衡

b树是自平衡树，如avl树. 在这里我们可以看到左右旋转如何保持avl树平衡. 和这里是一个解释插入的链接B树.如果我没有错，这种插入技术不涉及任何旋转，以保持树平衡.因此它看起来更简单. 问题:是否有类似(或任何其他技术而不使用旋转)以使AVL树平衡? 解决方案答案是...是和否. b树不需要执行旋转，因为它们有一些懈怠，其中它们可以将它们包装到节点中的不同键.当您在B树中添加越来越多的键时，您可以避免通过将这些键吸收到节点本身来避免树丢失. 二叉树没有这种奢侈品.如果将密钥插入二叉树，则在所有情况下将该树中的某些分支的高度增加1，因为该密钥需要进入其自己的节点.旋转通过确保某些分支生长太多，使其落入树的其余部分时，旋转通过确保. 大多数平衡的BST有一些涉及旋转的重新平衡策略，但并非所有人.一个值得注意的策略的例子，它不会直接涉及旋转是 scapegoat树，哪个重新平衡将巨大的子树撕掉出主树，最佳地重建它们，然后将子树粘在一起.这种方法并不技

370 2022-07-19 编程技术问答社区 algorithm data-structures b-tree avl-tree tree-balancing