文件
专题 ·
最新
首页
  • 我的主页卡化石
  • off中心
  • 基本设置
  • 文件上传

avl树的插入和删除操作

硅谷探秘者 2999 0 0 
package avlTree;

import java.util.LinkedList;

/**
 * avl树（平衡二叉树）
 * @author Administrator
 *
 */
public class AvlTree {
	
	private Node<Integer> head=null;
	
	/**
	 * 返回较大的值
	 * @param l
	 * @param r
	 * @return
	 */
	public int max(int l, int r){
	    return (l > r ? l : r);
	}
	/**
	 * 获取树高度
	 * @param n
	 * @return
	 */
	public int hight(Node<Integer> n) {
	    if(n==null)
	        return -1;
	    else
	        return n.high;
	}
	/**
	 * 整个树是右旋的单旋转
	 * @param head
	 * @return
	 */
	public Node<Integer> singleRotateRight(Node<Integer> head){
		Node<Integer> tmp = head.left;
	    head.left = tmp.right;
	    tmp.right = head; //旋转后深度随之变化，需要修改深度
	    head.high = max(hight(head.left), hight(head.right)) + 1;
	    tmp.high = max(hight(tmp.left), hight(tmp.right)) + 1;
	    return tmp;//返回新的子树根节点
	}
	/**
	 * 整个树是左旋的单旋转
	 * @param head
	 * @return
	 */
	public Node<Integer> singleRotateLeft(Node<Integer> head){
		Node<Integer> tmp = head.right;
	    head.right = tmp.left;
	    tmp.left = head;
	    head.high = max(hight(head.left), hight(head.right)) + 1;
	    tmp.high = max(hight(tmp.left), hight(tmp.right)) + 1;
	    return tmp;
	}
	
	/**
	 * 整个树是右旋的双旋转
	 * @param head
	 * @return
	 */
	public Node<Integer> doubleRotateRight(Node<Integer> head){
	    head.left = singleRotateLeft(head.left);
	    return singleRotateRight(head);//再将整个树左旋
	}
	/**
	 * 整个树是左旋的双旋转
	 * @param head
	 * @return
	 */
	public Node<Integer> doubleRotateLeft(Node<Integer> head){
	    head.right = singleRotateRight(head.right);
	    return singleRotateLeft(head);//再将整个树右旋
	}
	
	/**
	 * 先根据二叉排序树规则插入，插完后进行平衡判断（递归法）
	 * @param head
	 * @param newnode
	 * @return
	 */
	private Node<Integer>  insert_node(Node<Integer>  head, Node<Integer>  newnode){
		Node<Integer>  tmp = head;
	    if(head==null){
	    	head=newnode;
	        return newnode;
	    }else{
		    if(tmp.getE() > newnode.getE()){
		        tmp.left = insert_node(tmp.left, newnode);//递归向左子树插入
		        //旋转
		        if(hight(tmp.left) - hight(tmp.right) == 2){
		            if(tmp.left.getE() > newnode.getE())//插到左子树左边，右旋(单旋转)
		                tmp = singleRotateRight(tmp);  
		            else//插到左子树右边，左子树先左旋整个树再右旋(双旋转)
		                tmp = doubleRotateRight(tmp);
		        }
		    }else if(tmp.getE() < newnode.getE()){
		        tmp.right = insert_node(tmp.right, newnode);//递归向右子树中插入
		        //旋转
		        if(hight(tmp.right) - hight(tmp.left) == 2){
		            if(tmp.right.getE() < newnode.getE())//插到右子树右边，左旋(单旋转)
		                tmp = singleRotateLeft(tmp);
		            else//插到右子树左边，右子树先右旋整个树再左旋(双旋转)
		                tmp = doubleRotateLeft(tmp);     
		        }
		    }
	    }
	    tmp.high = max(hight(tmp.left), hight(tmp.right)) + 1;
	    return tmp;
	}
	/**
	 * 添加节点
	 * @param data
	 */
	public void add(int data){
		Node<Integer> n=new Node<Integer>(data);
		if(head==null){
			head=n;
		}else{
			head=insert_node(head,n);
		}
	}
	
	/**
	 * 先序遍历（递归法）
	 */
	public void preErgodic(){
		pre(head);
		System.out.println();
	}
	private void pre(Node<Integer> n){
		if(n==null){
			return;
		}
		System.out.print(n.getE()+"  ");
		pre(n.left);
		pre(n.right);
	}
	
