AVL 树的插入与旋转

/** * * @author xuejianxinokok * @date 2011-05-28 * */ public class AVLTree { /** * p (parent) * lc (left child) * rc (right child) * lgc (left grandchild) * rgc (right grandchild) */ private static class AVLNode{ public Object nodeValue; public AVLNode left,right; public int height; public AVLNode(Object item){ nodeValue=item; left=null; right=null; height=0; } } private AVLNode root;//树根 private int treeSize;//树节点数量 public AVLTree(){ //空构造函数 root=null; treeSize=0; } public AVLTree(AVLNode item){ root=item; treeSize=1; } public boolean add(Object item){ try { root=addNode(root,item); } catch (Exception e) { e.printStackTrace(); return false; } treeSize++; return true; } private AVLNode addNode(AVLNode t, Object item) { if(null==t){ t=new AVLNode(item); }else if(((Comparable)item).compareTo((Comparable)t.nodeValue)<0) { //左子树 t.left=addNode(t.left, item); if(height(t.left)-height(t.right)==2){ if(((Comparable)item).compareTo((Comparable)t.left.nodeValue)<0){ t=singleRotateRight(t);//左子树 左节点 }else { t=doubleRotateRight(t);//左子树 右节点 } } } else if(((Comparable)item).compareTo((Comparable)t.nodeValue)>0) { //右子树 t.right=addNode(t.right, item); if(height(t.left)-height(t.right)==-2){ if(((Comparable)item).compareTo((Comparable)t.right.nodeValue)>0){ t=singleRotateLeft(t); }else { t=doubleRotateLeft(t); } } } t.height=max(height(t.left), height(t.right))+1; return t; } /** 以 p 节点的左子节点 右旋转 * p lc * / / / / * lc rc ===> lgc p * / / / / / * lgc rgc item rgc rc * / * item * * @param p * @return */ private AVLNode singleRotateRight(AVLNode p) { AVLNode lc=p.left;//定位到 父节点P 的 左子节点 p.left=lc.right; lc.right=p; p.height=max(height(p.left),height(p.right))+1; lc.height=max(height(lc.left),height(lc.right))+1; return lc; } /** 以 p 节点的右子节点 左旋转 * p rc * / / / / * lc rc ===> p rgc * / / / / / * lgc rgc lc lgc item * / * item * @param p * @return */ private AVLNode singleRotateLeft(AVLNode p) { AVLNode rc=p.right;//定位到 父节点P 的 左子节点 p.right=rc.left; rc.left=p; p.height=max(height(p.left),height(p.right))+1; rc.height=max(height(rc.left),height(rc.right))+1; return rc; } /** * p p rgc * / / / / / / * lc rc 以rgc 左旋 rgc rc 以rgc右旋 lc p * / / ==========> / / ===========> / / / / * lgc rgc lc item lgc 空 item rc * / / / / * 空 item lgc 空 * * @param p * @return */ private AVLNode doubleRotateRight(AVLNode p) { p.left=singleRotateLeft(p.left); return singleRotateRight(p); } /** * p p lgc * / / / / / / * lc rc lgc右旋 lc lgc lgc左旋 p rc * / / ===========> / / ==========> / / / / * lgc rgc item rc lc item 空 rgc * / / / / * item 空 空 rgc * * @param p * @return */ private AVLNode doubleRotateLeft(AVLNode p) { p.right=singleRotateRight(p.right); return singleRotateLeft(p); } private int max(int height1, int height2) { if(height1>=height2){ return height1; }else { return height2; } } private static int height(AVLNode t){ if(null==t){ return -1; }else { return t.height; } } public static void main(String[] args) { AVLTree tree=new AVLTree(); tree.add("1"); tree.add("2"); tree.add("3"); tree.add("4"); tree.add("5"); /*tree.add("3"); tree.add("2"); tree.add("1");*/ System.out.println(""); } }