tree - AVL 树 - 如何正确插入？

Question

我正在做一些关于 AVL 树的研究，我知道插入顺序在 AVL 树中很重要。但是我没有找到可以让我明白什么是了解 AVL 树中正确插入顺序的最佳方法。例如：

我必须插入 1 2 3 4 5，我怎么知道哪个是最好的插入方式，为什么？

PS：它不是家庭作业，我对 AVL 树有疑问提前感谢

Answer 1

我不会直接回答你的问题，但我真的建议你访问这个网站。真的帮助我理解了 AVL 树，以及常用功能（如插入、删除、搜索）如何工作。尝试从左侧切换选项！

我希望这有帮助 ：）

Answer 2

插入新元素时，您可能会违反 AVL 树属性。因此，当您插入一个新元素时，您可能需要平衡树。您可以通过左旋或右旋来完成。

如果树是右重的，并且如果树的右子树是左重的，则执行左右旋转，否则将执行一次左旋转。

如果树左重而左子树右重，则执行左右旋转。否则，一个单一的右旋转就可以了。

（左旋转）：假设节点 v 和节点 v 的右孩子 x 在从 z 到根的路径上。W 表示 x 在路径上的右孩子 —> 左旋转。新的余额值：b(x) = 0 和 b(v) = 0。每个孩子向左移动一个。

（右旋转）：假设节点 v 和节点 v 的左孩子 x 在从 z 到根的路径上。W 表示路径上 x 的左孩子 —> 右旋转。新余额值：b(x) = 0 和 b(v) = 0。