package net.bobo;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Date;
import java.util.List;
public class AVLTree<T extends Comparable> {
private Node<T> root;
/**
* 按照顺序打印树,即中序遍历
*/
public void printByOrder(){
printByOrder(root);
System.out.println("");
}
/**
* 按顺序打印树(中序遍历)的实现例程
* @param root
*/
private void printByOrder(Node<T> root){
if(root == null) return;
printByOrder(root.left);
System.out.println(root.value+"("+(root.left == null?"空":root.left.value)+","+(root.right == null?"空":root.right.value)+")");
printByOrder(root.right);
}
public void delete(T value){
this.root = delete(this.root,value);
}
private Node<T> delete(Node<T> parent,T value){
if(parent == null) return null;
System.out.println("删除进入到:"+parent.value);
//找到了插入的节点
if(parent.value.compareTo(value) == 0){
//左子树为空
if(parent.left == null){
return parent.right;
}
//右子树为空
if(parent.right == null){
return parent.left;
}
//现在左右子树都不为空,找到中序遍历最后的节点,然后删除该节点
Node<T> maxLeftNode = parent.left;
Node<T> newDeletedNode = maxLeftNode;
while(maxLeftNode != null){
maxLeftNode = maxLeftNode.right;
if(maxLeftNode != null) newDeletedNode = maxLeftNode;
}
//找到了最新要删除的节点newDeletedNode,先将该节点的值赋给parent,然后删除最新要删除的节点
parent.value = newDeletedNode.value;
//递归删除最新的节点
parent.left = delete(parent.left,newDeletedNode.value);
return parent;
}
//如果父节点大于要删除的节点,进入到父节点的左子树
if(parent.value.compareTo(value) > 0){
parent.left = delete(parent.left,value);
}else{//如果父节点小于要删除的节点,进入到父节点的右子树
parent.right = delete(parent.right,value);
}
parent = rotate(parent);
return parent;
}
public void insert(T value){
System.out.println("开始插入:"+value);
//如果没有根节点
if(root == null){
root = new Node(value);
return;
}
root = insertNode(root,value);
}
/**
* 插入节点的实现例程
* @param parent 父节点
* @param value 需要插入的值
* @return 返回插入完成的树
*/
private Node<T> insertNode(Node<T> parent,T value){
//如果父节点为空,说明已经到达底部,value新节点为叶子节点
if(parent == null){
Node<T> newNode = new Node<T>(value);
return newNode;
}
if(parent.value.compareTo(value) == 0) return parent;
if(parent.value.compareTo(value) > 0){
parent.left = insertNode(parent.left,value);
}else{
parent.right = insertNode(parent.right,value);
}
//试着对树进行旋转
parent = rotate(parent);
System.out.println(parent.value+" >>> 左树高度:"+parent.leftHeight()+" 右树高度:"+parent.rightHeight());
return parent;
}
/**
* 旋转树,根据情况进行左旋或者右旋
* @param parent
* @return 返回旋转后达到平衡的新的树
*/
private Node<T> rotate(Node<T> parent){
int leftHeight = parent.leftHeight();
int rightHeight = parent.rightHeight();
//左子树的高度比右子树高2
if((leftHeight >= rightHeight && (leftHeight - rightHeight) >= 2)){
Node<T> leftChild = parent.left;
//左节点的左子树比右子树高,左左型,需要一次左旋
if((leftChild.leftHeight() > leftChild.rightHeight())){
parent = leftRotate(parent,leftChild);
}else{//左右型,需要一次右旋和一次左旋
parent.left = rightRotate(parent.left,parent.left.right);
parent = leftRotate(parent,parent.left);
}
//右子树的高度比左子树高2
}else if((rightHeight > leftHeight && (rightHeight - leftHeight) >=2 )){
Node<T> rightChild = parent.right;
//右节点的右子树比左子树高,右右型,需要一次右旋
if(rightChild.rightHeight() > rightChild.leftHeight()){
parent = rightRotate(parent,rightChild);
}else{
parent.right = leftRotate(parent.right,parent.right.left);
parent = rightRotate(parent,parent.right);
}
}
return parent;
}
private Node<T> leftRotate(Node<T> p1,Node<T> p2){
Node<T> p2Right = p2.right;
p2.right = p1;
p1.left = p2Right;
return p2;
}
private Node<T> rightRotate(Node<T> p1,Node<T> p2){
Node<T> p2Left = p2.left;
p2.left = p1;
p1.right = p2Left;
return p2;
}
private class Node<T extends Comparable>{
//左子树
private Node<T> left;
//右子树
private Node<T> right;
//父节点
private Node<T> parent;
//数据
private T value;
public Node(T value){
this.value = value;
}
public int leftHeight(){
return calculateHeight(left);
}
public int rightHeight(){
return calculateHeight(right);
}
/**
* 计算该树的高度
* @return
*/
public int calculateHeight(){
return calculateHeight(this);
}
/**
* 计算树的高度
* @param tree
* @return
*/
private int calculateHeight(Node<T> tree){
if(tree == null) return -1;
int leftHeight = calculateHeight(tree.left);
int rightHeight = calculateHeight(tree.right);
return 1+(leftHeight > rightHeight?leftHeight:rightHeight);
}
}
public static void main(String[] args){
int max = 20;
List<Integer> values = new ArrayList<Integer>();
for(int i = 1; i <= max; i++){
values.add(i);
}
Collections.shuffle(values);
Integer[] testValues = {5,4,10,7,11,9};
values = Arrays.asList(testValues);
for(Integer value:values)
System.out.print(value+" ");
System.out.println("");
AVLTree<Integer> tree = new AVLTree<Integer>();
for(Integer value:values)
tree.insert(value);
tree.printByOrder();
System.out.println(System.currentTimeMillis()+" "+new Date().getTime());
System.out.println("删除节点");
tree.delete(4);
tree.printByOrder();
tree.delete(5);
tree.printByOrder();
}
}
分享到:
相关推荐
平衡二叉树实现 平衡二叉树的实质就是保持树“尽量胖,尽量矮
AVL tree的源码实现。该AVL tree为模板容器,可以在其中放入任何东西。被放入的对象需要实现拷贝构造函数与赋值构造函数。该程序能够在linux下面顺利通过编译。平时随意开发,如有不足之处,还请见谅!!!
本设计实现了AVLTree的所有的实现功能,也包括BinSTree与AVLTree的转换
一个avltree的简单实现,便于了解avltree的结构及应用
涉及如何构建平衡二叉树,是C语言源代码,最流行的算法
这是一个用C实现的AVL tree,带MFC的测试程序。 在我的机器上(P4 T2050 Duo, 1G memory)列C盘所有文件并组织成AVL tree,一共是70000多个文件和目录,耗时大约是5-7秒
使用C++实现的AVLTree自平衡二叉树,支持动态插入与删除操作,供C++数据结构课程学习与交流使用。
自己写的平衡树的构建及相关操作
avltree的c代码实现,没有错,放心下载
AVLTREE,数据结构中AVL树的C语言实现
Java代码实现,从文件中读取数据,根据AVL树的构建规则,构建一棵AVL树(平衡二叉树),并输出平均查找长度ASL。
有mfc的界面, 单词的存储结构为avltree 实现单词增删改查 搜索计时 背单词功能
这是一个AvlTree的实现程序,类函数的实现代码是《数据结构与算法分析C++描述》([美] Mark Allen Weiss,人民邮电出版社)这本书里的。我简单地调用了类里的函数,但是没有用很多的数据去测试,我是用VC 6.0实现的。
用AVL-tree数据结构作为底层机制,以STL底层空间配置器和iterator_traits编程技法实作出一个独立的关联式容器(map, set, multimap, multiset),并对外提供接口实现和STL完全兼容的容器。
该代码包括了二叉树、二叉查找树、平衡树的Java实现代码
AVLTree(平衡二叉树)是常用的数据结构,文件中包括该数据结构的实现、基于该数据结构的算法详细分析,下载可直接运行调试,可供数据结构与算法课程的学习
avl树实现 数据结构数据结构数据结构数据结构
C语言实现的AVL树,实现了插入、删除、查找、rank、非递归前序、中序、后序遍历
(1)编写 AVL树判别程序,并判别一个二元查找树是否为 AVL树。二元查找树用其先序遍历结果表示,如:...(2)实现 AVL树的 ADT,包括其上的基本操作:结点的加入和删除;另外包括将一般二元查找树转变为 AVL树的操作。
c++平衡二叉树的实现 带内存分配,非常全面 ,有错误欢迎留言