文档章节

基本数据结构之AvlTree

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/10/21 19:42
字数 616
阅读 91
收藏 1

问题描述: 

AvlTree


问题分析: 

基本的实现

代码实现:

package c04;
/**
 * @project: DataStructureAndAlgorithmAnalysis
 * @filename: AvlTree.java
 * @version: 0.10
 * @author: JM Han
 * @date: 15:04 2015/10/21
 * @comment: Test Purpose
 * @result:
 */

import master.UnderflowException;

import static tool.util.*;

public class AvlTree<AnyType extends Comparable<? super AnyType>>{
   private static final int ALLOWED_IMBALANCE = 1;
   private AvlNode<AnyType> root;

   private static class AvlNode<AnyType>{
      AvlNode(AnyType theElement)
      {this(theElement, null, null);}

      AvlNode(AnyType theElement, AvlNode lt, AvlNode rt)
      {element = theElement; left = lt; right = rt;}

      AnyType element;
      AvlNode<AnyType> left;
      AvlNode<AnyType> right;
      int height;
   }

   public int height(AvlNode<AnyType> t){
      return t == null?-1:t.height;
   }

   public boolean isEmpty(){
      return null == root;
   }

   public void insert(AnyType x){
      root = insert(x,root);
   }

   public void remove(AnyType x){
      root = remove(x,root);
   }

   public AnyType findMin(){
      if(isEmpty())
         throw new UnderflowException();
      return findMin(root).element;
   }

   public AnyType findMax(){
      if(isEmpty())
         throw new UnderflowException();
      return findMax(root).element;
   }

   public boolean contains(AnyType x){
      return contains(x, root);
   }

   public void printTree(){
      if(isEmpty())
         System.out.println("Empty Tree");
      else
         printTree(root);
   }

   private AvlNode<AnyType> insert(AnyType x, AvlNode<AnyType> t){
      if(null == t)
         return new AvlNode<AnyType>(x, null, null);

      int compareResult = x.compareTo(t.element);

      if(compareResult < 0)
         t.left = insert(x, t.left);
      else if(compareResult > 0)
         t.right = insert(x, t.right);
      else
         ;//Duplicat, do nothing

      return balance(t);
   }

   private AvlNode<AnyType> balance(AvlNode<AnyType> t) {
      if (null == t)
         return t;

      if (height(t.left) - height(t.right) > ALLOWED_IMBALANCE) {
         if (height(t.left.left) >= height(t.left.right))
            t = rotateWithLeftChild(t);
         else
            t = doubleWithLeftChild(t);
      }
      else if(height(t.right) - height(t.left) > ALLOWED_IMBALANCE){
         if(height(t.right.right) >= height(t.right.left))
            t = rotateWithRightChild(t);
         else
            t = doubleWithRightChild(t);
      }
      //不进行Rotate操作时依然需要更新t的height
      t.height = Math.max(height(t.left), height(t.right)) + 1;
      return t;

   }

   private AvlNode<AnyType> rotateWithLeftChild(AvlNode<AnyType> k2){
      AvlNode<AnyType> k1 = k2.left;
      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;
   }

   private AvlNode<AnyType> rotateWithRightChild(AvlNode<AnyType> k2){
      AvlNode<AnyType> k1 = k2.right;
      k2.right = k1.left;
      k1.left = k2;
      k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
      k1.height = Math.max(height(k1.right), k2.height) + 1;
      return k1;
   }

   private AvlNode<AnyType> doubleWithLeftChild(AvlNode<AnyType> k3){
      k3.left = rotateWithRightChild(k3.left);
      return rotateWithLeftChild(k3);
   }

   private AvlNode<AnyType> doubleWithRightChild(AvlNode<AnyType> k3){
      k3.right = rotateWithLeftChild(k3.right);
      return rotateWithRightChild(k3);
   }


   private AvlNode<AnyType> remove(AnyType x, AvlNode<AnyType> t){
      if(null == t)
         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 balance(t);
   }

   private AvlNode<AnyType> findMin(AvlNode<AnyType> t){
      if(null == t)
         return null;
      else if(t.left == null)
         return t;
      return findMin(t.left);
   }

   private AvlNode<AnyType> findMax(AvlNode<AnyType> t){
      if(t != null)
         while(t.right != null)
            t = t.right;
      return t;
   }

