文档章节

基本数据结构之AvlTree

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

问题描述: 

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
skalibs 1.1.1 发布,低级的 C 程序库

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

小卒过河
2011/07/27
476
3
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.2 发布,C语言底层程序库

skalibs 是一组用于一般用途的、低级的 C 程序库,可替换标准 C 库的一些方法,主要用于构建很小的静态二进制文件。 Changes: This release clarifies the avlnode, avltree, and avltreen A...

红薯
2011/08/17
833
0
SonarQube Java 4.1 发布

SonarQube Java 4.1发布了。Sonar (SonarQube)是一个开源平台,用于管理源代码的质量。Sonar 不只是一个质量数据报告工具,更是代码质量管理平台。支持的语言包括:Java、PHP、C#、C、Cob...

oschina
2016/08/05
2.1K
3
ASN.1编码规则(数据类型)

ASN.1中定义的数据类型既有简单的基本数据类型,也有复杂的结构类型。 基本类型是不可再再分的,包括: 布尔型(BOOLEAN) 整型(INTEGER) 实型(REAL) 位串类型(BITSTRING) 8位位组类型...

DayDayUpCQ
2013/07/05
0
0
C语言/C加加程序员新手入门学习基础之数据类型分享

请点击此处输入图片描述 关注我们 为什么要首先介绍数据类型? 因为(数据结构就是对数据类型的操作)不论是哪一种语言,都要有其基本数据类型,这些基本的数据类型就像一块块砖,而程序中的...

小辰GG
2017/12/30
0
0
Python 基础:数据类型和结构(二)丨数析学院

课程简介 本节为 Python 金融数据分析基础课程,将重点介绍 Python 基本数据类型和数据结构,此外,也对 NumPy 库特有的数据结构进行了说明。建议初学者认真学习本节内容,已经掌握数据结构的...

Datartisan数据工匠
2017/11/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

istio源码分析之pilot-discovery模块分析

本文分析的istio代码版本为0.8.0,commit为0cd8d67,commit时间为2018年6月18日。 本文为Service Mesh深度学习系列之一: Service Mesh深度学习系列part1—istio源码分析之pilot-agent模块分...

xiaomin0322
7分钟前
0
0
数据库基本操作:增删改查及联表操作

所用软件:SQL Server Management Studio 首先第一步,建立一个表。在这里命名为T1。并在里面填入几条数据。如图: T1 一.查询 查询所有:select * from T1; 按条件查询:select * from T1 ...

小_橙_子
11分钟前
0
0
Crontab作业时间设置

今天,遇到这么一个题目,周一到周五的9:00-16:59之间,每隔两分钟将某个命令运行一次。给的答案是: */2 9-16 * * 1-5 /usr/sbin/somecommand dosomething 乍一看,这个答案不对,应...

大别阿郎
16分钟前
0
0
ES17-JAVA API文档管理

1.保存文档 可以通过json工具把java对象转换成json字符串进行保存,也可以通过内置的帮助类直接构建json格式 /** * 获取客户端 * * @return */public static TransportClie...

贾峰uk
16分钟前
0
0
Python代码规范和命名规范

前言 Python 学习之旅,先来看看 Python 的代码规范,让自己先有个意识,而且在往后的学习中慢慢养成习惯 一、简明概述 1、编码 如无特殊情况, 文件一律使用 UTF-8 编码 如无特殊情况, 文件头...

blackfoxya
19分钟前
0
0
联动滑动之一:NestScrollChild和NestedScrollingParent

NestScrollChild和NestedScrollingParent 吐槽一下开源中国竟然标题字数有限制 由于项目中使用了CoordinateLayout来解决联动以及实现炫酷的UI效果,那么必须就要研究一波源码了,毕竟知其然知...

JerryLin123
36分钟前
1
0
cloudera spark2.2 读写hbase

cloudera spark2.2 读写hbase 例子 host = 'bigdata-03,bigdata-05,bigdata-04'conf = { "hbase.zookeeper.quorum": host, "hbase.mapreduce.inputtable": "student1"}k......

osenlin
41分钟前
0
0
数据库规范化

转载自 一个小时学会MySQL数据库 地址:http://www.cnblogs.com/best/p/6517755.html 截取其中 1.4 部分 用于自己学习使用 感谢作者:张果 1.4、数据库规范化 经过一系列的步骤,我们现在终于...

十万猛虎下画山
42分钟前
0
0
ios逆向之工具篇

Reveal:查看任意app的UI结构 注:1.不越狱的手机,可以用Reveal来查看自己app的UI结构,不能查看其它app的结构。 2.越狱手机上可以查看任意app的UI结构。 IDA:反编译工具 从App Store下载的...

HeroHY
42分钟前
0
0
EOS区块链平台智能合约示例HelloWorld

我们将介绍一个使用EOS智能合约构建hello World的例子。 一般环境设置通过上一篇文章已经说明,这方面的问题大家可以看本博客上一篇文章,本文引用了官方EOS在Git上的示例。 运行nodeos 要通...

笔阁
44分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部