AVL（self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree）树定义可以自行百度。

AVL树的相关数据结构定义

节点的定义

// 数据接口
type Value interface {
    Less(v interface{}) bool  // 用户确认数据的排序规则
}
// 平衡二叉树的节点
type Node struct {
    l, r  *Node  // 左右孩子节点
    bf    int8    // 平衡因子，左树高-右树高
    value Value  // 节点值
}

AVL树的定义

type Tree struct {
    head *Node  // 树的数据
}

AVL树的相关数据操作

数据添加

AVL树的数据添加在叶子节点上进行，数据的添加会造成双亲节点平衡因子的改变，可能造成双亲节点树高的改变，这种树高的改变会从添加节点的位置沿着双亲节点往上冒泡到平衡因子（bf）改变而树高不改变的节点。
数据的添加可能会造成所属树的不平衡，当存在最小不平衡树的时候可以通过旋转最小不平衡树，解决不平衡的问题。旋转可能会改变树高。
树的旋转：树的旋转分为左旋（逆时针），右旋（顺时针），旋转的目的是让不平衡的树变的平衡。
-- 左旋：最简单的右旋示例

图片.png

-- 最小不平衡树的旋转(右旋)(此图并不能确保树的平衡)

图片.png

旋转的结果将不平衡二叉树变成平衡二叉树, 旋转之后只有8,10节点的bf改变, 我们可以通过数学计算计算出旋转之后的8,10的bf(数学推算可以自己推理,这里只给出结果)

右旋的bf计算:

    var n, m int8  // n代表旋转10的bf, m代表旋转之后的8的bf, N旋转之前的节点10
    if N.l.bf >= 0 {
        n = N.bf - N.l.bf - 1
    } else {
        n = N.bf - 1
    }
    if n >= 0 {
        m = N.l.bf - 1
    } else {
        if N.l.bf >= 0 {
            m = N.bf - 2
        } else {
            m = N.l.bf + N.bf - 2
        }
    }

左旋的bf计算:

    var n, m int8
    if N.r.bf >= 0 {
        n = N.bf + 1
    } else {
        n = N.bf + 1 - N.r.bf
    }
    if n >= 0 {
        if N.r.bf < 0 {
            m = N.bf + 2
        } else {
            m = N.bf + 2 + N.r.bf
        }
    } else {
        m = N.r.bf + 1
    }

这里我们只讨论N.bf 等于2 的情况(树不平衡)右旋:
当N.l.bf 大于或等于0 的时候, 此时N.l.bf 只能等于1或者0
n=N.bf - N.l.bf - 1 = 1-N.l.bf = 0|1 (树平衡)
m = N.l.bf-1 = 0|-1(树平衡)
当N.l.bf等于-1的时候
n = -2(树不平衡)
m = -1
所以当N.l.bf = -1 的时候旋转之后的树仍然不平衡, 达不到平衡的目的,此时我们就不能简单的直接右旋
这里我们只讨论N.bf 等于 -1 的情况左旋平衡树:
当N.r.bf 大于或等于0 的时候, 此时N.r.bf 只能等于1或者0
n = N.bf + 1 = 0
m = N.bf + 2 + N.r.bf = 2|1
当N.r.bf 小于0 的时候, 此时N.r.bf 只能等于-1
n = N.bf + 1 - N.r.bf = 1
m = N.bf + 2 = 1
所以当N.r.bf =1 的时候旋转之后的树不平衡(树的高度不变 , 这个可以自行证明)
我们把上面两种情况组合一下

- 当N.bf ==2 && N.l.bf != -1 直接右旋, 旋转以后的树平衡
- 当N.bf == 2 && N.l.bf == -1 时N.l先左旋旋转之后的N.l.bf = m = 2|1
  然后右旋
- - 当N.l.bf = 1的时候, 相当于步骤1 , 右旋之后的树平衡
- - 当N.l.bf = 2的时候代入公式,n = -1, m = 0,树平衡
    N.bf = -2(左旋)同理, 所以最小不平衡树最多通过两步旋转可以变成平衡二叉树
    代码如下


// lRotateBalance 左旋平衡 返回旋转之后的树
func lRotateBalance(N *Node) *Node {
    if N.bf == -2 && N.r.bf == LH {
        N.r = rRotateRf(N.r)
    }

    return lRotateBf(N)
}

