menu Error0 Blog
AVL树的初步了解
95 浏览 | 2019-11-03 | 分类:数据结构 | 标签:

平衡二叉树(AVL树)

空树或者,任意左右子树高度差的绝对值不超过1,|BF(1)|<=1

平衡二叉树调整

因“破坏者”的插入导致某个结点(发现者)不平衡所以需要相对应的旋转,才能达到平衡。

右单旋转


不平衡的“发现者” 是1号,破坏平衡结点的是3号。3号在“发现者”的左子树的左边,因LL插入,需要(右单旋转)

左单旋转

“发现者” 为1号 “破坏者”为3号,3号在“发现者”的右子树的右边。因RR插入,需要(左单旋转)

LR旋转

    “破坏者”在“发现者”的左子树的右边所以需要LR旋转(先左后右旋转)。

RL旋转

  “破坏者”在“发现者”的右子树的左边所以需要RL旋转(先右后左旋转)。

核心代码清单

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!

Emoji

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 46

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 48

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 87

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 89