AVL树-scala实现
AVL树-scala实现
venps 发表于2年前
AVL树-scala实现
• 发表于 2年前
• 阅读 2976
• 收藏 59
• 评论 8

# 平衡条件

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 (维基百科)

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

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

#### 引用来自“venps”的评论

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

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

×