golang 手撸 平衡二叉树

golang 手撸 平衡二叉树

树是一种计算机数据结构中非常常用的一种结构，其中就包含了：平衡二叉树，这种树是一种特殊的二叉查找树(二叉查找树也就是，右孩子大于其父结点，左孩子小于其父结点的树)，但是简单的二叉查找树存在的问题就是不平衡，最差的查找效率为O(n)，故就有人发明了一种平衡的额二叉查找树。

特点

1. 平衡二叉树是一种二叉查找树
2. 每个结点的左子树的高度减去右子树的高度的绝对值不超过1
3. 空树和左右子树都是平衡二叉树
4. 相比红黑树，平衡二叉树比较适用于没有删除的情况

平衡因子

平衡二叉树是在二叉查查找树的基础上进行构建了，为了维持平衡二叉树的平衡，那么就需要一种机制来判断平衡二叉树是否是平衡的。这种机制就叫做平衡因子。

平衡二叉树的每个结点都会维持一个值，这个值就是平衡因子，这个平衡因子就是这个结点的左子树的高度减去右子树的高度得到的值。如果这个平衡因子的值的绝对值大于1了，说明这个树就不平衡了，那么就需要调整树的结构了。

我们可以从如上这个这个图中看的到：每个结点都维持了一个值，比如左边的AVL 树根结点的值为-1，这个-1是怎么来的呢，就是结点 3 的左子树的高度为 2, 右子树的高度为 3, 左子树的高度减去右子树的高度就得到这个结点的平衡因子。

如果某个结点的平衡因子的绝对值大于了 1 ，那么就说明这个平衡二叉树不平衡了，就需要调整平衡二叉树的结构。

旋转

由于AVL树需要做到平衡，所以每次插入叶子节点，如果发现不平衡，都需要进行旋转以保持平衡。

找到了要给别人做的一个旋转图例，可以参考的看下：

我们来总结下以上图片中出现的这几种情况：

1. 三个结点的单旋转

   

• 我们可以看到上途中结点3的平衡因子为2了，这样就不平衡横了，那么就需要进行一个对结点3的顺时针旋转，旋转完的结果就是上图中的右图。

1. 三个结点的双旋转

   

三个结点的单旋转
三个结点的单旋转
三个结点的单旋转

什么时候怎样旋转呢?

1. 我们插入一个结点后，某个结点p的平衡因子由原来的1变成了2。

   • 那就可能是这两种情况：

   1. 新插入的结点插入到了结点p的左子树的左孩子下

      • 

      • golang 代码实现

        // 顺时针旋转，右旋
        func (avlNode *AVLNode) RightRotate() *AVLNode {
            headNode := avlNode.Left
            avlNode.Left = headNode.Right
            headNode.Right = avlNode
        
            // 更新旋转后结点的高度
            avlNode.height = Max(avlNode.Left.GetHeight(), avlNode.Right.GetHeight())+1
            headNode.height = Max(headNode.Left.GetHeight(), headNode.Right.GetHeight())+1
        
            return headNode
        }

   2. 新插入的结点插入到了结点p的左子树的右孩子下

      • 
      • 

      • 从以上例子中我们就可以发现，顺时针旋转和逆时针旋转的规律所在

      • golang 代码实现

        // 先逆时针旋转再顺时针旋转，先左旋，在右旋
        func (avlNode *AVLNode) LeftThenRightRotate() *AVLNode {
            // 先把左孩子结点进行左旋
            avlNode.Left = avlNode.Left.LeftRotate()
            // 然后把自己右旋
            return avlNode.RightRotate()
        }

   • 从以上的三张图中我们就可以发现这样的一个容易忽略的问题
     1. 假设有一个结点，这个结点是P，我们在逆时针旋转一个结点的时候需要把结点P的右孩子的左子树移动为结点P的右子树
     2. 假设有一个结点，这个结点是P，我们在顺时针旋转时，需要把P结点的左孩子的右子树移动为P结点的左子树

