首页 > Java > java教程 > 重写插入方法

重写插入方法

WBOY
发布: 2024-07-25 09:14:13
原创
650 人浏览过

Overriding the insert Method

将元素插入 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中文网其他相关文章!

来源:dev.to
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板