// rRotateBalance 右旋平衡 返回旋转之后的树
func rRotateBalance(N *Node) *Node {
    if N.bf == 2 && N.l.bf == RH {
        N.l = lRotateBf(N.l)
    }

    return rRotateRf(N)
}

// lRotateBf 左旋维护bf 旋转之后的Node
func lRotateBf(N *Node) *Node {
    var n, m int8

    if N.r.bf >= 0 {
        n = N.bf + 1
    } else {
        n = N.bf + 1 - N.r.bf
    }

    if n >= 0 {
        if N.r.bf < 0 {
            m = N.bf + 2
        } else {
            m = N.bf + 2 + N.r.bf
        }
    } else {
        m = N.r.bf + 1
    }
    // 旋转树
    root := N.r
    N.r = root.l
    root.l = N

    root.bf, root.l.bf = m, n
    return root
}

// rRotateRf 右旋维护bf 返回旋转之后的树
func rRotateRf(N *Node) *Node {
    // 当N.bf == 2 旋转之后的树高减少1 (可以自行证明)
    // 当N.bf == 1 旋转之后树高不变
    var n, m int8

    if N.l.bf >= 0 {
        n = N.bf - N.l.bf - 1
    } else {
        n = N.bf - 1
    }

    if n >= 0 {
        m = N.l.bf - 1
    } else {
        if N.l.bf >= 0 {
            m = N.bf - 2
        } else {
            m = N.l.bf + N.bf - 2
        }
    }

    // 旋转树
    root := N.l
    N.l = root.r
    root.r = N

    root.bf, root.r.bf = m, n

    return root
}

数据添加实现

知道了如何旋转最小不平衡二叉树保证树的平衡数据的添加就容易了, 可以自行看代码

const (
    LH         = 1  // 左高
    RH         = -1 // 右高
    EH         = 0  // 等高
    NOTBalance = "删除之前,树必须保持平衡"
)
// Insert 向一个AVL树中添加数据 return 添加是否成功
func (T *Tree) Insert(v Value) bool {
    if T == nil {
        return false
    }
    T.head, _ = insertValue(T.head, v)
    return true
}
// insertValue 当前的节点插入数据， 返回修改之后的树，树的高度是否增加
func insertValue(N *Node, v Value) (*Node, bool) {
    if N == nil {
        N := new(Node)
        N.value = v
        return N, true
    }

    if N.value == v {
        // 数据已经存在直接返回
        return N, false
    }

    var h bool // 树的高度是否增加

    if v.Less(N.value) {
        // 左插入
        if N.l, h = insertValue(N.l, v); h {
            if N.bf += 1; N.bf == 2 {
                N = doBalance(N)
                h = false
            } else if N.bf == EH {
                h = false
            }
        }
    } else {
        // 右插入
        if N.r, h = insertValue(N.r, v); h {
            if N.bf -= 1; N.bf == -2 {
                N = doBalance(N)
                h = false
            } else if N.bf == EH {
                h = false
            }
        }

    }

    return N, h
}

// doBalance 平衡最小不平衡树 返回平衡之后的树
func doBalance(N *Node) *Node {
    if N.bf == 2 {
        return rRotateBalance(N)
    } else {
        return lRotateBalance(N)
    }
}

删除

数据的删除分为大致可分为三种情况

叶子节点的删除(直接删除该叶子节点, )
只有单个孩子节点的删除(用孩子节点代替父节点)
有左右孩子节点的删除(用左孩子的最大值代替删除节点,或右孩子的最小值代替当前节点)

删除的代码实现

// Delete AVL树中删除数据 return 是否删除成功
func (T *Tree) Delete(v Value) bool {
    if T == nil || T.head == nil {
        return false // 代表数据不存在
    }

    T.head, _ = del(T.head, v)

    return true
}
// del 删除数据 返回删除后重新排序的树, 树的高度是否改变(减小)
func del(N *Node, v Value) (*Node, bool) {
    if N.value == v {
        // 找到数据执行删除
        return doDelete(N)
    }

    var h bool

    if N.value.Less(v) {
        // 右子树删除
        if N.r == nil { // 数据不存在
            return N, h
        }

        if N.r, h = del(N.r, v); h {

            switch N.bf += 1; N.bf - 1 {
            case EH:
                h = false
            case RH:
            case LH:
                // 此树不平衡为最小不平衡树
                if N.l.bf == EH {
                    h = false
                }
                N = doBalance(N)
            default:
                panic(NOTBalance)
            }
        }
        return N, h
    } else {
        if N.l == nil {
            return N, h
        }

        if N.l, h = del(N.l, v); h {
            N.bf -= 1

            switch N.bf + 1 {
            case EH:
                h = false
            case RH:
                if N.r.bf == EH {
                    h = false
                }
                N = doBalance(N)
            case LH:
            default:
                panic(NOTBalance)
            }
        }
        return N, h

    }
}

