带有二叉树旋转解释的代码（左或右）

发布于 2024-10-10 11:45:25 字数 304 浏览 2 评论 0原文

我一直在努力思考如何编写二叉树旋转的代码。我查看了 http://en.wikipedia.org/wiki/Tree_rotation 和 enfuzzled.com 我已经盯着这个看了两个小时了，之前已经看了好几遍了。我仍然在维基百科文章中看到问题，并且无法完全理解另一篇文章，例如

维基百科文章中提到的这两行不能同时为真

让 P 成为 Q 的左孩子。设 P 为新根。

有人可以帮忙吗？谢谢

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

美煞众生 2024-10-17 11:45:25

根据您对问题的评论，您正在寻找旋转算法的指导。这是一本优秀书籍中的 LEFT-ROTATE 算法 http://www.amazon.com/Introduction -算法-第三-Thomas-Cormen/dp/0262033844。

替代文本

回复收藏 0 原文

我也只是我 2024-10-17 11:45:25

“设 P 为 Q 的左子节点。将 P 设为新根。”基本上这是向右或顺时针旋转的描述：

  Q      P
 /   =>   \
P          Q

"Let P be Q's left child. Set P to be the new root." Basically that's the description of the rotation to the right or clockwise:

  Q      P
 /   =>   \
P          Q

回复收藏 0 原文

深府石板幽径 2024-10-17 11:45:25

这是我的 Corman 书版本中的 LEFT-ROTATE

回复收藏 0 原文

怪异←思 2024-10-17 11:45:25

这个答案来自 https://www.codesdope.com /课程/数据结构-红黑树-插入/
一切都归功于那些家伙。

左旋转（T，x）
y = x.右
x.right = y.left

y 的左子节点将成为 x - x.right = y.left 的右子节点。我们还需要将 y.left 的父级更改为 x。如果 y 的左子节点不为 NULL，我们将执行此操作。

如果 y.left != NULL
y.left.parent = x

然后我们需要将 y 放到 x 的位置。我们首先将 y 的父级更改为 x - y.parent = x.parent 的父级。之后，我们将使节点 x 成为 y 父节点的子节点，而不是 y。我们将通过检查 y 是其父级的右子级还是左子级来实现此目的。我们还将检查 y 是否是树的根。

y.parent = x.parent
if x.parent == NULL //x is root
  T.root = y
elseif x == x.parent.left // x is left child
  x.parent.left = y
else // x is right child
  x.parent.right = y

最后，我们需要使 x 成为 y 的左孩子。

y.left = x
x.parent = y

LEFT_ROTATE(T, x)
  y = x.right
  x.right = y.left
  if y.left != NULL
      y.left.parent = x
  y.parent = x.parent
  if x.parent == NULL //x is root
      T.root = y
  elseif x == x.parent.left // x is left child
      x.parent.left = y
  else // x is right child
      x.parent.right = y
  y.left = x
  x.parent = y

This answer is from https://www.codesdope.com/course/data-structures-red-black-trees-insertion/
All credit to those guys.

LEFT_ROTATION(T, x)
y = x.right
x.right = y.left

The left child of y is going to be the right child of x - x.right = y.left. We also need to change the parent of y.left to x. We will do this if the left child of y is not NULL.

if y.left != NULL
y.left.parent = x

Then we need to put y to the position of x. We will first change the parent of y to the parent of x - y.parent = x.parent. After this, we will make the node x the child of y's parent instead of y. We will do so by checking if y is the right or left child of its parent. We will also check if y is the root of the tree.

y.parent = x.parent
if x.parent == NULL //x is root
  T.root = y
elseif x == x.parent.left // x is left child
  x.parent.left = y
else // x is right child
  x.parent.right = y

At last, we need to make x the left child of y.

y.left = x
x.parent = y

LEFT_ROTATE(T, x)
  y = x.right
  x.right = y.left
  if y.left != NULL
      y.left.parent = x
  y.parent = x.parent
  if x.parent == NULL //x is root
      T.root = y
  elseif x == x.parent.left // x is left child
      x.parent.left = y
  else // x is right child
      x.parent.right = y
  y.left = x
  x.parent = y

回复收藏 0 原文

~没有更多了~