平衡树
如何平衡这个树结构
13
/ \
8 18
/ \
14 19
\
15
How to balance this tree structure
13
/ \
8 18
/ \
14 19
\
15
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您没有指定您想要哪种平衡树。例如，您可以使用 AVL 树，
如果您计算节点高点，那么您将得到节点 13 与值 -2 不平衡，18 与 1 不平衡，因此您必须在节点 18 中进行右旋转，在节点 13 中进行左旋转。之后该节点变为均衡。
右旋转后：
左旋转后：
You didn't specified what kind of balanced tree you want. For example you can use AVL tree
If you count node highs then you will get that node 13 is disbalanced with worth -2 and 18 with 1 so you have to do right rotation in node 18 and left rotation in node 13. After that node become balanced.
After right rotation:
After left rotation:
您的值是
8 13 14 15 18 19，因此具有这些值的平衡树可能是：为了获得这棵树，我计算了值以获得树的一般形状（从左到右填充层） -right，自上而下）然后对值进行排序并将它们从左到右放置在树中。
如果平衡树一次，这具有良好的性能，但不应该用于在每次插入/删除后平衡树。
Your values are
8 13 14 15 18 19, so a balanced tree with these values could be:To get this tree, I counted the values to get the general shape of the tree (filling layers left-to-right, top-down) then sorted the values and placed them left-to-right in the tree.
This has good performance if balancing a tree once, but should not be used to balance the tree after every insert/delete.
我也是一名学生，正在研究avl树，在这个问题中，节点13的平衡是-2，这是违反avl条件的，现在这种违反发生是因为插入了新节点15。现在是违反avl条件的节点条件让我们称之为 alpha ，现在我们需要识别插入的情况
插入的情况有：
1）插入到alpha右子树的右子树（alpha是平衡因子违反avl条件的节点）。在这种情况下，我们需要单次左旋转。
2）插入到alpha右子树的左子树中。在这种情况下，我们需要进行双旋转，即右左旋转。
3) 插入到 alpha 左子树的右子树中。在这种情况下，我们需要进行双重旋转，即左右旋转。
4）插入到 alpha 左孩子的左子树中。在这种情况下，我们需要进行一次右旋转来重新平衡树。
现在，在您的问题中，这是情况 2 ，我们需要进行左右旋转来重新平衡树。
我们将在 alpha 的右子树和其左子树的父树之间进行右旋转。
然后，在此之后，我们需要在 alpha 和 alpha 的新右子树（这是 alpha 右子树的左子树的父树）之间进行左旋转，在左旋转之后，我们有一棵树，其根是 14 的左子树 14 13 的左孩子是 8。14 的右孩子是 18 18 的左孩子是 15 18 的右孩子是 19。
我不知道如何发布这棵树的图，Gaim 也回答了这个问题。所以请参阅他发布的数字。
我希望这会有所帮助。
i am also a student and studying the avl tree, in this question the balance of node 13 is -2 which is the violation of avl condition , now this violation occurs because of insertion of new node 15. now the node which is violating the avl condition lets call it alpha , now we need to identify the case of insertion
the cases of insertion are:
1) insertion in the right subtree of right child of alpha(alpha is the node whose balance factor is violating the avl condition). in this case we need single left rotation.
2)insertion in the left subtree of right child of alpha. in this case we need to do double rotation that is right left rotation.
3) insertion in the right subtree of the left child of alpha. in this case we need to do double rotation that is left right rotation.
4)insertion in left subtree of left child of alpha . in this case we need to do single right rotation to rebalance the tree.
now in your question this is case 2 , we need to do right left rotation to rebalance the tree.
we will do the right rotation between the right child of alpha and parent of its left subtree.
then after this we need to do a left rotation between the alpha and the new right child of alpha(which was the parent of left subtree of right child of alpha) after this left rotation we have a tree whoes root is 14 left child of 14 is 13 left child of 13 is 8. Right child of 14 is 18 left child of 18 is 15 right child of 18 is 19.
i don't know how to post figer of this tree, the person Gaim answered this question too. so see the figer that he posted.
I hope this will help.
实际上，AVL 树在插入时是平衡的，检查节点是否需要平衡，并使用尾递归来平衡从插入返回的所有内容。维基百科的 AVL 文章实际上也有一些不错的插图：
http://en.wikipedia.org/wiki/ AVL_tree#插入
In practice AVL trees are balanced upon insert, check if the node needs balancing, and using tail-recursion to balance everything on the way back up from the insert. Wikipedia's AVL article actually has some decent illustrations too:
http://en.wikipedia.org/wiki/AVL_tree#Insertion