// doDelete 删除树的顶点 return 删除后的树，树的高度是否减少
func doDelete(N *Node) (*Node, bool) {
    // 判断删除点左右是否都有值
    if N.l == N.r || N.l == nil {
        return N.r, true
    } else if N.r == nil {
        return N.l, true
    }

    // 左右子树都有值
    // 删除左子树的最大值, 然后将当前为止变成删除的值
    // 或者删除右子树最小值, 然后将当前为止变成删除的值

    var h bool // 左右子树高度是否改变

    switch N.bf {
    case LH:
        if N.l, h, N.value = deleteMax(N.l); h {
            N.bf -= 1
        }
    case EH:
        if N.l, h, N.value = deleteMax(N.l); h {
            N.bf -= 1
        }
        h = false
    default:
        if N.r, h, N.value = deleteMin(N.r); h {
            N.bf += 1
        }
    }
    return N, h
}

// deleteMin 删除最小值，返回删除之后的Node, 树的高度是否减少， 删除的值
func deleteMin(N *Node) (*Node, bool, Value) {

    if N.l == nil {
        return N.r, true, N.value
    } else {
        var h bool
        var v Value

        if N.l, h, v = deleteMin(N.l); h {
            switch N.bf -= 1; N.bf + 1 {
            case EH:
                // 左右子树相等， 单独删除左树一个单位树的长度没有影响
                h = false
            case LH:
            case RH:
                if N.r.bf == EH {
                    h = false
                }
                N = doBalance(N)
            default:
                panic(NOTBalance)
            }

        }

        return N, h, v
    }
}

// deleteMax 删除最大值， 返回删除之后的Node, 树的高度是否减少， 删除的值
func deleteMax(N *Node) (*Node, bool, Value) {

    if N.r == nil {
        return N.l, true, N.value
    } else {
        var h bool
        var v Value
        if N.r, h, v = deleteMax(N.r); h {
            switch N.bf += 1; N.bf - 1 {
            case EH:
                // 左右子树相等， 单独删除左树一个单位树的长度没有影响
                h = false
            case LH:
                if N.l.bf == EH {
                    h = false
                }
                N = doBalance(N)
            case RH:
                // return N, true, v
            default:
                panic(NOTBalance)
            }

        }
        return N, h, v
    }

}

查找

查找就比较简单了可以自己完成

结论

结论AVl树的插入的时候可能会形成最小不平衡二叉树
插入时形成最小不平衡二叉树,因为插入是叶子节点插入,最小不平衡二叉树的高度增加1, 但是不平衡树的旋转会减少树的高度1, 所以插入的时候形成的最小二叉树平衡旋转之后高度和未插入前的高度不变, 对整体的高度影响在形成最小不平衡二叉树的时候消失,所以AVL树的插入最大的旋转次数只有2
AVL树的删除, 删除是对双亲节点左子树或者右子树高度的减少, 当形成最小不平衡二叉树的时候, 旋转最小二叉树,此时相对于旋转之前的二叉树的高度减少1, 所以双亲节点的bf值会+1或者-1(最小不平衡树在左子树-1,在右子树+1), 这种树的高度改变会一直往上冒泡, 可能造成以双亲节点的双亲节点为跟的子AVL不平衡, 极端情况下这种不平衡会一直冒泡到整棵树的根部,所以删除的时候旋转的最大次数为树高-2, 这可能是导致AVL实际应用比较少的原因(删除操作时间复杂度O(logn))

可以优化,改正的地方还请指出

AVL树算法和理论实现（go）

AVL树算法和理论实现（go）

AVL（self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree）树定义可以自行百度。

AVL树的相关数据结构定义

AVL树的相关数据操作

数据添加

数据添加实现

删除

删除的代码实现

查找

结论

AVL树算法和理论实现（go）

AVL（self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree） 树定义可以自行百度。

AVL树的相关数据结构定义

AVL树的相关数据操作

数据添加

数据添加实现

删除

删除的代码实现

查找

结论

AVL（self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree）树定义可以自行百度。