今天,我正在研究“数据结构”中的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] 删除。
我来说两句