   private boolean contains(AnyType x, AvlNode<AnyType> t){
      if(t == null)
         return false;

      int comparableResult = x.compareTo(t.element);

      if(comparableResult < 0)
         return contains(x, t.left);
      else if(comparableResult > 0)
         return contains(x, t.right) ;
      else
         return true;
   }

   private void printTree(AvlNode<AnyType> t){
      if(null != t){
         printTree(t.left);
         System.out.println(t.element);
         printTree(t.right);
      }
   }

   public static void main(String[] args) {
      AvlTree<Integer> avlt = new AvlTree<Integer>();
      avlt.insert(4);
      avlt.insert(3);
      avlt.insert(6);
      avlt.insert(0);
      avlt.insert(2);
      avlt.insert(3);
      avlt.printTree();
      System.out.println("Contains 3: " + avlt.contains(3));
      System.out.println("Max: " + avlt.findMax());
      System.out.println("Min: " + avlt.findMin());
      avlt.remove(3);
      avlt.printTree();
   }


}

代码输出:

0
2
3
4
6
Contains 3: true
Max: 6
Min: 0
0
2
4
6


© 著作权归作者所有

共有 人打赏支持
关西大汉弹琵琶
粉丝 7
博文 41
码字总数 14221
作品 0
浦东
程序员
avltree、bstree、rbtree和Splaytree

具体参考:https://github.com/nfs-ganesha/nfs-ganesha

itfanr
2015/08/10
0
0
跨平台C + +库--CrissCross

CrissCross是一种小型的跨平台C + +库,用于处理控制台和文件I / O , CPU的识别( CPUID ) ,散列( MD2 , MD4 , MD5编码,了SHA - 1 ,SHA- 256 ,SHA- 512 ,Tiger) ,Socket( TCP和...

匿名
2009/02/09
4.1K
0
AVL树-scala实现

二叉查找树已经能够很好的应用到应用程序中,但它们在最坏的情况下性能还是很糟糕。考虑到如图所示这种情况:查找操作的性能完全等同于线性。而AVL树的查找操作,能够保证无论怎么构造它,运...

venps
2016/02/14
2.9K
8
Phalcon7 1.2.2 重要更新2:修复 model 相关 bug

Phalcon7 是继承自 Phalcon 1.3.x,开源、全功能栈、使用 C 编写、针对 PHP 7 优化的高性能框架。 开发者不需要学习和使用 C 语言的功能, 因为所有的功能都以 PHP 类的方式暴露出来,可以直...

朱宗鑫1
2017/01/15
429
0
skalibs 1.1.1 发布,低级的 C 程序库

skalibs 1.1.1 发布,该版本修复了一个当使用avltree 架构时潜在的segfault错误。 skalibs 是一组用于一般用途的、低级的 C 程序库,可替换标准 C 库的一些方法,主要用于构建很小的静态二进...

小卒过河
2011/07/27
476
3

没有更多内容

加载失败,请刷新页面

加载更多

在t-io老巢造谣,不过有造谣的就会有反造谣的!

只发当事人的截图,不发表评论,以免有引导嫌疑 PS: 截图是由不同的人发过来的 本人已经不在此微信群 图3:有造谣的,就有反造谣的 图4是2018-09-23的t-io官方群的一个发言小统计,有助于让...

talent-tan
今天
80
0
heartbeat 资源

drbd+apache+heartbeat : http://blog.51cto.com/11838039/1827901 heartbeat双机热备的架设 : http://blog.51cto.com/11838039/1827560 对heaetbeat的深一步认识 : http://blog.51cto.co......

寰宇01
今天
4
0
Spring 转换 model 为 json 时增加属性

缘起 目前的项目中有个需求是在附件对象转换成 json 时增加个 url 属性,以前的方式是在返回附件对象或列表时候做一次统一处理,这次想看看 spring 或者 jackson fasterxml 是否自带类似功能...

郁也风
今天
4
0
10大PHP比特币开源项目

如果你是一个Phper,如果你希望学习区块链,那么本文列出的 10个开源的Php比特币项目,将有助于你了解在自己的应用中 如何加入对比特币的支持。 如果你希望快速掌握使用Php对接比特币钱包的方...

汇智网教程
今天
5
0
springclould feign客户端添加全局参数

用springclould feign作为调用服务的客户端,一般来说参数可以写在feignclient的方法参数里 有时需要所有feign请求都统一添加一些参数,例如token用于鉴权等,可以这样做: 添加一个配置类,...

canneljls
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部