AVL树的完整实现（含比较器，Java语言描述）
201 浏览量
2020-12-22
14:49:09
上传
评论
收藏 55KB PDF 举报
AVL树的完整实现（含比较器，树的完整实现（含比较器，Java语言描述）语言描述）
前情提要前情提要
之前只写了一些AVL树核心算法，这里给出一个AVL树的完整实现。
AVL树是平衡查找二叉树，不仅能避免二叉搜索树出现斜树的状况，更是能保持比较标准的O(log2N)，但AVL树可能需要很多
次的各种调整：
左儿子单旋转
左儿子双旋转
右儿子单旋转
右儿子双旋转
最终使得AVL树维持平衡，保持较高查找效率。
调整在插入删除每一次的不平衡后进行，可能简单也可能复杂，但基本的四种“动作”是固定的。
AVL树作为数据结构，说简单也简单，说复杂也复杂。对初学者来说，一定要掌握的是检测和调整AVL树平衡（含四种旋转）
的代码，随着学习的深入，应该尝试编写AVL树的完整代码。
这里就给大家提供一份可用的完整代码。
功能介绍功能介绍
void insert(x) → Insert x
void remove(x) → Remove x (unimplemented)
boolean contains(x) → Return true if x is present
boolean remove(x) → Return true if x was present
Comparable findMin() → Return smallest item
Comparable findMax() → Return largest item
boolean isEmpty() → Return true if empty; else false
void makeEmpty() → Remove all items
void printTree() → Print tree in sorted order
异常类异常类
当集合容器为空的时候就不能够删除或获取元素，这时就会出现一种异常，命名为UnderflowException：
/**
* Exception class for access in empty containers
* such as stacks, queues, and priority queues.
*/
public class UnderflowException extends RuntimeException {}
编程实现编程实现
/**
* Implements an AVL tree.
* Note that all "matching" is based on the compareTo method.
*/
public class AvlTree<T extends Comparable> {
/**
* The tree root.
*/
private AvlNode root;
/**
* Construct the tree.
*/
public AvlTree() {
root = null;
}
/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert(T x) {
root = insert(x, root);
}
weixin_38666208
- 粉丝: 17
- 资源: 934
评论0