重写插入方法

将元素插入 AVL 树与将其插入 BST 相同，只是树可能需要重新平衡。新元素始终作为叶节点插入。添加新节点后，新叶节点祖先的高度可能会增加。插入新节点后，检查从新叶节点到根节点的路径上的节点。如果发现不平衡节点，请使用下面代码中的算法执行适当的旋转。

1 平衡路径(E e) {
2 获取包含元素e的节点到根的路径，
3如图26.9所示；
4 对于通向根的路径中的每个节点 A {
5 更新A的高度；
6 令parentOfA 表示A 的父级，
7 是路径中的下一个节点，如果 A 是根，则为 null；
8
9 开关 (balanceFactor(A)) {
10 情况-2：如果balanceFactor(A.left) == -1或0
11 执行LL旋转； //见图26.2
其他 12 个
13 进行左右旋转； //见图26.4
14 休息；
15 情况+2：如果balanceFactor(A.right) == +1或0
16 执行RR轮换； //见图26.3
其他 17 个
18 进行RL旋转； //见图26.5
19 } // 切换结束
20 } // for
结束 21 } // 方法结束

该算法考虑从新叶节点到根的路径中的每个节点。更新路径上节点的高度。如果节点是平衡的，则无需执行任何操作。如果节点不平衡，则执行适当的旋转

以上是重写插入方法的详细内容。更多信息请关注PHP中文网其他相关文章！