Node.js
AVL树的Java实现
发布时间：2019-06-03 发布网站：脚本宝典
脚本宝典收集整理的这篇文章主要介绍了AVL树的Java实现，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
定义
在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的@R_809_1304@都是 {displaystyle O(LOG {n})} O(log{n})。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorIThm for the organization of information》中公开了这一数据结构。
理论
实现AVL树的要点为：每次新增/删除节点后判断平衡性然后通过调整使整棵树重新平衡
判断平衡性：每次新增/删除节点后，刷新受到影响的节点的高度，即可通过任一节点的左右子树高度差判断其平衡性
调整：通过对部分节点的父子关系的改变使树重新平衡
实现
基本结构
public class Tree<T extends Comparable<T>> {
private static final int MAX_HEIGHT_DIFFERENCE = 1;
private Node<T> root;
class Node<KT> {
KT key;
Node<KT> left;
Node<KT> right;
int height = 1;
public Node(KT key, Node<KT> left, Node<KT> right) {
this.key = key;
this.left = left;
this.right = right;
}
}
}插入（insert）
四种不平衡范型
对于任意一次插入所造成的不平衡，都可以简化为下述四种范型之一：
下面四张图中的数字仅代表节点序号，为了后文方便展示调整过程
4、5、6、7号节点代表了四棵高度可以使不平衡成立的子树（遵循插入的规则）
- LL型
- LR型
- RR型
- RL型
总结得到判断范型的方法为：不平衡的节点（节点1）通往高度最大的子树的叶子节点时所途经的前两个节点（节点2、节点3）的方向
调整方法
- LL型
-
5号节点作为1号节点的左孩子
-
1号节点作为2号节点的右孩子
例子（例子中的数字代表节点的值）：
插入节点5后造成节点9不平衡，其范型为LL型，按照固定步骤调整后全局重新达到平衡
- LR型
-
6号节点作为2号节点的右孩子
-
7号节点作为1号节点的左孩子
-
2号节点作为3号节点的左孩子
-
1号节点作为3号节点的右孩子
例子（例子中的数字代表节点的值）：
插入节点8.5后造成节点9不平衡，其范型为LR型，按照固定步骤调整后全局重新达到平衡
- RR型
-
5号节点作为1号节点的右孩子
-
1号节点作为2号节点的左孩子
例子（例子中的数字代表节点的值）：
插入节点10.5后造成节点7不平衡，其范型为RR型，按照固定步骤调整后全局重新达到平衡
- RL型
-
7号节点作为2号节点的左孩子
-
6号节点作为1号节点的右孩子
-
2号节点作为3号节点的右孩子
-
1号节点作为3号节点的左孩子
例子（例子中的数字代表节点的值）：
插入节点7.5后造成节点7不平衡，其范型为RL型，按照固定步骤调整后全局重新达到平衡
代码实现
public void insert(T key) {
if (key == null) {
throw new NullPointerException();
}
root = insert(root, key);
}
private Node<T> insert(Node<T> node, T key) {
if (node == null) {
return new Node<>(key, null, null);
}
int cmp = key.compareTo(node.key);
if (cmp == 0) {
return node;
}
if (cmp < 0) {
node.left = insert(node.left, key);
} else {
node.right = insert(node.right, key);
}
if (Math.abs(height(node.left) - height(node.right)) > MAX_HEIGHT_DIFFERENCE) {
node = balance(node);
}
refreshHeight(node);
return node;
}
private int height(Node<T> node) {
if (node == null) {
return 0;
}
return node.height;
}
private void refreshHeight(Node<T> node) {
node.height = Math.max(height(node.left), height(node.right)) + 1;
}
/**
* 此方法中的node, node1, node2分别代表上文范型中的1、2、3号节点
*/
private Node<T> balance(Node<T> node) {
Node<T> node1, node2;
// ll
if (height(node.left) > height(node.right) &&
height(node.left.left) > height(node.left.right)) {
node1 = node.left;
node.left = node1.right;
node1.right = node;
refreshHeight(node);
return node1;
}
// lr
if (height(node.left) > height(node.right) &&
height(node.left.right) > height(node.left.left)) {
node1 = node.left;
node2 = node.left.right;
node.left = node2.right;
node1.right = node2.left;
node2.left = node1;
node2.right = node;
refreshHeight(node);
refreshHeight(node1);
return node2;
}
// rr
if (height(node.right) > height(node.left) &&
height(node.right.right) > height(node.right.left)) {
node1 = node.right;
node.right = node1.left;
node1.left = node;
refreshHeight(node);
return node1;
}
// rl
if (height(node.right) > height(node.left) &&
height(node.right.left) > height(node.right.right)) {
node1 = node.right;
node2 = node.right.left;
node.right = node2.left;
node1.left = node2.right;
node2.left = node;
node2.right = node1;
refreshHeight(node);
refreshHeight(node1);
return node2;
}
return node;
}总结
由插入节点导致的局部不平衡均会符合上述四种范型之一，只需要按照固定的方式调整相关节点的父子关系即可使树恢复平衡
关于调整，很多博客或者书籍中将这种调整父子关系的过程称为旋转，这个就见仁见智了，个人觉得这种描述并不容易理解，故本文统一称为调整
删除（remove）
通常情况
对于删除节点这个操作来说，有两个要点：被删除节点的空缺应该如何填补以及删除后如何使树恢复平衡
- 被删除节点的空缺应该如何填补
- 如果被删除节点是叶子节点，则不需要填补空缺
- 而如果是枝干节点，则需要填补空缺，理想的情况是使用某个节点填补被删除节点的空缺后，整棵树仍然保持平衡
a) 如果节点的左右子树有一棵为空，则使用非空子树填补空缺
b) 如果节点的左右子树均为非空子树，则使用节点的左右子树中更高的那棵子树中的最大/最小节点来填补空缺（如果子树高度一致则哪边都可以）
例子：
- 假设待删除节点为
节点9，则应当使用左子树中的最大值节点8来填补空缺
- 假设待删除节点为
节点13，则应当使用右子树中的最小值节点14来填补空缺
- 假设待删除节点为
节点2，则使用左子树中的最大值节点1.5或者右子树中的最小值节点2.5来填补空缺均可
按照上述方式来填补空缺，可以尽可能保证删除后整棵树仍然保持平衡
- 删除后如何使树恢复平衡
如图，叶子节点12为被删除节点，删除后不需要填补空缺，但是此时节点13产生了不平衡
不过节点13的不平衡满足上文所说的不平衡范型中的RR型，因此只需要对节点13做对应的调整即可，如图：
此时节点13所在的子树经过调整重新达到局部平衡
但是我们紧接着发现，节点11出现了不平衡，其左子树高度为4，右子树高度为2
如果此时按照插入情况下的不平衡范型判断方法去判断节点11的不平衡情况属于哪种范型，会发现无法满足四种范型的任一情况
特殊情况
由删除节点导致的不平衡，除了会出现插入中所说的四种范型之外，还会出现两种情况，如图：
整棵树初始状态为平衡状态，此时假设删除节点13或节点14，均会导致节点11产生不平衡（左子树高度3，右子树高度1）
但是如果仍然按照插入时的方法来判断不平衡，则会发现，节点4的左右子树高度一致，即在满足了L后，后续无法判断这种情况属于哪种范型
对于R方向也是一样
本文称它们为L型和R型
不过这两种情况的处理也很简单，实际上当出现这种情况时，使用LL型或LR型的调整方法均可以达到使树重新平衡的目的
如图：
两种调整方式均可使树重新平衡，对于R型也是一样，这里不再赘述
代码实现
public void remove(T key) {
if (key == null) {
throw new NullPointerException();
}
root = remove(root, key);
}
private Node<T> remove(Node<T> node, T key) {
if (node == null) {
return null;
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node.left = remove(node.left, key);
}
if (cmp > 0){
node.right = remove(node.right, key);
}
if (cmp == 0) {
if (node.left == null || node.right == null) {
return node.left == null ? node.right : node.left;
}
var successorKey = successorOf(node).key;
node = remove(node, successorKey);
node.key = successorKey;
}
if (Math.abs(height(node.left) - height(node.right)) > MAX_HEIGHT_DIFFERENCE) {
node = balance(node);
}
refreshHeight(node);
return node;
}
/**
* 寻找被删除节点的继承者
*/
private Node<T> successorOf(Node<T> node) {
if (node == null) {
throw new NullPointerException();
}
if (node.left == null || node.right == null) {
return node.left == null ? node.right : node.left;
}
return height(node.left) > height(node.right) ?
findMax(node.left, node.left.right, node.left.right == null) :
findMin(node.right, node.right.left, node.right.left == null);
}
private Node<T> findMax(Node<T> node, Node<T> right, boolean rightIsNull) {
if (rightIsNull) {
return node;
}
return findMax((node = right), node.right, node.right == null);
}
private Node<T> findMin(Node<T> node, Node<T> left, boolean leftIsNull) {
if (leftIsNull) {
return node;
}
return findMin((node = left), node.left, node.left == null);
}其中用到的private Node<T> balance(Node<T> node)方法修改为：
private Node<T> balance(Node<T> node) {
Node<T> node1, node2;
// ll & l
if (height(node.left) > height(node.right) &&
height(node.left.left) >= height(node.left.right)) {
node1 = node.left;
node.left = node1.right;
node1.right = node;
refreshHeight(node);
return node1;
}
// lr
if (height(node.left) > height(node.right) &&
height(node.left.right) > height(node.left.left)) {
node1 = node.left;
node2 = node.left.right;
node.left = node2.right;
node1.right = node2.left;
node2.left = node1;
node2.right = node;
refreshHeight(node);
refreshHeight(node1);
return node2;
}
// rr & r
if (height(node.right) > height(node.left) &&
height(node.right.right) >= height(node.right.left)) {
node1 = node.right;
node.right = node1.left;
node1.left = node;
refreshHeight(node);
return node1;
}
// rl
if (height(node.right) > height(node.left) &&
height(node.right.left) > height(node.right.right)) {
node1 = node.right;
node2 = node.right.left;
node.right = node2.left;
node1.left = node2.right;
node2.left = node;
node2.right = node1;
refreshHeight(node);
refreshHeight(node1);
return node2;
}
return node;
}也就是将L型情况包含进了LL型，R型的情况包含进了RR型，因为这两种范式的调整要比对应的LR型/RL型的操作数少
总结
尽管删除节点时会出现特殊的情况，但是仍然可以通过简单的调整使树始终保持平衡
完整代码
/**
* AVL-Tree
*
* @author Shinobu
* @since 2019/5/7
*/
public class Tree<T extends Comparable<T>> {
private static final int MAX_HEIGHT_DIFFERENCE = 1;
private Node<T> root;
class Node<KT> {
KT key;
Node<KT> left;
Node<KT> right;
int height = 1;
public Node(KT key, Node<KT> left, Node<KT> right) {
this.key = key;
this.left = left;
this.right = right;
}
}
public Tree(T... keys) {
if (keys == null || keys.length < 1) {
throw new NullPointerException();
}
root = new Node<>(keys[0], null, null);
for (int i = 1; i < keys.length && keys[i] != null; i++) {
root = insert(root, keys[i]);
}
}
public T find(T key) {
if (key == null || root == null) {
return null;
}
return find(root, key, key.compareTo(root.key));
}
private T find(Node<T> node, T key, int cmp) {
if (node == null) {
return null;
}
if (cmp == 0) {
return node.key;
}
return find(
(node = cmp > 0 ? node.right : node.left),
key,
node == null ? 0 : key.compareTo(node.key));
}
public void insert(T key) {
if (key == null) {
throw new NullPointerException();
}
root = insert(root, key);
}
private Node<T> insert(Node<T> node, T key) {
if (node == null) {
return new Node<>(key, null, null);
}
int cmp = key.compareTo(node.key);
if (cmp == 0) {
return node;
}
if (cmp < 0) {
node.left = insert(node.left, key);
} else {
node.right = insert(node.right, key);
}
if (Math.abs(height(node.left) - height(node.right)) > MAX_HEIGHT_DIFFERENCE) {
node = balance(node);
}
refreshHeight(node);
return node;
}
private int height(Node<T> node) {
if (node == null) {
return 0;
}
return node.height;
}
private void refreshHeight(Node<T> node) {
node.height = Math.max(height(node.left), height(node.right)) + 1;
}
private Node<T> balance(Node<T> node) {
Node<T> node1, node2;
// ll & l
if (height(node.left) > height(node.right) &&
height(node.left.left) >= height(node.left.right)) {
node1 = node.left;
node.left = node1.right;
node1.right = node;
refreshHeight(node);
return node1;
}
// lr
if (height(node.left) > height(node.right) &&
height(node.left.right) > height(node.left.left)) {
node1 = node.left;
node2 = node.left.right;
node.left = node2.right;
node1.right = node2.left;
node2.left = node1;
node2.right = node;
refreshHeight(node);
refreshHeight(node1);
return node2;
}
// rr & r
if (height(node.right) > height(node.left) &&
height(node.right.right) >= height(node.right.left)) {
node1 = node.right;
node.right = node1.left;
node1.left = node;
refreshHeight(node);
return node1;
}
// rl
if (height(node.right) > height(node.left) &&
height(node.right.left) > height(node.right.right)) {
node1 = node.right;
node2 = node.right.left;
node.right = node2.left;
node1.left = node2.right;
node2.left = node;
node2.right = node1;
refreshHeight(node);
refreshHeight(node1);
return node2;
}
return node;
}
public void remove(T key) {
if (key == null) {
throw new NullPointerException();
}
root = remove(root, key);
}
private Node<T> remove(Node<T> node, T key) {
if (node == null) {
return null;
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node.left = remove(node.left, key);
}
if (cmp > 0){
node.right = remove(node.right, key);
}
if (cmp == 0) {
if (node.left == null || node.right == null) {
return node.left == null ? node.right : node.left;
}
var successorKey = successorOf(node).key;
node = remove(node, successorKey);
node.key = successorKey;
}
if (Math.abs(height(node.left) - height(node.right)) > MAX_HEIGHT_DIFFERENCE) {
node = balance(node);
}
refreshHeight(node);
return node;
}
private Node<T> successorOf(Node<T> node) {
if (node == null) {
throw new NullPointerException();
}
if (node.left == null || node.right == null) {
return node.left == null ? node.right : node.left;
}
return height(node.left) > height(node.right) ?
findMax(node.left, node.left.right, node.left.right == null) :
findMin(node.right, node.right.left, node.right.left == null);
}
private Node<T> findMax(Node<T> node, Node<T> right, boolean rightIsNull) {
if (rightIsNull) {
return node;
}
return findMax((node = right), node.right, node.right == null);
}
private Node<T> findMin(Node<T> node, Node<T> left, boolean leftIsNull) {
if (leftIsNull) {
return node;
}
return findMin((node = left), node.left, node.left == null);
}
}结语
AVL树的实现，在了解了不平衡的六种情况，以及对应的处理方式后，还是比较简单且逻辑清晰的
本文实现的AVL树的增删查三种操作，全部基于递归的算法模式，考虑到在树足够大时递归的效率问题，本人尝试进行了一些尾递归优化，希望这能使操作效率更高一些
后续也许会学习并尝试实现一下红黑树，然后对比一下二者的效率
文章如果有谬误或疏漏，还请务必指正，感谢万分
脚本宝典总结
以上是脚本宝典为你收集整理的AVL树的Java实现全部内容，希望文章能够帮你解决AVL树的Java实现所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
猜你在找的Node.js相关文章
- ubuntu 下部署 node 服务器环境 - 番外（bash | vim | chmod） 2019-06-20
- Node.js安装 2019-06-14
- node.js 安装 2019-07-03
- ubuntu install node npm bower 2019-06-13
- linux下安装node.js 2019-06-06
- Node.js 指南（目录） 2019-06-29
- node 相关笔记 2019-06-03
- Linux环境升级node版本 2019-06-16
- Node的边界 2019-07-16
- Redis的Node.js扩展包 node_redis 示例代码 2018-11-10
全站导航更多
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧JavaScriptASP.NETPHP编程正则表达式AJAX相关ASP编程JSP编程编程10000问CSS/HTMLFlexvbsDOS/BAThtahtcpythonperl游戏相关VBA远程脚本ColdFusionMsSqlMysqlmariadboracleDB2mssql2008mssql2005SQLitePostgreSQLMongoDB星外虚拟主机华众虚拟主机Linuxwin服务器FTP服务器DNS服务器Tomcatnginxzabbix云和虚拟化bios系统安装系统系统进程Windows系列LINUXRedHat/CentosUbuntu/DebianFedoraSolaris红旗Linux建站经验微信营销网站优化网站策划网络赚钱网络创业站长故事alexa域名photoshop教程摄影教程Fireworks教程CorelDraw教程Illustrator教程Painter教程Freehand教程IndesignSketch笔记本主板内存CPU存储显卡显示器光存储鼠标键盘平板电脑安全教程杀毒防毒安全设置病毒查杀脚本攻防入侵防御工具使用业界动态Exploit漏洞分析
最新Node.js教程
热门Node.js教程
- ubuntu 下部署 node 服务器环境 - 番外（bash | vim | chmod）
- CountDownLatch的await和countDown方法简单分析
- AbstractQueuedSynchronizer理解之一（ReentrantLock）
- Threads in Node 10.5.0: a practical intro
- 学习JavaScript数据结构与算法（四）：二叉搜索树
- Node.js 系列：原生 Node.js 应用
- Node项目之需求收集平台（三）- 使用cookie实现点赞功能
- socket.io+express实现聊天室的思考（一）
- 聊聊storm的AssignmentDistributionService
- npx命令介绍