java实现二叉平衡树_java实现二叉树 如何保证不重叠

1. 二叉平衡树定义
   二叉树中所有子树的左右子树的高度差不超过1

2. 树的高度
   从所有叶节点开始数高度到根节点，其中的最大值即为树的高度

3. 非平衡二叉树转成平衡二叉树(思路)

1. 找出所有不平衡的子树,将不平衡子树的根节点记录下来.
2. 调节位于最下方的子树,使之平衡
3. 重复1,2步,直到这棵树平衡
   每次调整只调整节点数最少的子树,节点少的子树大部分情况都为4中的基本情况

4. 二叉树的调节(旋转)
   不平衡的情况(符合二叉树的规则大的节点在右边,小的在左)
   图一
   
   图二
   

图一中
1,2两种情况,分别以中间的节点为旋转中心顺时针(1),逆时针(2)将根节点旋转到中间节点的下方.(两种情况对应)
3,4两种情况,将最下方的节点作为根节点,分别将根节点,中间节点作为最下方节点的左右子节点.(两种情况对应)
处理图:(四种情况中列出两种,其余两种对应)

图二中
1(ll),2(rr)两种情况,分别以根节点的左子节点(1),右子节点(2)为旋转中心,将跟节点选装至他子节点的下方,子节点的右(左)子节点,称为根节点的左(右)子节点.(两种情况对应)

3(lr),4(rl)两种情况,以最下方的叶子节点的父节点为旋转中心,将跟节点的左(右)子节点旋转至其父节点的下方,这样3,4两种情况就转化成了1,2两种情况,再用处理1,2两种情况的方法处理.(两种情况对应)
处理图:(四种情况中列出两种,其余两种对应)

其余情况:最小的不平衡子树的高度超过4

只需将根节点旋转至节点少的这一侧即可

5. 算法设计及实现

了解了大致情况,要转换成二叉树,节点的变换,
(1)左右节点变化(是否从有到无或者从无到有),过程中很可能忘记setRight(null)操作,这样这棵树就完全乱了.我的User类中在设置左右节点时,就将左右节点的父节点设置成当前节点

