public class AVLTree<T extends Comparable<? super T>> { /** * 根节点 */ private AvlNode<T> root; /** * 插入 * * @timestamp Mar 5, 2016 6:31:53 PM * @param x */ public void insert(T x) { root = insert(x, root); } /** * 删除 * * @timestamp Mar 5, 2016 3:44:42 PM * @param x */ public void remove(T x) { root = remove(x, root); } /** * 打印 * * @timestamp Mar 5, 2016 7:00:22 PM */ public void printTree() { if (isEmpty()) System.out.println("Empty tree"); else printTree(root); } /** * 是否为空 * * @timestamp Mar 5, 2016 4:21:26 PM * @return */ public boolean isEmpty() { return root == null; } /** * 中序遍历 * * @timestamp Mar 5, 2016 4:22:19 PM * @param t */ private void printTree(AvlNode<T> t) { if (t != null) { printTree(t.left); System.out.print(t.element + " ,"); printTree(t.right); } } /** * 删除 * * @timestamp Mar 5, 2016 3:44:53 PM * @param x * @param t * @return */ private AvlNode<T> remove(T x, AvlNode<T> t) { if (t == null) return t; int compareResult = x.compareTo(t.element); if (compareResult < 0) t.left = remove(x, t.left); else if (compareResult > 0) t.right = remove(x, t.right); else if (t.left != null && t.right != null) { t.element = findMin(t.right).element; t.right = remove(t.element, t.right); } else t = (t.left != null) ? t.left : t.right; return t; } private AvlNode<T> findMin(AvlNode<T> t) { if (t == null) return null; else if (t.left == null) return t; return findMin(t.left); } /** * 实际插入 * * @timestamp Mar 5, 2016 6:35:02 PM * @param x * @param t * @return */ private AvlNode<T> insert(T x, AvlNode<T> t) { if (t == null) return new AvlNode<T>(x, null, null); int compareResult = x.compareTo(t.element); if (compareResult < 0) {// 左边 t.left = insert(x, t.left); if (height(t.left) - height(t.right) == 2) {// 如果两遍深度相差大于1 if (x.compareTo(t.left.element) < 0) t = rotateWithLeftChild(t);// 左旋 else t = doubleWithLeftChild(t);// 双旋 } } else if (compareResult > 0) {// 右边 t.right = insert(x, t.right); if (height(t.right) - height(t.left) == 2) {// 如果两遍深度相差大于1 if (x.compareTo(t.right.element) > 0) t = rotateWithRightChild(t);// 右旋 else t = doubleWithRightChild(t);// 双旋 } } else ; // 数据重复 t.height = Math.max(height(t.left), height(t.right)) + 1;// 重定义高度 return t; } /** * 旋转右孩子 * * @timestamp Mar 5, 2016 7:19:09 PM * @param k1 * @return */ private AvlNode<T> rotateWithRightChild(AvlNode<T> k1) { AvlNode<T> k2 = k1.right;// k1代表父节点,k2代表父节点的右孩子 k1.right = k2.left;// 孩子节点的左孩子 --> 父节点的右孩子 k2.left = k1;// 父节点 --> 孩子的左节点 k1.height = Math.max(height(k1.left), height(k1.right)) + 1; k2.height = Math.max(height(k2.right), k1.height) + 1;// 重定义高度 return k2; } /** * 旋转左孩子 * * @timestamp Mar 5, 2016 7:18:55 PM * @param k2 * @return */ private AvlNode<T> rotateWithLeftChild(AvlNode<T> k2) { AvlNode<T> k1 = k2.left;// k2代表父节点,k1代表父节点的左孩子 k2.left = k1.right;// 孩子节点的右孩子 --> 父节点的左孩子 k1.right = k2;// 父节点 --> 孩子的右节点 k2.height = Math.max(height(k2.left), height(k2.right)) + 1; k1.height = Math.max(height(k1.left), k2.height) + 1;// 重定义高度 return k1; } /** * 双向旋转左孩子 * * @timestamp Mar 5, 2016 7:19:42 PM * @param k3 * @return */ private AvlNode<T> doubleWithLeftChild(AvlNode<T> k3) { k3.left = rotateWithRightChild(k3.left);// 传入父节点的左孩子节点 return rotateWithLeftChild(k3); } /** * 双向旋转右孩子 * * @timestamp Mar 5, 2016 7:32:56 PM * @param k1 * @return */ private AvlNode<T> doubleWithRightChild(AvlNode<T> k1) { k1.right = rotateWithLeftChild(k1.right);// 传入父节点的右孩子节点 return rotateWithRightChild(k1); } /** * 获取深度,没有返回-1 * * @timestamp Mar 5, 2016 6:41:18 PM * @param t * @return */ private int height(AvlNode<T> t) { return t == null ? -1 : t.height; } /** * 节点 * * @timestamp Mar 5, 2016 6:36:41 PM * @author smallbug * @param <E> */ private static class AvlNode<E> { AvlNode(E theElement, AvlNode<E> lt, AvlNode<E> rt) { element = theElement; left = lt; right = rt; height = 0; } E element; // 数据 AvlNode<E> left; // 左孩子 AvlNode<E> right; // 右孩子 int height; // 深度 } public static void main(String[] args) { AVLTree<Integer> t = new AVLTree<>(); t.insert(3); t.insert(2); t.insert(1); t.insert(4); t.insert(5); t.insert(6); t.insert(7); t.insert(10); t.insert(9); t.insert(8); t.printTree(); System.out.println(); t.remove(8); t.printTree(); } }
相关推荐
数据结构与算法的一些实例,数据结构包括图(遍历算法)、树(哈夫曼树、AVL平衡树等),算法包括查找算法(二分查找、斐波那契查找等)、排序算法(快速排序、堆排序等)、贪心算法、KMP算法等.zip
java数据结构与算法之平衡二叉树AVL树的设计与实现分析.doc
AVL树Java中的AVL树实现有两个基本操作,使用这些操作树本身会保持平衡。 左旋转。 右旋。 然后将有四种可能性左-左情况:— x是y的左子代,y是z的左子代。 左右案例:— x是y的右子代,y是z的左子代。 左右案例:—...
java数据结构与算法之平衡二叉树(AVL树)的设计与实现分析.docx
java数据结构与算法之平衡二叉树(AVL树)的设计与实现分析.pdf
之前只写了一些AVL树核心算法,这里给出一个AVL树的完整实现。 AVL树是平衡查找二叉树,不仅能避免二叉搜索树出现斜树的状况,更是能保持比较标准的O(log2N),但AVL树可能需要很多次的各种调整: 左儿子单旋转 左...
平衡二叉树插入节点和删除节点
Java代码实现,从文件中读取数据,根据AVL树的构建规则,构建一棵AVL树(平衡二叉树),并输出平均查找长度ASL。
平衡二叉树建立过程分析,从第一个元素的插入,截止至最后一个元素,均以详细的画图展示
不同之处在于,您可能必须在插入或删除操作之后重新平衡树。节点的平衡因子是其右子树的高度减去左子树的高度。如果一个节点的平衡因子为- 1,0或1,则称该节点为平衡节点。如果一个节点的平衡因子为-1,则该节点称为...
java实现别踩白块儿源码唐ju don.juan.matus信息库 包don.juan.matus.lib.collection.sorted.tree.bintree 二叉搜索树类: BST(BinTreeBase) 权重平衡树(BinTreeW) AVL(AVLBinTree) 红黑树(RedBlackTree) AA...
使用Java实现二叉平衡树,对二叉树进行添加结点同时构建二叉树的平衡。详细原理见本人博客文章《数据结构:二叉平衡树(AVL树)Java实现》。
间隔树 用于存储重叠范围的 AVL 平衡间隔树。 为方便起见,实现了 Java SortedSet。 有关区间树的说明,请参阅 Wikiepdia: :
插入和删除可能需要通过一次或多次树旋转来重新平衡树。 AVL 树以其两位苏联发明者 Georgy Adelson-Velsky 和 EM Landis 的名字命名,他们在 1962 年的论文“信息组织的算法”中发表了它。 AVL 树经常与红黑...
//通过旋转,使节点z的平衡因子的绝对值不超过1(支持AVL树) //返回新的子树根 public static BinTreePosition rotate(BinTreePosition z) { BinTreePosition y = tallerChild(z);//取y为z更高的孩子 ...
该代码包括了二叉树、二叉查找树、平衡树的Java实现代码
本项目是一个示例项目,展示了如何在 BlueJ 等简单的编程环境中使用 Java 实现一个 AVL 二叉搜索树。 ###用作图书馆 可以通过实现IData接口来添加数据 BinaryTree是一种基本的二叉搜索树,它以排序的方式插入元素 ...
AVL树(AVLTree)、红黑树(RebBlackTree) B树(B-Tree) 集合(TreeSet)、映射(TreeMap) 哈夫曼树 Trie 线性+树形数据结构 集合(HashSet) 映射(HashMap、LinkedHashMap) 二叉堆(BinaryHeap) 优先级队列...
5. 腾讯面试题:有了二叉查找树、平衡树为啥还需要红黑树? 6. 你真的了解 i++, ++i 和 i+++++i 以及 i+++i++ 吗? 7. 面试准备-《算法第4版》Java算法笔记、理解整理 8. Java基础知识面试题(总结最全面的面试题...
红黑树Java代码的实现,可以直接使用。 红黑树(Red Black Tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 红黑树是一种特化的AVL树(平衡二叉树),都是在进行...