AVL是什么？
AVL树又称平衡二叉树，它也是一颗二叉查找树，但在二叉查找树中，某个结点的左右子树高度之差的绝对值可能会超过1，称之为不平衡。而在平衡二叉树中，任何结点的左右子树高度之差的绝对值会小于等于 1。
AVL产生的意义？
在二叉查找树中最坏情况下查找某个元素的时间复杂度为O(n)，而AVL树能保证查找操作的时间复杂度总为O(logn)，如果在检索时这样的效率是有很大的改进的，所以基于此类效率的数据结构会有更大的应用空间。
对于一棵BST树而言，不仅有查找操作，也有插入、删除等改变树的形态的操作。随着不断地插入、删除，BST树有可能会退化成链表的形式（在二叉树基础中的斜二叉树就是极端情况的BST），使得查找的时间复杂度变成O(N)，这种情形下，BST树的结构非常不平衡了。为了保持树的平衡，需要对树的形态做一些限制，因此，引入了AVL树，以保证树的左右子树高度之差的绝对值小于等于1。
AVL通过什么样的操作才可以保持较高的效率？
旋转
何种情况下该如何旋转？
插入、删除
旋转的四种类型，解决所有问题
在旋转是要注意旋转节点和其子节点的左右重新连接。
2.1、左左旋转（LL型）
如图，造成A节点的高度差>1的节点为子树为左子节点和左子节点的左子节点，则为LL型，LL型为顺时针旋转。
如图2-1所示，此时A节点的左树与右树的高度差为2，与AVL的定义不符，此时以B节点为轴心，AB间连线为转轴，将A节点旋转至B节点下方，由B节点的父节点变成子节点。实现所有节点的左右子树高度差小于等于1。如图2-2。
2.2、右右旋转
如图，造成A节点的高度差>1的节点为子树为右子节点和右子节点的右子节点，则为RR型，RR型为逆时针旋转。
右右旋转与左左旋转类似，但是动作相反，如图2-3，2-4所示，以B节点为轴心，BC间连线为轴，将C节点旋转至B下方，成为B的子节点。实现所有节点的左右子树高度差小于等于1。
2.3、左右旋转
如图，造成A节点的高度差>1的节点为子树为右子节点和右子节点的右子节点，则LR型，LR型为先逆时针旋转，后顺时针旋转。
左右旋转稍复杂一点，需要旋转两次，如果用左左旋转的方式直接旋转图2-5中的树，会变成图2-8的样子，此时B节点的左右子树高度差依然没有平衡，所以要先对2-5的树做一步处理，就是以BC为轴，
将C节点旋转至B节点的位置，如图2-6所示，此时就将树转换成了左左旋转的场景，之后使用左左旋转即可完成平衡。
2.4、右左旋转
右左旋转与左右旋转类似，也是旋转两次，先顺时针旋转，后逆时针旋转。
旋转的代码是啥？
mport java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;
public class AVLTree {
//根节点
private Node root;
/**
* 添加节点
* @param item
*/
public void add(int item){
if(root == null)
root = new Node(item);
else{
Node parent = root;
Node temp = root;
do{
parent = temp;
if(item < parent.getValue()){
temp = parent.getLeft();
}else if(item > parent.getValue()){
temp = parent.getRight();
}else{
break;
}
}while(temp != null);
if(temp != null){
temp.setValue(item);
}else{
Node node = new Node(item);
node.setParent(parent);
if(item < parent.getValue()){
parent.setLeft(node);
if(parent.getRight() == null)
balance(node);
else
parent.subAVL();
}else{
parent.setRight(node);
if(parent.getLeft() == null)
balance(node);
else
parent.addAVL();
}
}
}
}
/**
* 增加节点时修改节点平衡值，对不平衡的子树进行调整
* 依次向上遍历，修改父节点的平衡因子，直到出现最小不平衡节点
* @param node
*/
private void balance(Node node){
Node parent = node.getParent();
Node node_middle = node;
Node node_prev = node;
Boolean avl = true;
do{
if(node_middle == parent.getLeft() && (-1 <= parent.getAVL()-1 && parent.getAVL()-1 <= 1)){
parent.subAVL();
node_prev = node_middle;
node_middle = parent;
if(parent != null && parent.getAVL() == 0)
parent = null;
else
parent = parent.getParent();
}else if(node_middle == parent.getRight() && (-1 <= parent.getAVL()+1 && parent.getAVL()+1 <= 1)){
parent.addAVL();
node_prev = node_middle;
node_middle = parent;
if(parent != null && parent.getAVL() == 0)
parent = null;
else
parent = parent.getParent();
}else{//出现最小不平衡节点，新增时不需要考虑更高节点，所以直接中断循环，调用平衡方法
avl = false;
}
}while(parent != null && avl);
if(parent == null){
return;
}
chooseCalculation(parent, node_middle, node_prev);
}
/**
* 选择合适的转换规则，返回变更的高度值（删除平衡时会用到）。
* @param parent
* @param node_middle
* @param node_prev
*/
private int chooseCalculation(Node parent, Node node_middle, Node node_prev) {
//变更的高度值
int height = 0;
if(node_middle == parent.getLeft() && node_prev == node_middle.getLeft()){
if(node_middle.getAVL() == -1)
height = -1;
LeftLeftRotate(node_middle);
}else if(node_middle == parent.getLeft() && node_prev == node_middle.getRight()){
height = -1;
LeftRightRotate(node_middle);
}else if(node_middle == parent.getRight() && node_prev == node_middle.getLeft()){
height = -1;
RightLeftRotate(node_middle);
}else if(node_middle == parent.getRight() && node_prev == node_middle.getRight()){
if(node_middle.getAVL() == 1)
height = -1;
RightRightRotate(node_middle);
}
return height;
}
/**
* 查询节点
* @param item
* @return
*/
public Node get(int item){
if(root == null)
return null;
if(item == root.getValue()){
return root;
}else{
Node node = root;
do{
if(item < node.getValue()){
node = node.getLeft();
}else if(item > node.getValue()){
node = node.getRight();
}else{
return node;
}
}while(node != null);
}
return null;
}
/**
* 获取树的高度
* @return
*/
public int treeLength(){
return getLength(root);
}
/**
* 获取node到树底的高度
* @param node
* @return
*/
private int getLength(Node node){
if(node == null)
return 0;
int num = 1;
List<Node> l = new ArrayList<Node>();
l.add(node);
num = itrableNode(num, l);
return num;
}
private int itrableNode(int num, List<Node> list){
List<Node> newlist = new ArrayList<Node>();
list.forEach(new Consumer<Node>() {
@Override
public void accept(Node t) {
if(t.getLeft() != null){
newlist.add(t.getLeft());
}
if(t.getRight() != null){
newlist.add(t.getRight());
}
}
});
if(newlist.size() > 0){
num += 1;
num = itrableNode(num,newlist);
}
return num;
}
/**
* 打印树形图(仅限10到99的正整数组成的树，否则排版会有问题)，测试用方法
*/
public void printByPhoto(){
if(root == null){
return;
}
int length = treeLength();
int blank = countoutBlank(length, 1);
List<Node> l = new ArrayList<Node>();
l.add(root);
printRow(length,blank,1,l);
}
/**
* 计算每行的空格数
* @param length
* @param row
* @return
*/
private int countoutBlank(int length, int row){
int half = (int)Math.pow(2, length-1-row);
int blank = 0;
if(length == 2){
blank = 2;
}else if(length > 2){
if(half == 2){
blank = 6;
}else{
blank = (int) (Math.pow(2, length-2-row) * 6 + (Math.pow(2, length - 2-row) - 1) * 2);
}
}else{
blank = 0;
}
return blank;
}
/**
* 绘制行
* @param length
* @param blank
* @param row
* @param list
*/
private void printRow(int length, int blank, int row, List<Node> list){
for(int n = 0; n < blank; n++){
System.out.print(" ");
}
StringBuffer x = new StringBuffer();
for(int n = 0; n < blank*2; n++){
x.append(" ");
}
x.append(" ");
StringBuffer y = new StringBuffer();
for(int n = 0; n < blank*2; n++){
y.append(" ");
}
y.append(" ");
List<Node> newlist = new ArrayList<Node>();
if(row == 1){
System.out.print(root.getValue());
System.out.println("");
printRow(length,countoutBlank(length, row+1),row+1,list);
}else{
for(Node t : list){
if(t.getLeft() != null){
newlist.add(t.getLeft());
System.out.print(t.getLeft().getValue()+x.toString());
}else if(t.getValue() != 0 || row <= length){
newlist.add(new Node(0));
System.out.print("x "+x.toString());
}
if(t.getRight() != null){
newlist.add(t.getRight());
System.out.print(t.getRight().getValue()+y.toString());
}else if(t.getValue() != 0 || row <= length){
newlist.add(new Node(0));
System.out.print("x "+y.toString());
}
}
System.out.println("");
if(newlist.size() > 0)
printRow(length,countoutBlank(length, row+1),row+1,newlist);
}
}
/**
* 左左旋转
* @param node
*/
private void LeftLeftRotate(Node node){
Node parent = node.getParent();
if(parent.getParent() != null && parent == parent.getParent().getLeft()){
node.setParent(parent.getParent());
parent.getParent().setLeft(node);
}else if(parent.getParent() != null && parent == parent.getParent().getRight()){
node.setParent(parent.getParent());
parent.getParent().setRight(node);
}else{
root = node;
node.setParent(null);
}
parent.setParent(node);
parent.setLeft(node.getRight());
if(node.getRight() != null)
node.getRight().setParent(parent);
node.setRight(parent);
if(node.getAVL() == -1){//只有左节点时，parent转换后没有子节点
parent.setAVL(0);
node.setAVL(0);
}else if(node.getAVL() == 0){//node有两个子节点，转换后parent有一个左节点
parent.setAVL(-1);
node.setAVL(1);
}//node.getAVL()为1时会调用左右旋转
}
/**
* 右右旋转
* @param node
*/
private void RightRightRotate(Node node){
Node parent = node.getParent();
if(parent.getParent() != null && parent == parent.getParent().getLeft()){
node.setParent(parent.getParent());
parent.getParent().setLeft(node);
}else if(parent.getParent() != null && parent == parent.getParent().getRight()){
node.setParent(parent.getParent());
parent.getParent().setRight(node);
}else{
root = node;
node.setParent(null);
}
parent.setParent(node);
parent.setRight(node.getLeft());
if(node.getLeft() != null)
node.getLeft().setParent(parent);
node.setLeft(parent);
if(node.getAVL() == 1){
node.setAVL(0);
parent.setAVL(0);
}else if(node.getAVL() == 0){//当node有两个节点时，转换后层数不会更改，左树比右树高1层，parent的右树比左树高一层
parent.setAVL(1);
node.setAVL(-1);
}
}
/**
* 左右旋转
* @param node
*/
private void LeftRightRotate(Node node){
Node parent = node.getParent();
Node child = node.getRight();
//左右旋转时node的avl必为1，所以只需考虑child的avl
if(!child.hasChild()){
node.setAVL(0);
parent.setAVL(0);
}else if(child.getAVL() == -1){
node.setAVL(0);
parent.setAVL(1);
}else if(child.getAVL() == 1){
node.setAVL(-1);
parent.setAVL(0);
}else if(child.getAVL() == 0){
node.setAVL(0);
parent.setAVL(0);
}
child.setAVL(0);
//第一次交换
parent.setLeft(child);
node.setParent(child);
node.setRight(child.getLeft());
if(child.getLeft() != null)
child.getLeft().setParent(node);
child.setLeft(node);
child.setParent(parent);
//第二次交换
if(parent.getParent() != null && parent == parent.getParent().getLeft()){
child.setParent(parent.getParent());
parent.getParent().setLeft(child);
}else if(parent.getParent() != null && parent == parent.getParent().getRight()){
child.setParent(parent.getParent());
parent.getParent().setRight(child);
}else{
root = child;
child.setParent(null);
}
parent.setParent(child);
parent.setLeft(child.getRight());
if(child.getRight() != null)
child.getRight().setParent(parent);
child.setRight(parent);
}
/**
* 右左旋转
* @param node
*/
private void RightLeftRotate(Node node){
Node parent = node.getParent();
Node child = node.getLeft();
if(!child.hasChild()){
node.setAVL(0);
parent.setAVL(0);
}else if(child.getAVL() == -1){
node.setAVL(1);
parent.setAVL(0);
}else if(child.getAVL() == 1){
node.setAVL(0);
parent.setAVL(-1);
}else if(child.getAVL() == 0){
parent.setAVL(0);
node.setAVL(0);
}
child.setAVL(0);
//第一次交换
parent.setRight(child);
node.setParent(child);
node.setLeft(child.getRight());
if(child.getRight() != null)
child.getRight().setParent(node);
child.setRight(node);
child.setParent(parent);
//第二次交换
if(parent.getParent() != null && parent == parent.getParent().getLeft()){
child.setParent(parent.getParent());
parent.getParent().setLeft(child);
}else if(parent.getParent() != null && parent == parent.getParent().getRight()){
child.setParent(parent.getParent());
parent.getParent().setRight(child);
}else{
root = child;
child.setParent(null);
}
parent.setParent(child);
parent.setRight(child.getLeft());
if(child.getLeft() != null)
child.getLeft().setParent(parent);
child.setLeft(parent);
}
/**
* 删除节点
* @param item
*/
public void deleteNode(int item){
Node node = get(item);
if(node == null)
return;
Node parent = node.getParent();
if(!node.hasChild()){//叶子节点
if(parent == null){//删除最后节点
root = null;
return;
}
if(node.hasBrother()){//node有兄弟节点时，需要判断是否需要调用平衡方法
if(node == parent.getLeft())
isBalance(node, 1);
else
isBalance(node, -1);
parent.deleteChildNode(node);
}else{//node没有兄弟节点时，高度减一，需要进行平衡
deleteAvl(node);
parent.deleteChildNode(node);
}
}else if(node.getLeft() != null && node.getRight() == null){//有一个子节点时，将子节点上移一位，然后进行平衡即可
if(parent == null){//删除的是跟节点
root = node;
return;
}
if(node == parent.getLeft()){
parent.setLeft(node.getLeft());
}else{
parent.setRight(node.getLeft());
}
node.getLeft().setParent(parent);
deleteAvl(node.getLeft());
}else if(node.getLeft() == null && node.getRight() != null){//有一个子节点时，将子节点上移一位，然后进行平衡即可
if(parent == null){//删除的是跟节点
root = node;
return;
}
if(node == parent.getRight()){
parent.setRight(node.getRight());
}else{
parent.setLeft(node.getRight());
}
node.getRight().setParent(parent);
deleteAvl(node.getRight());
}
else{//有两个子节点时，先在节点左树寻找最大节点last，然后删除last，最后将被删除节点的value替换为last的value
Node last = findLastNode(node);
int tmp = last.getValue();
deleteNode(last.getValue());
node.setValue(tmp);
}
node = null;//GC
}
/**
* 判断是否需要平衡
* @param node
* @param avl
*/
private void isBalance(Node node, int avl){
Node parent = node.getParent();
if(avl == 1){
if(parent.getAVL() + 1 > 1){
deleteAvl(node);
}else{
parent.addAVL();
}
}else if(avl == -1){
if(parent.getAVL() - 1 < -1){
deleteAvl(node);
}else{
parent.subAVL();
}
}
}
/**
* 搜索node节点左树的最大节点，用于替换被删除节点
* @param n
* @return
*/
private Node findLastNode(Node n){
Node last = null;
Node node = n.getLeft();
if(node != null){
do{
last = node;
node = node.getRight();
}while(node != null);
}
return last;
}
/**
* 删除时平衡上级节点
* @param node
*/
private void deleteAvl(Node node){
Node node_middle = node;
Node parent = node_middle.getParent();
Node node_prev = node_middle;
boolean avl = true;
do{
node_prev = node_middle;
if(node_middle == parent.getLeft() && (parent.getAVL() + 1 <= 1)){
if(parent.getAVL() == 0){
parent.addAVL();
return;
}
parent.addAVL();
node_middle = parent;
parent = node_middle.getParent();
}else if(node_middle == parent.getRight() && (parent.getAVL() - 1 >= -1)){
if(parent.getAVL() == 0){
parent.subAVL();
return;
}
parent.subAVL();
node_middle = parent;
parent = node_middle.getParent();
}else{
//由于删除时有可能进行多次平衡，所以不直接使用node_middle的值，防止影响之后的循环
Node middle = node_middle.getBrother();
Node child = middle.getAVL() == -1 ? middle.getLeft() : (middle.getAVL() == 1 ? middle.getRight() : (parent.getAVL() == -1 ? middle.getLeft() : middle.getRight()));
int height = chooseCalculation(parent, middle, child);
if(height == 0)
return;
node_middle = parent.getParent();
parent = node_middle.getParent();
}
}while(parent != null && avl);
}
}
辅助代码
public class Node {
private Node parent;
private Node left;
private Node right;
private int item;
private int avl;
public Node(int item) {
this.item = item;
this.avl = 0;
}
public int getValue(){
return item;
}
public Node getLeft(){
return left;
}
public Node getRight(){
return right;
}
public Node getParent(){
return parent;
}
public void setValue(int item){
this.item = item;
}
public void setParent(Node parent){
this.parent = parent;
}
public void setLeft(Node item){
this.left = item;
}
public void setRight(Node item){
this.right = item;
}
public int getAVL(){
return avl;
}
public void setAVL(int avl){
this.avl = avl;
}
public int subAVL(){
avl -= 1;
return avl;
}
public int addAVL(){
avl += 1;
return avl;
}
@Override
public String toString() {
return String.valueOf(item);
}
public boolean hasBrother(){
if(parent == null)
return false;
else if(this == parent.getLeft() && parent.getRight() != null)
return true;
else if(this == parent.getRight() && parent.getLeft() != null)
return true;
else
return false;
}
public boolean hasChild(){
if(left != null || right != null)
return true;
else
return false;
}
public Node getBrother(){
if(parent == null)
return null;
else if(this == parent.getLeft())
return parent.getRight();
else
return parent.getLeft();
}
public void deleteChildNode(Node child){
if(child == null)
return;
else if(child == left)
left = null;
else if(child == right)
right = null;
}
}
网友评论