public void setLeft(User faust) {
		
		this.left = faust;
		if(faust != null)
			faust.head = this;
		
	}

	public void setRight(User pippin) {
		
		this.right = pippin;
		if(pippin != null)
			pippin.head = this;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

(2)根节点是否改变,根节点没有父节点要setHead(null); root = user;这两步操作

计算树的高度

public int getDepth(User treeRoot){
		
		if(treeRoot == null)
			return 0;
		
		return Math.max(getDepth(treeRoot.getLeft()), getDepth(treeRoot.getRight()))+1;
		
	}
1
2
3
4
5
6
7
8

判断是否为平衡二叉树

ArrayList<User> avlUsers = new ArrayList<User>();
int l;//每次记录的是最后一次判断的子树的根
public boolean isAvl(User treeRoot){
		if(treeRoot == null)
			return true;
		if(Math.abs(getDepth(treeRoot.getLeft())-getDepth(treeRoot.getRight()))>1){
			avlUsers.add(treeRoot);//记录不平衡子树的根节点
			if(getDepth(treeRoot.getLeft())>getDepth(treeRoot.getRight()))
				l = 1;//左边子树高导致的不平衡
			else {
				l = 0;//右边子高导致的不平衡
			}
			return false;
		}
		else 
			return isAvl(treeRoot.getLeft())&&isAvl(treeRoot.getRight());//左右子树都平衡,这棵树才平衡
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

调节算法

public void toAVL(User user){
		
		User insertUser = user.getHead();
		User insertUserHead = insertUser.getHead();
		
		
		if(insertUserHead.getRight() == null || insertUserHead.getLeft()==null){//单转
			treeRoate(user, insertUser, insertUserHead);
			
		}else {
			User p = insertUserHead.getHead();
			int g = getDepth(avlUsers.get(avlUsers.size()-1));
			if (g<5) {
				if(insertUserHead == p.getLeft() && insertUser == insertUserHead.getRight()){//图二中的3，lr
					
					//先单转
					treeRoate(user, insertUser, insertUserHead);
					
					treeRoateLL(p.getLeft().getLeft(), p.getLeft());
				}
				
				else if(insertUserHead == p.getRight() && insertUser == insertUserHead.getLeft()){//图二中的4，rl
					//先单转
					treeRoate(user, insertUser, insertUserHead);
					
					treeRoateLL(p.getRight().getRight(), p.getRight());
				}
			}else//图二中的1，2情况，其余情况
				treeRoateLL(insertUser, insertUserHead);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

图一中情况处理

public void treeRoate(User user,User insertUser,User insertUserHead){
		if(user==insertUser.getRight()&&insertUser == insertUserHead.getRight()){//rr
			
			if(insertUserHead == root){
				insertUser.setHead(null);
				root = insertUser;
				insertUser.setLeft(insertUserHead);
				insertUserHead.setRight(null);
			}else {
				User p = insertUserHead.getHead();
				if(p.getLeft() == insertUserHead)
					p.setLeft(insertUser);
				else
					p.setRight(insertUser);
				insertUser.setLeft(insertUserHead);
				insertUserHead.setRight(null);
			}
		}
		else if(user==insertUser.getLeft()&&insertUser == insertUserHead.getLeft()){//ll
			if(insertUserHead == root){
				insertUser.setHead(null);
				root = insertUser;
				insertUser.setRight(insertUserHead);
				insertUserHead.setLeft(null);
			}else {
				User p = insertUserHead.getHead();
				if(p.getLeft() == insertUserHead)
					p.setLeft(insertUser);
				else
					p.setRight(insertUser);
				insertUser.setRight(insertUserHead);
				insertUserHead.setLeft(null);
			}
		}
		else if(user==insertUser.getLeft()&&insertUser == insertUserHead.getRight()){//lr
			if(insertUserHead == root){
				user.setRight(insertUserHead);
				user.setLeft(insertUser);
				user.setHead(null);
				insertUserHead.setLeft(null);
				insertUser.setRight(null);
				root = user;
			}else {
				User p = insertUserHead.getHead();
				if(p.getLeft() == insertUserHead)
					p.setLeft(user);
				else
					p.setRight(user);
				
				user.setRight(insertUserHead);
				user.setLeft(insertUser);
				insertUserHead.setLeft(null);
				insertUser.setRight(null);
				
			}
		}
		else if(user==insertUser.getRight()&&insertUser == insertUserHead.getLeft()){//rl
			if(insertUserHead == root){
				user.setLeft(insertUserHead);
				user.setRight(insertUser);
				user.setHead(null);
				insertUserHead.setRight(null);
				insertUser.setLeft(null);
				root = user;
			}else {
				User p = insertUserHead.getHead();
				if(p.getLeft() == insertUserHead)
					p.setLeft(user);
				else
					p.setRight(user);
				
				user.setLeft(insertUserHead);
				user.setRight(insertUser);
				insertUserHead.setRight(null);
				insertUser.setLeft(null);
				
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

其余情况和图二中的1,2情况处理

	public void treeRoateLL(User insertUser,User insertUserHead){
		
		User p = avlUsers.get(avlUsers.size()-1);
		User util;
		
		if(l == 0){//rr
			insertUserHead = p.getRight();
			//insertUser = insertUserHead.getRight();
			
			util = insertUserHead.getLeft();
			if(p == root){
				root = insertUserHead;
				insertUserHead.setLeft(p);
				insertUserHead.setHead(null);
				
				p.setRight(util);
			}else {
				
				User pHead = p.getHead();
				
				insertUserHead.setLeft(p);
				p.setRight(util);
				
				if(pHead.getLeft() == insertUserHead)
					pHead.setLeft(insertUserHead);
				else
					pHead.setRight(insertUserHead);
			}
		}
		else {//ll
			insertUserHead = p.getLeft();
			//insertUser = insertUserHead.getLeft();
			
			util = insertUserHead.getRight();
			if(p == root){
				root = insertUserHead;
				insertUserHead.setRight(p);
				insertUserHead.setHead(null);
				
				p.setLeft(util);
			}else {
				
				User pHead = p.getHead();
				
				insertUserHead.setRight(p);
				p.setLeft(util);
				
				if(pHead.getLeft() == insertUserHead)
					pHead.setLeft(insertUserHead);
				else
					pHead.setRight(insertUserHead);
			}
		}
		
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

总函数

public boolean addAVL(User friend) throws IllegalArgumentException {
		
		if(friend == null){
			throw new IllegalArgumentException();
		}
		
		else {
			this.beFriend(friend);
			
			//清空list结合
			avlUsers.clear();
			
			/*if(isAvl(root) == false)
				toAVL(friend);*/
			User p = root;
			
			//用while循环遍历,将树中所有不平衡子树的根节点存在list集合中
			while(isAvl(p) == false){
				isAvl(p);
				if(l==1)
					p = avlUsers.get(avlUsers.size()-1).getLeft();
				else {
					p = avlUsers.get(avlUsers.size()-1).getRight();
				}
			}
			//如果list集合中有元素,说明树不平衡
			if(avlUsers.size()>0)
				toAVL(friend);
			return true;
		}
		
		return false;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33