2. 我们插入一个结点后，某个结点p的平衡因子由原来的-1变成了-2。

   • 那就可能是这两种情况：

   1. 新插入的结点插入到了结点p的右子树的右孩子下

      • 那就应该进行对结点p的逆时针旋转
      • 旋转过程可以参考上图
      • golang 实现

        // 逆时针旋转，左旋
        func (avlNode *AVLNode) LeftRotate() *AVLNode {
            headNode := avlNode.Right
            avlNode.Right = headNode.Left
            headNode.Left = avlNode
        
            // 更新结点的高度
            // 这里应该注意的俄式应该先更新avlNode 的高度，因为headNode结点在avlNode结点的上面
            // headNode计算高度的时候要根据avlNode的高度来计算
            avlNode.height = Max(avlNode.Left.GetHeight(), avlNode.Right.GetHeight())+1
            headNode.height = Max(headNode.Left.GetHeight(), headNode.Right.GetHeight())+1
        
            return headNode
        }

   2. 新插入的结点插入到了结点p的右子树的左孩子下

      • 那就因该先对结点p的右孩子进行顺时针旋转
      • 然后在对结点p进行逆时针旋转
      • 旋转过程可以参考上图
      • golang 实现

        // 先顺时针旋转再逆时针旋转，先右旋，再左旋
        func (avlNode *AVLNode) RightThenLeftRotate() *AVLNode {
            // 先把右孩子进行右旋
            avlNode.Right = avlNode.Right.RightRotate()
            // 然后把自己右旋
            return avlNode.LeftRotate()
        }

上面我们展示了针对具体的四种情况，是怎么怎么旋转的，但是我们要写一个函数用来判断这四种情况：

// 调整AVL树的平衡
func (avlNode *AVLNode) adjust() *AVLNode {
    // 如果右子树的高度比左子树的高度大于2
    if avlNode.Right.GetHeight() - avlNode.Left.GetHeight() == 2 {
        // 如果 avlNode.Right 的右子树的高度比avlNode.Right的左子树高度大
        // 直接对avlNode进行左旋转
        // 否则先对 avlNode.Right进行右旋转然后再对avlNode进行左旋转
        if avlNode.Right.Right.GetHeight() > avlNode.Right.Left.GetHeight() {
            avlNode = avlNode.LeftRotate()
        }else{
            avlNode = avlNode.RightThenLeftRotate()
        }
        // 如果左子树的高度比右子树的高度大2
    }else if avlNode.Right.GetHeight() - avlNode.Left.GetHeight() == -2 {
        // 如果avlNode.Left的左子树高度大于avlNode.Left的右子树高度
        // 那么就直接对avlNode进行右旋
        // 否则先对avlNode.Left进行左旋，然后对avlNode进行右旋
        if avlNode.Left.Left.GetHeight() > avlNode.Left.Right.GetHeight() {
            avlNode = avlNode.RightRotate()
        }else {
            avlNode = avlNode.LeftThenRightRotate()
        }
    }

    return avlNode
}

golang 实现

AVLNode

type AVLNode struct {
    Left, Right *AVLNode    // 表示指向左孩子和右孩子
    Data        interface{} // 结点存储数据
    height      int         // 记录这个结点此时的高度
}

AVL树还需要一些简单的获取和设置结点性质的方法

注意：每次NewAVLNode的时候height一定是1，因为一个简单的高度最低就是1

// 定义comparer 指针类型
// 用来比较两个结点中Data的大小
type comparator func(a, b interface{}) int

// compare 指针
var compare comparator

// 新建一个结点
func NewAVLNode(data interface{}) *AVLNode {
    return &AVLNode{
        Left:   nil,
        Right:  nil,
        Data:   data,
        height: 1,
    }
}

// 新建AVL 树
func NewAVLTree(data interface{}, myfunc comparator) (*AVLNode, error) {
    if data == nil && myfunc == nil {
        return nil, errors.New("不能为空")
    }
    compare = myfunc
    return NewAVLNode(data), nil
}

// 获取结点数据
func (avlNode *AVLNode) GetData() interface{} {
    return avlNode.Data
}

// 设置结点数据
func (avlNode *AVLNode) SetData(data interface{}) {
    if avlNode == nil {
        return
    }
    avlNode.Data = data
}

