venps

平衡条件

1. 对α的左儿子的左子树进行一次插入
2. 对α的左儿子的右子树进行一次插入
3. 对α的右儿子的左子树进行一次插入
4. 对α的右儿子的右子树进行一次插入

1和4，2和3 是关于α点的镜像对称。因此理论上讲只有两种情况，当然编程上还是四种情况。

scala实现

``````sealed trait AVLTree[+A] extends Serializable {
def balance: Int

def depth: Int

def contains[B >: A](x: B)(implicit ordering: Ordering[B]): Boolean

def insert[B >: A](x: B)(implicit ordering: Ordering[B]): AVLTree[B]

def rebalance[B >: A]: AVLTree[B]

}

/**
* 叶子节点
*/
case object Leaf extends AVLTree[Nothing] {

override val balance: Int = -1
override val depth: Int = 0

override def contains[B >: Nothing](x: B)(implicit ordering: Ordering[B]): Boolean = false

override def insert[B >: Nothing](x: B)(implicit ordering: Ordering[B]): AVLTree[B] = {
Node(x, Leaf, Leaf)
}

override def rebalance[B >: Nothing]: AVLTree[B] = this

}

case class Node[A](value: A, left: AVLTree[A], right: AVLTree[A]) extends AVLTree[A] {
override def balance: Int = right.depth - left.depth

override def depth: Int = math.max(left.depth, right.depth)

override def contains[B >: A](x: B)(implicit ordering: Ordering[B]): Boolean = ???

override def insert[B >: A](x: B)(implicit ordering: Ordering[B]): AVLTree[B] = {
val cmp = ordering.compare(x,value)
if (cmp < 0){
Node(value, left.insert(x),right).rebalance
} else if (cmp > 0){
Node(value, left, right.insert(x)).rebalance
} else {
this
}
}

override def rebalance[B >: A]  = {
if (-2 == balance){
if (1 == left.balance){
doubleRightRotation
} else {
rightRotation
}
} else if(2 == balance) {
if (-1 == right.balance){
doubleLeftRotation
}else {
leftRotation
}
} else {
this
}
}

/*
*   5
*    \                                  6
*     6       ---- 左单旋转 --->        /  \
*      \                              5   7
*       7
*
*   在节点5 发生不平衡 5的右节点成为新的根节点
*/
private def leftRotation[B >: A] = {
if (Leaf != right) {
val r = right.asInstanceOf[Node[A]]
Node(r.value, Node(value, left, r.left), r.right)
} else {
sys.error("should not happen.")
}
}

/*
*           7
*          /                                6
*         6    ---- 右单旋转 --->           /  \
*        /                                5   7
*       5
*
*    在节点7 发生不平衡 7的左节点成为新的根节点
*/
private def rightRotation[B >: A] = {
if (Leaf != left) {
val l = left.asInstanceOf[Node[A]]
Node(l.value, l.left, Node(value, l.right, right))
} else {
sys.error("should not happen.")
}

}

/*
*     左双旋转
*
*     5                           5
*       \                          \                     6
*        7    ----step1 --->        6    ---step2--->   / \
*       /                            \                 5   7
*      6                              7
*
*  在节点5处不平衡
*  step1 : 节点5的右节点 做一次 右旋转
*  step2 : 左旋转
*
*/
private def doubleLeftRotation[B >: A] = {
if (Leaf != right) {
val r = right.asInstanceOf[Node[A]]
val rightRotated = r.rightRotation
Node(rightRotated.value, Node(value, left, rightRotated.left), rightRotated.right)
} else {
sys.error("should not happen.")
}
}

/*
*   右双旋转
*
*     7                            7
*    /                            /                   6
*   5       ----step1 --->       6    ---step2--->   / \
*    \                          /                   5   7
*     6                        5
*
*  在节点7处不平衡
*  step1 : 节点7的左节点 做一次 左旋转
*  step2 : 右旋转
*
*/
private def doubleRightRotation[B >: A] = {
if (Leaf != left) {
val l: Node[A] = left.asInstanceOf[Node[A]]
val leftRotated = l.leftRotation
Node(leftRotated.value, leftRotated.left, Node(value, leftRotated.right, right))
} else sys.error("Should not happen.")
}

}

``````

参考资料

《数据结构与算法分析java语言描述》 AVL tree (维基百科)

评论(8)

引用来自“Neo”的评论

avl维持平衡，可能需要经过多次旋转，但是rbtree只需要最多经过3次旋转——我听说的

引用来自“venps”的评论

AVL是高度平衡的二叉树，维护这种高度平衡的代价相对较大，一般是用追求局部而不是非常严格整体平衡的红黑树来替代。红黑树的应用比较多，比如 java中的TreeMap和TreeSet。

引用来自“行意天下”的评论

AVL是高度平衡的二叉树，维护这种高度平衡的代价相对较大，一般是用追求局部而不是非常严格整体平衡的红黑树来替代。红黑树的应用比较多，比如 java中的TreeMap和TreeSet。

2017/01/17
0
0
AVL树旋转操作的C++实现(转载)

AVL树的介绍AVL树是高度平衡的而二叉树。它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。 AVL树的C++实现 AVL树节点 旋转 如果在AVL树中进行插入或者删除节点，可能导致AVL树失去...

osc_gjsta20x
2019/07/12
1
0
AVL树与红黑树（R-B树）的区别与联系

osc_sd6j22mg
2018/07/03
6
0
AVL树和伸展树 -数据结构（C语言实现）

osc_xk1o4tx1
2018/09/08
2
0

cut
2012/11/10
496
7

windows下安装M2Crypto

A_laoshiren
56分钟前
14
0

56分钟前
12
0
vue源码---将data对象中的属性变成observable

function defineReactive(obj, key, val, cb) { Object.defineProperty(obj, key, { enumerable: true, configurable: true, get: () => { re......

gtandsn
58分钟前
11
0

28
0