第一次PO板，可能写的不尽详细or不完整.... 假设两儿子的高度差为 正数 or 0 找出旋转点：先从刚插入的节点往root的方向，依序往上找， 直到找到节点的两个儿子高度差为2 则此节点的爸爸以上，高度差皆 >= 2 此节点的儿子以下，高度差皆 <= 1 再判断此节点与刚刚节点插入的方向（就是LL LR那四种的某一种） 依插入的方向，可以找出三个节点， 依二元树特性，可以找出这三节点的大小关系， 而这三个节点，会连接四个节点，依小到大，我用红黄绿蓝四色代表。 找好之後，开始作旋转。 旋转：将需要作旋转的三个节点，依二元树的特性，列出大中小三个值 而中间的值往上搬成为父点，小的值与大的值变成中间值的两个儿子 接下来比较难的就是旋转前三个节点的四个儿子（红黄绿蓝四个节点） 此四个节点（红 < 黄 < 绿 < 蓝）依图例， 红色接到最小值的左儿子（因为红色是最小的）， 黄色接到最小值的右儿子（次小） 绿色接到最大值的左儿子（次大） 蓝色接到最大值的右儿子（因为最大） 按照这种规则就可以实作出来了， 我会利用从插入的节点往回找高度差的原因是因为， 这样子就不用每插入一次，就要整棵树parse一次， 再者，旋转只会与那三个需要旋转的点有关， 旋转完之後，并不需要再计算整棵树每个节点的高度差， 因为旋转一次，整棵树就会平衡了。（horowitz课本後面好像有证明的样子） │ │ ╭─╮ 　　　　　　 │大│ ← 以此点的"左右儿子高度差"为２ 　　　　　　 ╰─╯ （他儿孙的高度差皆为１或０， 　　　　　　 ／ ＼ 他爸爸、爷爷往上，皆大於等於２） ／ Ｌ ＼ 　 ╭─╮　　　 　 　 ╭─╮ 　│小│ 　　　 　│ │ 　╰─╯ 　 　 　　╰─╯ ／　＼ Ｒ 　 　 ／　＼ ／　　　＼ ／　　　＼ ╭─╮　　　╭─╮ ╭─╮　　　╭─╮ │ │ 　│中│ │ │ 　　│ │ ╰─╯ 　╰─╯ ╰─╯ 　　╰─╯ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ○ ○ ○ ○○ ○ ○ ○ ： ： ： ： ： ： ● ← 假设插入的节点在这边， 由此节点往上开始比较爸爸的左右两儿子高度差 if ( 爸爸的左右儿子高度差 >= 1 ) then 记录此点， 并判断 此点 与 插入节点 的关系， 即 LL or LR or RL or RR， 开始做旋转!! else 继续找爸爸的爸爸， 直到找到第一个高度差为２的节点， 或是找到root都没有高度差为２，则结束! 　　　　　　　　　 父　 父 │ │ │ │ ╭─╮ 经ＬＲ旋转後 　 　 ╭─╮ 　　　　 │大│ ＝＝＝＝＝＝＞　 　│中│ 　　　　 ╰─╯ 　　╰─╯ 　　　 ／ ＼ 　 ／　＼ ／ Ｌ ＼ ／　　　＼ 　 ╭─╮　　　 　 　 ╭─╮ ╭─╮　　　╭─╮ 　│小│ 　　　 　│Ｄ│ │小│ 　　│大│ 　╰─╯ 　 　 　　╰─╯ ╰─╯ 　　╰─╯ ／　＼ Ｒ 　 　 ／　＼ ／ ＼ ／ ＼ ／　　　＼ ／　　　＼ Ａ Ｂ Ｃ Ｄ ╭─╮　　　╭─╮ ╭─╮　　　╭─╮ ： ： ： ： │Ａ│ 　│中│ │ │ 　　│ │ ： ： ： ： ╰─╯ 　╰─╯ ╰─╯ 　　╰─╯ ● ／ ＼ ／ ＼ ／ ＼ ／ ＼ ○ ○ Ｂ Ｃ○ ○ ○ ○ ： ： ： ： ： ： ● 剩下LL RL （RR我就没有画了，因为差不多） 爷 │ 父 │ ╭─╮ 　　　　 │大│ 　　　　 ╰─╯ 　　　　 ／ ＼ ／ Ｌ ＼ 　 ╭─╮　　　 　 　 ╭─╮ 　│中│ 　　　 　│ │ 　╰─╯ 　 　 　　╰─╯ ／　＼ 　 　 　 ／　＼ ／Ｌ　　＼ ／　　　＼ ╭─╮　　　╭─╮ ╭─╮　　　╭─╮ │小│ 　│　│ │ │ 　　│ │ ╰─╯ 　╰─╯ ╰─╯ 　　╰─╯ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ○ ○ ○ ○○ ○ ○ ○ ： ： ： ： ： ： ● ● ↖ ↑ ↖↑ 不管插在哪一边，皆都是LL型 !! 爷 │ 父 │ ╭─╮ 　　　　 │小│ 　　　　 ╰─╯ 　　　　 ／ ＼ ／ 　 Ｒ ＼ 　 ╭─╮　　　 　 　 ╭─╮ 　│　│ 　　　 　│大│ 　╰─╯ 　 　 　　╰─╯ ／　＼ 　 　 Ｌ ／　＼ ／　　　＼ ／　　　＼ ╭─╮　　　╭─╮ ╭─╮　　　╭─╮ │　│ 　│　│ │中│ 　　│ │ ╰─╯ 　╰─╯ ╰─╯ 　　╰─╯ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ○ ○ ○ ○○ ○ ○ ○ ： ： ： ： ： ： ● ● ↖ ↑ ↖↑ 不管插在哪一边，皆都是RL型 !! ※ 引述《drkkimo (Dr.K)》之铭言： : 我想这算是蛮常被提到的一种东西吧 不过老实说 我对它的资料插入和删除後 要作的 : 调整真的搞不太懂 看到二、三本书吧 都分成LL、LR、RR、LR型调整之类的 但还是不很 : 了解 … : 请问有没有人知道那里有比较完整的实作 或是比较清楚的解说呢 因为我最近想把它弄懂　 : 可否指点一下呢 thx:) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.229.230.7 ※ 编辑: iamomygod 来自: 61.229.230.7 (01/31 21:31)