首页 / JAVA / AVL树(Java实现)
AVL树(Java实现)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了AVL树(Java实现),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3372字,纯文字阅读大概需要5分钟。
内容图文
AVL树基本操作
未完....待续....
AVL树代码
public class AVLTree<Key extends Comparable<? super Key>, Value> { private class Node { Key key;//键,相当于词典里的单词 Value value;//值,相当于词典里的单词解释 int height;//结点的高度 Node left; Node right; public Node(Key key, Value value) { this.key = key; this.value = value; this.left = null; this.right = null; int height = 0; } } private Node root; public AVLTree() { root = null; } private int height(Node node) { if (node != null) { return node.height; } return 0; } public int height() { return height(root); } private int max(int a, int b) { return a > b ? a : b; } private void preOrder(Node node) { if (node != null) { System.out.println(node.key); preOrder(node.left); preOrder(node.right); } } public void preOrder() { preOrder(root); } private void inOrder(Node node) { if (node != null) { inOrder(node.left); System.out.println(node.key); inOrder(node.right); } } public void inOrder() { inOrder(root); } public void postOrder(Node node) { if (node != null) { postOrder(node.left); postOrder(node.right); System.out.println(node.key); } } public void postOrder() { postOrder(root); } private Node search(Node node, Key key) { if (node == null) { return null; } else if (key.compareTo(node.key) == 0) { return node; } else if (key.compareTo(node.key) < 0) { return search(node.left, key); } else {//key.compareTo(node.key) > 0 return search(node.right, key); } } public Node search(Key key) { return search(root, key); } private Node minNode(Node node) { if (node == null) { return null; } else if (node.left == null) { return node; } else { return minNode(node.left); } } public Node minNode() { return minNode(root); } private Node maxNode(Node node) { if (node == null) { return null; } else if (node.right == null) { return node; } else { return maxNode(node.right); } } public Node maxNode() { return maxNode(root); } // 对如下的LL情况 // // k1 k2 // / \ / // k2 z LL转 x k1 // / \ ----\ / / // x y ----/ o y z // / // o // // 或 // // k1 k2 // / \ / // k2 z LL转 x k1 // / \ ----\ \ / // x y ----/ o y z // // o // private Node leftLeftRotation(Node k1) { Node k2 = k1.left; //k2是k1的左子树 k1.left = k2.right;//k2的右子树 变为 k1 的左子树 k2.right = k1; //k1变为k2的右子树 k1.height = max(height(k1.left), height(k1.right)) + 1;//计算k1的高度 k2.height = max(height(k2.left), k1.height) + 1;//计算k2的高度 return k2;//返回新的根k2 } // 对如下的RR情况 // // k1 k2 // / \ / // x k2 RR转 k1 k3 // / \ ----\ / \ // y k3 ----/ x y z // // z // // 或 // // k1 k2 // / \ / // x k2 RR转 k1 k3 // / \ ----\ / \ / // y k3 ----/ x y z // / // z // public Node rightRightRotation(Node k1) { Node k2 = k1.right; k1.right = k2.left; k2.left = k1; k1.height = max(height(k1.left), height(k1.right)) + 1; k2.height = max(k1.height, height(k2.right)) + 1; return k2; } // 对如下的LR情况 // k1 k1 k3 // / \ / \ / // k2 z k2左旋 k3 z k1右旋 k2 k1 // / \ -----\ / \ -----\ / \ / // w k3 -----/ k2 y -----/ w x y z // / \ RR单转 / \ LL单转 // x y w x // public Node leftRightRotation(Node k1) { k1.left = rightRightRotation(k1.left); return leftLeftRotation(k1); } // 对如下的RL情况 // k1 k1 k3 // / \ k2右旋 / \ k1左旋 / // w k2 -----\ w k3 -----\ k1 k2 // / \ -----/ / \ -----/ / \ / // k3 z LL单转 x k2 RR单旋 w x y z // / \ / // x y y z // public Node rightLeftRotation(Node k1) { k1.right = leftLeftRotation(k1.right); return rightRightRotation(k1); } //插入 //删除 }
原文:http://www.cnblogs.com/noKing/p/8001608.html
内容总结
以上是互联网集市为您收集整理的AVL树(Java实现)全部内容,希望文章能够帮你解决AVL树(Java实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。