|
平衡二叉树
平衡二叉树又叫平衡二叉搜索树，可以保证查询效率较高。 特点一棵树它左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
右旋转
构建二叉查找树：  构成的二叉树的形状：   此时，左右子树高度差为为2，根节点值为10  这时二叉树：左子树高度-右子树的高度=2 不满足平衡二叉树，为了让二叉树成为平衡二叉树就需要进行右旋转降低左子树的高度，增加右子树的深度。 右旋转的步骤：（紫色为当前结点，红色为新结点） 
//右旋转方法
private void rightRotate(){
//创建新的结点，给新结点赋值当前结点的值
Node newNode=new Node(this.value);
//把新节点的右子树设置当前结点的右子树
newNode.right=this.right;
//把新节点的左子树设置为当前结点的左子树的右子树
newNode.left=this.left.right;
//把当前结点的值换位当前结点的左子结点的值
this.value=this.left.value;
//把当前结点的左子树设置成为左子树的左子树
this.left=this.left.left;
//把当前结点的右子树设置为新结点
this.right=newNode;
}
执行右旋转完后，左右子树高度差为为0，根节点值为8，满足平衡二叉树 
左旋转
构建二叉查找树：  构成的二叉树的形状：   此时，左右子树高度差为为2，根节点值为4  这时二叉树：右子树高度-左子树的高度=2 不满足平衡二叉树，为了让二叉树成为平衡二叉树就需要进行左旋转降低右子树的高度，增加左子树的深度。 左旋转的步骤：（紫色为当前结点，红色为新结点） 
//左旋转方法
private void leftRotate(){
//创建新的结点，给新结点赋值当前节点的值
Node newNode=new Node(this.value);
//把新的结点的左子树设置成当前结点的左子树
newNode.left=this.left;
//把新的结点的右子树设置为当前结点的右子树的左子树
newNode.right=this.right.left;
//把当前护额短板的值替为右子节点的值
this.value=this.right.value;
//把当前结点的右子树设置成右子树的右子树
this.right=this.right.right;
//把当前结点的左子树设置为新的结点
this.left=newNode;
}
执行左旋转完后，左右子树高度差为为0，根节点值为6，满足平衡二叉树 
双旋转
拿数据为例  此时构建的二叉查找树还会有这种情况  此时二叉树满足右旋转，旋转完后，二叉树左右子树高度差还是大于1  就要用到双旋转，什么条件执行双旋转呢，拿开始为右旋转为例当 (左子树的高度 - 右子树的高度) > 1并且它的左子树的右子树高度大于它的左子树的高度，就先对当前结点的左结点(左子树)->左旋转，再对当前结点进行右旋转，反之开始为左旋转。  执行双旋转完后，左右子树高度差为为0，根节点值为8，满足平衡二叉树 
代码汇总
package avl;
public class AVLTreeDemo {
public static void main(String[] args) {
//int[] arr={10,12,8,9,7,6};
//int[] arr = {4,3,6,5,7,8};
int[] arr = { 10, 11, 7, 6, 8, 9 };
AVLTree avlTree=new AVLTree();
for (int i=0;i
private Node root;
public Node getRoot(){
return root;
}
//添加结点
public void add(Node node){
//如果root为空则直接让root指向node
if(root==null){
root=node;
}else{
root.add(node);
}
}
}
class Node{
int value;
Node left;
Node right;
public Node(int value){
this.value =value;
}
// 返回左子树的高度
public int leftHeight(){
if(left==null){
return 0;
}
return left.height();
}
// 返回右子树的高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}
//返回以该结点为根节点的树的高度
public int height(){
return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;
}
//左旋转方法
private void leftRotate(){
//创建新的结点，给新结点赋值当前节点的值
Node newNode=new Node(this.value);
//把新的结点的左子树设置成当前结点的左子树
newNode.left=this.left;
//把新的结点的右子树设置为当前结点的右子树的左子树
newNode.right=this.right.left;
//把当前护额短板的值替为右子节点的值
this.value=this.right.value;
//把当前结点的右子树设置成右子树的右子树
this.right=this.right.right;
//把当前结点的左子树设置为新的结点
this.left=newNode;
}
//右旋转方法
private void rightRotate(){
//创建新的结点，给新结点赋值当前节点的值
Node newNode=new Node(this.value);
//把新节点的右子树设置当前结点的右子树
newNode.right=this.right;
//把新节点的左子树设置为当前结点的左子树的右子树
newNode.left=this.left.right;
//把当前结点的值换位当前结点的左子结点的值
this.value=this.left.value;
//把当前结点的左子树设置成为左子树的左子树
this.left=this.left.left;
//把当前结点的右子树设置为新结点
this.right=newNode;
}
public void add(Node node){
if(node==null){
return;
}
//判断传入的结点的值，和当前子树的根节点的值关系
if(node.value
this.left=node;
}else{
//递归 向左子树添加
this.left.add(node);
}
}else{
// 添加的结点的值大于 当前结点的值
if (this.right == null) {
this.right = node;
} else {
// 递归的向右子树添加
this.right.add(node);
}
}
//当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
if(rightHeight() - leftHeight() > 1) {
//如果它的右子树的左子树的高度大于它的右子树的右子树的高度
if(right != null && right.leftHeight() > right.rightHeight()) {
//先对右子结点进行右旋转
right.rightRotate();
//然后在对当前结点进行左旋转
leftRotate(); //左旋转..
} else {
//直接进行左旋转即可
leftRotate();
}
return ; //必须要!!!
}
//当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
if(leftHeight() - rightHeight() > 1) {
//如果它的左子树的右子树高度大于它的左子树的高度
if(left != null && left.rightHeight() > left.leftHeight()) {
//先对当前结点的左结点(左子树)->左旋转
left.leftRotate();
//再对当前结点进行右旋转
rightRotate();
} else {
//直接进行右旋转即可
rightRotate();
}
}
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
}
|