请帮助我了解AVL树中的LR旋转

Mistu4u

今天,我正在研究“数据结构”中的AVL树,但被困在理解LR和RL旋转方面。LL和RR旋转非常直观,因此很容易记住,但是在我看来,LR和RL旋转不遵循常识,因此我很难记住它们。这些旋转应该被塞住还是有什么办法可以理解它们?我正在阅读的书(Seymoure Lipschutz的《数据结构》)说LR旋转是RR旋转后跟LL旋转的组合。但是我无法连接它。这是那本书中描绘的图片:

在此处输入图片说明

在第二张图像和最后一张图像之间,发生了什么,请尽可能说明一下这张图片。我认为,如果我理解LR,那么自动会理解RL,因为两者都是彼此的镜像。

贾斯汀

您不了解它,因为它不正确,如图所示。它甚至不是有效的二进制搜索树。37不能是76的正确(较大)子代,因为它较小。

初始插入

└── 44
    ├── (L) 30
    │   ├── (L) 16
    │   └── (R) 39
    │       └── (L) 37
    └── (R) 76

在(30)处左旋转后:(39)旋转到其父母的[30]点,(39)的孩子[37]成为30的孩子。

└── 44
    ├── (L) 39
    │   └── (L) 30
    │       ├── (L) 16
    │       └── (R) 37
    └── (R) 76

在(39)上右旋转后:(39)在树的顶部,(44)成为他的右子。

└── 39
    ├── (L) 30
    │   ├── (L) 16
    │   └── (R) 37
    └── (R) 44
        └── (R) 76

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章