问题标签 [tree-balancing]

这里是c中的一个简单的二叉树，但是好像不平衡，怎么让它平衡呢？

代码：

我正在编写一个 AVL 树类，我的教授已经对我们的代码进行了一些测试。除了三个之外，我已经通过了所有测试，而我没有通过的三个测试似乎表明，当元素被添加到树中或从树中删除时，树在必要时不会自我平衡。我一直在尝试调试它，但我似乎无法找到错误。有人可以指出我缺少什么吗？

编辑： 失败的测试： RemoveRoot - 删除 AVL 树的根并用它的继任者替换它。AddManySingle - 添加几个元素并强制单次旋转。AddManyDouble - 添加几个元素并强制双旋转。

so as fun i decided to write a simple program that can solve the 8 Out of 10 Cats Does Countdown number puzzle, link is form Countdown, but same rules. so my program simply goes through a all possible combinations of AxBxCxDxExF, where letters are numbers and "x" are +, -, / and *. here is the code for it:

and here is what i use to test if the combination is what i want to not.

so in last episode i found a problem with my code. this was the solution to one of the puzzles.

i noticed that i do find this combination "10*7-8*3+7" (twice), but because i check for solutions by doing the operation left to right i actually don't find all answers. i only check for solutions like this ((((10*7)-8)*3)+7). so even though i found the combination i don't have the right order.

so now the question is how do i test all possible math orders, like (10*7)-(8*(3+7)), (10*7)-((8*3)+7) or 10*(7-8)*(3+7)? i though i can use a balance tree with operations as balancing nodes. but still i have not idea how to go through all possible combinations without moving around the formula.

how do i do this in code? not looking for solved code more of how i should change perspective to fix it. i don't know why i am stumped at it.

about me: 4th year computer science, not new or noob at programming (i like to believe at least ;))

我正在阅读编码书，其中一个问题要求编写一个函数来检查二叉树的高度是否平衡。例如，如果一棵树的右子树的高度为 4（意味着它的深度为 4），而左子树的深度为 6，则它不平衡，但如果它偏离 1，则没关系。

所以我实现了这个逻辑：

但我认为根据解决方案的解释可能是错误的，但我不明白为什么。以下是简化的类：

这是创建图形和调用函数的主要位置：

我试图让二叉搜索树平衡，我知道它为什么不起作用，但我不知道如何解决它。我直接在插入方法中进行平衡。我画了一些斜线来说明平衡应该发生的地方。像这样代码不起作用，我得到这个异常：

当我在没有平衡的情况下插入时，一切都很好。

我有一类BST。我需要一个递归函数Rotate，它将 BST 的根作为参数并返回一个平衡的 BST。

附件是仅平衡一个节点的代码，但它不适用于根节点。

我想让它递归，以便平衡整个树而不是单个节点。

在我的数据库课上，我的教授正在描述从 B+ 树中删除键。如果你看到下图：

除了他告诉leaf level节点最多只能包含3密钥的部分之外，我完全理解了所有内容。根据我的理解，根据 的深度B+ tree，在叶级别决定的总键值从dd到2*d树的深度不等。既然这里d的叶子是2，为什么叶子级别的节点不能有4键。我哪里错了？

根级别包含的密钥总数在这里也很重要吗？谁能解释一下

这是序列 20,10,5,30,40,57,3,2,4,35,25,18,22,27 我已经尝试过将每个新插入的节点都设为根，但它不起作用。谁能给我一步一步的解释？

我现在正在编写一个 CART 树的实现，它是机器学习中使用的二叉树。它是递归训练的，如以下代码所示：

现在假设我将训练迭代的次数限制为一个选定的值，比如nTraining=4。

然后，通过展开递归函数调用，我希望只left进化分支。所以前四个调用是：

这使得一棵完全不平衡的树看起来像

任何人都可以提出一种我可以进一步使用递归训练方法并仍然获得平衡树的方法吗？

目标是从根节点中删除 22 并重新平衡树。

首先，我删除了 22，并用它的有序继任者 28 替换它。

其次，我通过将空节点向左移动来重新平衡生成的树。结果树如下。

将 28 向上移动正确的程序，我最后是否正确平衡了左侧？

谢谢！