花了一个多小时手撸的AVL树

package com.example.demo;

public class AVLTree {
	AVLNode root;
	/**
	 * 插入节点
	 * @param data
	 */
	public void put(int data) {
		putData(root, data);
	}
	private boolean putData(AVLNode node, int data) {
		if(node == null) {
			node  = new AVLNode(data);
			root = node;
			return true;
		}
		int t;
		AVLNode p;
		AVLNode temp = node;
		do {
			p = temp;
			t = temp.data - data;
			if(t < 0) {
				temp = temp.rc;
			}
			else if(t > 0) {
				temp = temp.lc;
			}
			else {
				return false;
			}
		} while(temp != null);
		
		if(t < 0) {
			p.rc = new AVLNode(p, data);
		}
		else if(t > 0) {
			p.lc = new AVLNode(p, data);
		}
		adjustTree(p);
		return true;
	}
	/**
	 * 右旋
	 * @param node
	 * @return
	 */
	public AVLNode rightHanded(AVLNode node){
		if(node!=null){
			//摘左子树
			AVLNode lc=node.lc;
			//改变左子树的右节点到根节点的左节点
			node.lc=lc.rc;
			if(lc.rc!=null){
				lc.rc.parent=node;
			}
			//改变父节点指向关系
			lc.parent=node.parent;
			if(node.parent==null){
				this.root=lc;
			}else if(node.parent.lc==node){
				node.parent.lc=lc;
			}else if(node.parent.rc==node){
				node.parent.rc=lc;
			}
			//改变根节点和左节点关系
			node.parent=lc;
			lc.rc=node;
			return lc;
		}
		return null;
	}
	public void adjustTree(AVLNode node){
	  while(node!=null){
		if(getBalanceValue(node)==2){
			if(node.lc.lc!=null){
				rightHanded(node);
			}else if(node.lc.rc!=null){
				 leftHanded(node.lc);
				 rightHanded(node);
			}
		}else if(getBalanceValue(node)==-2){
			if(node.rc.rc!=null){
				leftHanded(node);
			}else if(node.rc.lc!=null){
				 rightHanded(node.lc);
				 leftHanded(node);
			}
		}
		node=node.parent;
	  }
	}
	public int getDepth(AVLNode node){
		if(node==null)
			return 0;
		return Math.max(getDepth(node.lc),getDepth(node.rc))+1;
	}
	public int getBalanceValue(AVLNode node){
		if(node==null)
			return 0;
		return getDepth(node.lc)-getDepth(node.rc);
	}
	public static void main(String[] args) {
		AVLTree at=new AVLTree();
		at.put(1);
		at.put(2);
		at.put(3);
		System.out.println(at.getDepth(at.root.rc));
		System.out.println(at.getDepth(at.root.lc));

	}
	/**
	 * 左旋
	 * @param node
	 * @return
	 */
	public AVLNode leftHanded(AVLNode node){
		if(node!=null){
			//摘右子树
			AVLNode rc=node.rc;
			//改变右节点左子树与根节点的指向关系
			node.rc=rc.lc;
			if(rc.lc!=null){
				rc.lc.parent=node;
			}
			//改变父节点指向关系
			rc.parent=node.parent;
			if(node.parent==null){
				this.root=rc;
			}else if(node.parent.lc==node){
				node.parent.lc=rc;
			}else if(node.parent.rc==node){
				node.parent.rc=rc;
			}
			//改变根节点和右节点关系
			node.parent=rc;
			rc.lc=node;
			return rc;
		}
		
		return null;
	}
	/**
	 * 中序遍历
	 */
	public void middOrderErgodic() {
		this.middOrderErgodic(this.root);
	}
	public void middOrderErgodic(AVLNode node) {
		if(node != null) {
			this.middOrderErgodic(node.lc);
			System.out.print(node.data + ", ");
			this.middOrderErgodic(node.rc);
		}
	}
}
/**
 * AVL树节点
 * @author rbb
 *
 */
class AVLNode{
	public AVLNode parent;
	public AVLNode lc;
	public AVLNode rc;
	public int data;
	public AVLNode(AVLNode parent, AVLNode leftChild, AVLNode rightChild, int data) {
		this.parent = parent;
		this.lc = leftChild;
		this.rc = rightChild;
		this.data = data;
	}
	
	public AVLNode(int data) {
		this(null, null, null, data);
	}
	
	public AVLNode(AVLNode parent, int data) {
		this.parent = parent;
		this.data = data;
	}
}