	/**
	 * 层级遍历
	 */
	public void cengDis() {
		Node<Integer> p=this.head;
		LinkedList<Node<Integer>> stack=new LinkedList<>();
		LinkedList<Node<Integer>> dui=new LinkedList<>();
		PrintfTree tree = null;
		dui.add(p);
		while(true){
			Node<Integer> f=null;
			if(dui.size()>0) {
				f=dui.removeFirst();
			}
			if(f==null) {
				Node<Integer> d=null;
				if(stack.size()>0) {
					d=stack.removeFirst();
				}
				if(d==null) {
					tree.show();
					return ;
				}else {
					dui.addLast(d);
					while(true) {
						d=null;
						if(stack.size()>0) {
							d=stack.removeFirst();
						}
						if(d==null) {
							break;
						}else {
							dui.addLast(d);
						}
					}
				}
			}else {
				if(tree==null) {
					tree=new PrintfTree(""+f.getE()+"("+f.high+")");
				}else {
					tree.add(new PrintfTree(""+f.getE()+"("+f.high+")"));
				}
				Node<Integer> left=f.left;
				if(left!=null) {
					stack.addLast(left);
				}
				Node<Integer> right=f.right;
				if(right!=null) {
					stack.addLast(right);
				}
			}
		}
	}
	/**
	 * 删除节点
	 * @param data
	 */
	public void del(int data){
		Node<Integer> n=new Node<Integer>(data);
		if(head!=null){
			head=remove(head,n);
		}
	}
	/**
	 * 删除节点（递归）
	 * @param tree
	 * @param z
	 * @return
	 */
	 private Node<Integer> remove(Node<Integer> tree, Node<Integer> z) {
        // 根为空 或者 没有要删除的节点，直接返回null。
        if (tree==null || z==null)
            return null;

        int cmp = z.getE()-tree.getE();
        if (cmp < 0) {        // 待删除的节点在"tree的左子树"中
            tree.left = remove(tree.left, z);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (hight(tree.right) - hight(tree.left) == 2) {
                Node<Integer> r =  tree.right;
                if (hight(r.left) > hight(r.right))
                    tree = doubleRotateLeft(tree);
                else
                    tree = singleRotateLeft(tree);
            }
        } else if (cmp > 0) {    // 待删除的节点在"tree的右子树"中
            tree.right = remove(tree.right, z);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (hight(tree.left) - hight(tree.right) == 2) {
                Node<Integer> l =  tree.left;
                if (hight(l.right) > hight(l.left))
                    tree = doubleRotateRight(tree);
                else
                    tree = singleRotateRight(tree);
            }
        } else {    // tree是对应要删除的节点。
            // tree的左右孩子都非空
            if ((tree.left!=null) && (tree.right!=null)) {
                if (hight(tree.left) > hight(tree.right)) {
                    // 如果tree的左子树比右子树高；
                    // 则(01)找出tree的左子树中的最大节点
                    //   (02)将该最大节点的值赋值给tree。
                    //   (03)删除该最大节点。
                    // 这类似于用"tree的左子树中最大节点"做"tree"的替身；
                    // 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
                    Node<Integer> max = maximum(tree.left);
                    tree.setE(max.getE());
                    tree.left = remove(tree.left, max);
                } else {
                    // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
                    // 则(01)找出tree的右子树中的最小节点
                    //   (02)将该最小节点的值赋值给tree。
                    //   (03)删除该最小节点。
                    // 这类似于用"tree的右子树中最小节点"做"tree"的替身；
                    // 采用这种方式的好处是：删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
                    Node<Integer> min = minimum(tree.right);
                    tree.setE(min.getE());
                    tree.right = remove(tree.right, min);
                }
            } else {
                Node<Integer> tmp = tree;
                tree = (tree.left!=null) ? tree.left : tree.right;
                tmp = null;
            }
        }

        return tree;
    }
 	/* 
     * 查找最小结点：前驱节点
     */
    private Node<Integer>  minimum(Node<Integer>  tree) {
        if (tree == null)
            return null;

        while(tree.left != null)
            tree = tree.left;
        return tree;
    }

    public Integer minimum() {
        Node<Integer>  p = minimum(head);
        if (p != null)
            return p.getE();
        return null;
    }
     
    /* 
     * 查找最大结点：后继节点
     */
    private Node<Integer>  maximum(Node<Integer>  tree) {
        if (tree == null)
            return null;
        while(tree.right != null)
            tree = tree.right;
        return tree;
    }

    public Integer maximum() {
        Node<Integer>  p = maximum(head);
        if (p != null)
            return p.getE();

        return null;
    }
}
package avlTree;

public class PrintfTree
{
	private String v;
	private PrintfTree l;
	private PrintfTree r;
	
	public PrintfTree(String v){
		this.v = v;
	}
	
	public void add(PrintfTree the){
		if(new Integer(the.v.substring(0,the.v.lastIndexOf("("))) < new Integer(v.substring(0,v.lastIndexOf("(")))){
			if(l==null) l = the;
			else l.add(the);
		}
		else{
			if(r==null) r = the;
			else r.add(the);
		}
	}
	
	public int getHeight(){
		int h = 2;
		int hl = l==null? 0 : l.getHeight();
		int hr = r==null? 0 : r.getHeight();
		return h + Math.max(hl,hr);
	}
	
	public int getWidth(){
		int w = (""+v).length();
		if(l!=null) w += l.getWidth();
		if(r!=null) w += r.getWidth();
		return w;
	}
	
