前文介绍了,二叉树、二叉排序树,需要了解的不妨关注下小JIA。
AVL是一种高度平衡的二叉排序树。对于任意节点左子树与右子树高度差不超过1,AVL的高度与节点数量为O(logn)关系。平衡因子等于左子树高度减去右子树高度。AVL所有节点的平衡因子只可能是-1、0、1。因此当添加元素或删除元素时有可能会破会这种平衡,所以需要维护。失去平衡主要有四种情况,分别为LL、LR、RR和RL。
public class AVLTreeNode<T extends Comparable<T>> { private T key; //关键字(键值) private int height; //高度 private AVLTreeNode<T> left; //左孩子 private AVLTreeNode<T> right; //右孩子 public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) { this.key = key; this.left = left; this.right = right; this.height = 0; } ...... }
LL,平衡因子大于1,左子树平衡因子大于等于0,需要将A顺时针向下右旋转,B做为父节点
右旋转操作,首先保存B右子树K3,将A做为B的右子树,K3做为A的左孩子,并更新A,B的高度值,完成旋转。
/* LL:左旋转 */ private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> node) { AVLTreeNode<T> tempNode; tempNode = node.getLeft(); node.setLeft(tempNode.getRight()); tempNode.setRight(node); node.setHeight(max(height(node.getLeft()), height(node.getRight())) + 1); tempNode.setHeight(max(height(tempNode.getLeft()), node.getHeight()) + 1); return tempNode; }
RR,平衡因子小于-1,右子树平衡因子小于等于0,需要将A逆时针向下左旋转,B做为父节点
左旋转操作,首先保存B左子树K2,将A做为B的左子树,K2做为B的右孩子,并更新A、B的高度值,完成旋转
/* RR:右旋转 */ private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> node) { AVLTreeNode<T> tempNode; tempNode = node.getRight(); node.setRight(tempNode.getLeft()); tempNode.setLeft(node); node.setHeight(max( height(node), height(node.getRight())) + 1); tempNode.setHeight(max( height(tempNode.getRight()), node.getHeight()) + 1); return tempNode; }
LR,平衡因子大于1,左子树平衡因子小于0,首先将B进行左旋转,在将A进行右旋转
/* LR:左双旋转 */ private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> node) { node.setLeft(rightRightRotation(node.getLeft())); return leftLeftRotation(node); }
RL,平衡因子大于-1,右子树平衡因子大于0,首先将B进行右旋转,在将A进行左旋转
/* RL:右双旋转 */ private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> node) { node.setRight(leftLeftRotation(node.getRight())); return rightRightRotation(node); }
原则:根据二叉查找树BST的规定插入数据,再来判断是否失去平衡;若失去平衡再根据文上介绍的旋转规则平衡数据;最后再设置树高。
/* 将结点插入到AVL树中 */ private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) { if (tree == null) { //新建节点 tree = new AVLTreeNode<T>(key, null, null); } else { int cmp = key.compareTo(tree.getKey()); if (cmp < 0) { //将key插入到tree的左子树 tree.setLeft(insert(tree.getLeft(), key)); //插入节点后,若AVL树失去平衡,则进行相应的调节。 if (height(tree.getLeft()) - height(tree.getRight()) > 1) { if (key.compareTo(tree.getLeft().getKey()) < 0) tree = leftLeftRotation(tree); else tree = leftRightRotation(tree); } } else if (cmp > 0) {//将key插入到tree的右子树 tree.setRight(insert(tree.getRight(), key)); //插入节点后,若AVL树失去平衡,则进行相应的调节。 if (height(tree.getRight()) - height(tree.getLeft()) > 1) { if (key.compareTo(tree.getRight().getKey()) > 0) tree = rightRightRotation(tree); else tree = rightLeftRotation(tree); } } } tree.setHeight(max(height(tree.getLeft()), height(tree.getRight())) + 1); return tree; }
同理,先找到删除节点的位置,再进行AVL平衡调节。找到要删除的节点Z后,如果Z的左右孩子都非空,
a)若Z的左子树高于右子树,找出左子树中的最大节点K(maxNum方法),使用K的值替换掉Z的值,并删除K;
b)若Z的左子树矮于或等于右子树,找出右子树中最小节点K(minNum方法),使用K的值替换掉Z的值,并删除K。
这种方式的好处是删除后AVL树仍然是平衡的。
/* 删除结点 */ private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> delNode) { //根为空 或者 没有要删除的节点,直接返回null。 if (tree == null || delNode == null) return null; int cmp = delNode.getKey().compareTo(tree.getKey()); if (cmp < 0) { //待删除的节点在tree的左子树中 tree.setLeft(remove(tree.getLeft(), delNode)); // 删除节点后,若AVL树失去平衡,则进行相应的调节。 if (height(tree.getRight()) - height(tree.getLeft()) > 1) { AVLTreeNode<T> r = tree.getRight(); if (height(r.getLeft()) > height(r.getRight())) tree = rightLeftRotation(tree); else tree = rightRightRotation(tree); } } else if (cmp > 0) { //待删除的节点在tree的右子树中 tree.setRight(remove(tree.getRight(), delNode)); // 删除节点后,若AVL树失去平衡,则进行相应的调节。 if (height(tree.getLeft()) - height(tree.getRight()) > 1) { AVLTreeNode<T> l = tree.getLeft(); if (height(l.getRight()) > height(l.getLeft())) tree = leftRightRotation(tree); else tree = leftLeftRotation(tree); } } else { // tree是对应要删除的节点。 // tree的左右孩子都非空 if ((tree.getLeft() != null) && (tree.getRight() != null)) { //如果tree的左子树比右子树高; if (height(tree.getLeft()) > height(tree.getRight())) { AVLTreeNode<T> max = maxNum(tree.getLeft()); tree.setKey(max.getKey()); tree.setLeft(remove(tree.getLeft(), max)); //如果tree的左子树矮于或等于右子树 } else { AVLTreeNode<T> min = minNum(tree.getRight()); tree.setKey(min.getKey()); tree.setRight(remove(tree.getRight(), min)); } } else { AVLTreeNode<T> tmpNode = tree; tree = (tree.getLeft() != null) ? tree.getLeft() : tree.getRight(); tmpNode = null; } } return tree; }