// 获取结点的右孩子结点
func (avlNode *AVLNode) GetRight() *AVLNode {
    if avlNode == nil {
        return nil
    }
    return avlNode.Right
}

// 获取结点的左孩子结点
func (avlNode *AVLNode) GetLeft() *AVLNode {
    if avlNode == nil {
        return nil
    }
    return avlNode.Left
}

// 获取结点的高度
func (avlNode *AVLNode) GetHeight() int {
    if avlNode == nil {
        return 0
    }
    return avlNode.height
}

//比较两个子树高度的大小
func Max(a, b int) int {
    if a >= b {
        return a
    } else {
        return b
    }
}

查找结点

查找指定结点

// 查找指定值
func (avlNode *AVLNode) Find(data interface{}) *AVLNode {
    var finded *AVLNode
    // 调用比较函数比较两个结点的指的大小
    switch compare(data, avlNode.Data) {
    case -1:
        finded = avlNode.Left.Find(data)
    case 1:
        finded = avlNode.Right.Find(data)
    case 0:
        return avlNode
    }

    return finded
}

查找最大结点

// 查找最大值
func (avlNode *AVLNode) FindMax() *AVLNode {
    var finded *AVLNode

    if avlNode.Right != nil {
        finded = avlNode.Right.FindMin()
    } else {
        finded = avlNode
    }

    return finded
}

查找最小结点

// 查找最小值
func (avlNode *AVLNode) FindMin() *AVLNode { // 递归写法
    var finded *AVLNode

    if avlNode.Left != nil {
        finded = avlNode.Left.FindMin()
    } else {
        finded = avlNode
    }

    return finded
}

插入和删除

插入

// 插入数据
// 因为没有定义 结点的parent指针，所以你插入数据就只能递归的插入，因为我要调整树的平衡和高度
func (avlNode *AVLNode) Insert(value interface{}) *AVLNode {
    if avlNode == nil {
        return NewAVLNode(value)
    }

    switch compare(value, avlNode.Data) {
    case -1:
        // 如果value 小于 avlNode.Data 那么就在avlNode的左子树上去插入value
        avlNode.Left = avlNode.Left.Insert(value)
        avlNode = avlNode.adjust() // 自动调整平衡
    case 1:
        avlNode.Right = avlNode.Right.Insert(value)
        avlNode = avlNode.adjust()
    case 0:
        fmt.Print("数据已经存在")
    }
    // 修改结点的高度
    avlNode.height = Max(avlNode.Left.GetHeight(), avlNode.Right.GetHeight()) + 1

    return avlNode
}

插入数据的时候我们应该注意的是，我们要针对插入点相关的父结点，都要判断是否平衡，然后就行平衡的调整。

删除

// 删除数据
func (avlNode *AVLNode) Delete(value interface{}) *AVLNode {
    // 没有找到匹配的数据
    if avlNode == nil {
        //fmt.Println("不存在", value)
        return nil
    }

    switch compare(value, avlNode.Data) {
    case 1:
        avlNode.Right = avlNode.Right.Delete(value)
    case -1:
        avlNode.Left = avlNode.Left.Delete(value)
    case 0:
        // 找到数据，删除结点
        if avlNode.Left != nil && avlNode.Right != nil { // 结点有左孩子和右孩子
            avlNode.Data = avlNode.Right.FindMin().Data
            avlNode.Right = avlNode.Right.Delete(avlNode.Data)
        } else if avlNode.Left != nil { // 结点只有左孩子，无右孩子
            avlNode = avlNode.Left
        } else { // 结点只有右孩子或者无孩子
            avlNode = avlNode.Right
        }

    }

    // 自动调整平衡, 如果avlNode!=nil说明执行了对avlNode 的某个子树执行了删除结点，那么就需要重新调整树的平衡
    if avlNode != nil {
        avlNode.height = Max(avlNode.Left.GetHeight(), avlNode.Right.GetHeight()) + 1
        avlNode = avlNode.adjust() // 自动平衡
    }

    return avlNode
}