	public void show(){
		char[][] buf = new char[getHeight()][getWidth()];
		printInBuf(buf, 0, 0);
		showBuf(buf);
	}
	
	private void showBuf(char[][] x){
		for(int i=0; i<x.length; i++){
			for(int j=0; j<x[i].length; j++)
				System.out.print(x[i][j]==0? ' ':x[i][j]);
			System.out.println();
		}
	}
	
	private void printInBuf(char[][] buf, int x, int y){
		String sv = "" + v;
		
		
		int p1 = l==null? x : l.getRootPos(x);
		int p2 = getRootPos(x);
		int p3 = r==null? p2 : r.getRootPos(p2+sv.length());
		
		buf[y][p2] = '|';
		for(int i=p1; i<=p3; i++) buf[y+1][i]='-';
		for(int i=0; i<sv.length(); i++) buf[y+1][p2+i]=sv.charAt(i); 
		if(p1<p2) buf[y+1][p1] = '/';
		if(p3>p2) buf[y+1][p3] = '\\';
		
		if(l!=null) l.printInBuf(buf,x,y+2);
		if(r!=null) r.printInBuf(buf,p2+sv.length(),y+2);
	}
	
	private int getRootPos(int x){
		return l==null? x : x + l.getWidth();
	}
}
package avlTree;

public class Node<E> {
	private E e;//数据
	public Node<E> left;//左子树
	public Node<E> right;//右子树
	public int high;//树高度
	public E getE() {
		return e;
	}
	public void setE(E e) {
		this.e = e;
	}
	public Node<E> getLeft() {
		return left;
	}
	public void setLeft(Node<E> left) {
		this.left = left;
	}
	public Node<E> getRight() {
		return right;
	}
	public void setRight(Node<E> right) {
		this.right = right;
	}
	public int getHigh() {
		return high;
	}
	public void setHigh(int high) {
		this.high = high;
	}
	public Node(E e) {
		super();
		this.e = e;
		this.high=0;
	}
	public Node() {
		super();
		// TODO Auto-generated constructor stub
		this.high=0;
	}
	
}
package avlTree;

public class TestMain {
	public static void main(String[] args) {
		AvlTree avl=new AvlTree();
		avl.add(1);
		avl.add(2);
		avl.add(3);
		avl.add(4);
		avl.add(5);
		avl.add(6);
		avl.add(7);
		avl.add(8);
		avl.add(9);
		avl.cengDis();
		avl.del(4);
		avl.cengDis();
	}
}

image.png


评论区
请写下您的评论...
暂无评论...
猜你喜欢
weblog 4702 红黑树简介 红黑树（RedBlackTree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定
数据结构与算法 4108 ),任一节点的平衡因子是-1,0,1之一2.avl树的操作AVL树的操作基本和二叉查找树一样，这里我们关注的是两个变化很大的操作：插入和删除！AVL树不仅是一颗二叉查找树，它还有其他的性质。如果我们按照一般
数据结构与算法 3286 二叉树删除节点c++先看一个简单的树图删除节点是分以下几种情况：1.待删节点为叶子节点：此种情况下直接删除叶子节点即可2.待删节点只有左子树，或只有右子树，那么将左子树或右子树的根节点替换该节点即可
数据结构与算法 2977 链式栈的出栈入栈操作c++描述基于双向链表//节点classnode{public:intdata;node*next;node*prev;};//双向链表#include"node.h
数据结构与算法 4980 二叉树基本操作c++classnode{public: intdata; node*left; node*right; node(); node(intdata); node(intdata
official 680 《操作系统》操作系统的特征
official 729 上层的应用程序、用户提供简单易用的服务3.操作系统是系统软件，而不是硬件定义：操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的
official 837 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为要被删除的节点。现有一个链表--head=[4,5,1,9]，它可以表示为:示例1：输入：head=[4,5,1,9],n
最新发表
归档
2018-11  12 2018-12  33 2019-01  28 2019-02  28 2019-03  32 2019-04  27 2019-05  33 2019-06  6 2019-07  12 2019-08  12 2019-09  21 2019-10  8 2019-11  15 2019-12  25 2020-01  9 2020-02  5 2020-03  16 2020-04  4 2020-06  1 2020-07  7 2020-08  13 2020-09  9 2020-10  5 2020-12  3 2021-01  1 2021-02  5 2021-03  7 2021-04  4 2021-05  4 2021-06  1 2021-07  7 2021-08  2 2021-09  8 2021-10  9 2021-11  16 2021-12  14 2022-01  7 2022-05  1 2022-08  3 2022-09  2 2022-10  2 2022-12  5 2023-01  3 2023-02  1 2023-03  4 2023-04  2 2023-06  3 2023-07  4 2023-08  1 2023-10  1 2024-02  1 2024-03  1 2024-04  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy srs 音视频 webrtc javascript
目录
没有一个冬天不可逾越，没有一个春天不会来临。最慢的步伐不是跬步，而是徘徊，最快的脚步不是冲刺，而是坚持。