AVL二叉查找树

AVL二叉查找树是一种特殊的二叉查找树，其规定

每个节点的左子树和右子树的高度差最多是1

AVL调整算法

AVL树插入一个新的节点到某个节点下破坏AVL树的要求时，对于破坏条件的第一个节点a（最靠近底部/深度最深的节点），具有四种情况：

插入a的左儿子节点的左子树
插入a的左儿子节点的右子树
插入a的右儿子节点的左子树
插入a的右儿子节点的右子树

其中，第一种和第四种可以看成一种情况的镜像，均是插入外侧；第二种和第三种可以看成另一种情况的镜像，均是插入内侧。这两种情况分别对应两种不同调整方法——单旋转和双旋转。其核心思想都相同，都是尽量将违规子树的父节点的位置尽量向上提。

单旋转调整

考虑入下左图所示的情况，假设X与Z的深度相同且，整棵树符合AVL条件：

单旋转

若插入一个小于b的值，则X的深度将+1，从a节点来看，左子树的深度就比右子树大2，不符合条件。调整的方法如右图所示，以下是调整的合理性：

查找树条件：X子树存储的数据小于b，Z子树存储的数据大于a，Y子树存储的数据范围时(b,a)，且a>b，由此看出转换后的数依然是一颗查找树。
AVL条件：X深度比Z深1，但Z的位置要比X低1，因此a节点开始的树满足AVL条件。a树原来的深度为max{X+2,Y+2,Z+1}，现在a树的深度是max{X+1,Y+2,Z+2}。由于原树满足AVL条件，则Y的深度不会比原来X的深度深，所以深度分别为X1+2，X2+1，其中X2=X1+1，所以a节点深度不变，不影响上层AVL结构。

由此，只要将b提为树根，a放到b的右子树，再将Y挂到a的左子树就可以完成调整

待调整指针	调整前	调整后
树根指针	a	b
b左儿子（不变）	X	X
b右儿子	Y	a
a左儿子	b	Y
a右儿子（不变）	Z	Z

双旋转

考虑下左图情况

双旋转

设左图为一颗AVL树，X,Y的深度比W,Z浅1（X,Y深度相等，W,Z深度相等），假若在X或Y中插入一个节点，在a节点的AVL条件将不同，需要使用双旋转调整，调整成右图的样子，合理性如下：

查找树条件：对于W中的w，有w<b；对于X中的x，有b<x<c；对于Y中的y，有c<y<a；对于Z中的z，有z>a。且有b<c<a。在右侧数中以上均成立
AVL条件：c的子树深度为1+max{W,X}，右侧深度为1+max{Y,Z}，W,X,Y,Z中有三个相同，另一个比其他都要浅1，则a的AVL条件成立。双旋转处理后c树深度不变，因此不影响上层的AVL条件

调整情况如下

待调整指针	调整前	调整后
树根节点	a	c
a左儿子	b	Y
a右儿子（不变）	Z	Z
b左儿子（不变）	W	W
b右儿子	c	X
c左儿子	X	b
c右儿子	Y	a

同时，双旋转可以看成b-c和c-a之间的两次单旋转：

双旋转转单旋转

代码实现

结构体

type tree_data struct {
    data int
}

type tree_node struct {
    num    int
    height int
    data   tree_data
    parent *tree_node
    left   *tree_node
    right  *tree_node
}

构造函数

func New_tree_node(num int, data tree_data, parent *tree_node) *tree_node {
    node := tree_node{}
    node.num = num
    node.data = data
    node.height = 0
    node.left = nil
    node.right = nil
    node.parent = parent
    return &node
}

插入方法

func (t *tree_node) Insert(num int, data tree_data) {
    if num > t.num {
        if t.right != nil {
            t.right.Insert(num, data)
             //调整算法，向右子树插入，只能是右侧深度破坏条件
            if t.GetLenght(t.right) > t.GetLenght(t.left)+1 {
                if num > t.right.num {
                      //当待插入的数大于右侧标签，为插入右节点的右子树，单旋转
                    t.RightSimpleRotate()
                } else {
                      //当待插入的数小于右侧标签，为插入右节点的左子树，双旋转
                    t.RightDoubleRotate()
                }
            }
        } else {
             //新建节点不会导致条件破坏
            t.right = New_tree_node(num, data, t)
        }
    } else if num < t.num {
        if t.left != nil {
            t.left.Insert(num, data)
             //调整算法，向左子树插入，只能是左侧深度破坏条件
            if t.GetLenght(t.left) > t.GetLenght(t.right)+1 {
                if num < t.left.num {
                      //当待插入的数小于左侧标签，为插入左节点的左子树，单旋转
                    t.LeftSimpleRotate()
                } else {
                      //当待插入的数大于左侧标签，为插入左节点的右子树，双旋转
                    t.LeftDoubleRotate()
                }
            }
        } else {
             //新建节点不会导致条件破坏
            t.left = New_tree_node(num, data, t)
        }
    } else {
        t.data = data
    }
    t.compute_height()
}

单旋转方法

func (t *tree_node) LeftSimpleRotate() {
    if t.parent.left == t {
        t.parent.left = t.left
    } else {
        t.parent.right = t.left
    }
    temp := t.left.right
    t.left.right = t
    t.left.parent = t.parent

    t.parent = t.left
    t.left = temp
}

func (t *tree_node) RightSimpleRotate() {
    if t.parent.left == t {
        t.parent.left = t.right
    } else {
        t.parent.right = t.right
    }
    temp := t.right.left
    t.right.left = t
    t.right.parent = t.parent

    t.parent = t.right
    t.right = temp
}

双旋转

func (t *tree_node) LeftDoubleRotate() {
    t.left.RightSimpleRotate()
    t.LeftSimpleRotate()
}

func (t *tree_node) RightDoubleRotate() {
    t.right.LeftSimpleRotate()
    t.RightSimpleRotate()
}

其他方法

计算深度

func (t *tree_node) compute_height() {
    t.height = int(math.Max(float64(t.GetLenght(t.left)), float64(t.GetLenght(t.right)))) + 1
}

获得深度

func (t *tree_node) GetLenght(node *tree_node) int {
    if node == nil {
        return -1
    } else {
        return node.height
    }[图片上传中...(simple.png-2406ad-1514205437481-0)]

}

遍历

func (t *tree_node) Visit(indent string) {
    fmt.Println(indent, t.num, t.GetLenght(t.left), t.GetLenght(t.right))
    if t.left != nil {
        t.left.Visit(indent + "  ")
    }
    if t.right != nil {
        t.right.Visit(indent + "  ")
    }
}

AVL二叉树