golang实现BST和AVL

一、二分搜索树的定义

二分搜索树（binary search tree, bst）

• 二分搜索树是二叉树。
• 二分搜索树的每个节点的值都大于其左子树的所有节点的值。
• 二分搜索树的每个节点的值都小于其右子树的所有节点的值。
• 每一棵子树也是二分搜索树。

如图：

不过二分搜索树不需要每一个节点都有两个子节点，不需要是一个满二叉树，所以二分搜索树在构建的时候，如果数据集是有序的，比如从小到大，或者从大到小的有序序列，二分搜索树就会退化成链表。

二、二分搜索树的插入和删除

1. 插入节点

因为树是天然的递归结构，所以用递归的写法，实现起来非常简单，比当前节点小就往左子树递归，比当前节点大就往右子树递归，递归的出口就是当给一个空节点添加节点的时候，说明已经到叶子节点或者此时是个root为nil的空树。

代码片段：

func (bst *binarySearchTree) add(node *treeNode, e int) *treeNode {
    if node == nil {
        bst.size++
        return newTreeNode(e)
    }

    if e < node.element {
        node.left = bst.add(node.left, e)
    } else if e > node.element {
        node.right = bst.add(node.right, e)
    }

    return node
}

2. 删除节点

删除节点稍微需要分类讨论，一共有四种种情况：第一种是被删除节点左子树为空，第二种是右子树为空，第三种是左右子树都不为空，第四种情况是左右子树都为空，这种情况可以归并到只有左子树为空或者只有右子树为空的情况去处理。

1. 左子树为空，只需要把右孩子放到当前位置就可以。
2. 右子树为空，只需要把左孩子放到当前位置就可以。
3. 左右子树都不为空，可以选择节点的前驱（左子树中的最大值）或者后继（右子树的最小值）来放到当前被删除的位置上。这里实现的时候，是用的后继来放当被删除的节点位置上。

代码片段：

func (bst *binarySearchTree) remove(node *treeNode, e int) *treeNode {
    if node == nil {
        return nil
    }

    if e < node.element {
        node.left = bst.remove(node.left, e)
        return node
    } else if e > node.element {
        node.right = bst.remove(node.right, e)
        return node
    } else { // e == node.element
        // 1. 左子树为空
        if node.left == nil {
            rightNode := node.right
            node.right = nil
            bst.size--
            return rightNode
        }

        // 2. 右子树为空
        if node.right == nil {
            leftNode := node.left
            node.left = nil
            bst.size--
            return leftNode
        }

        // 3. 左右子树都不为空
        // 找到待删除的节点的后继（比待删除节点的最小节点），然后用这个后继代替待删除的节点. Hibbard deletion
        successor := bst.minimum(node.right)
        successor.right = bst.removeMinNode(node.right)
        successor.left = node.left
        return successor
    }
}

三、二分搜索树的完整实现：binary-search-tree

AVL树

一、AVL树的定义

AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它，它是最早的自平衡二分搜索树。

如前文所说，在极限情况下，比如数据集有序的时候，bst就会退化成链表，严重影响插入查找等操作的性能。而AVL通过左旋和右旋在插入和删除节点的时候维持了自身的平衡性，也就保证了O(logn)的时间复杂度。

AVL树首先一定是一个二分搜索树，但是他自己有一个平衡条件：每个节点的左右子树的高度之差的绝对值（平衡因子）最多为1。

二、产生不平衡的情况：

首先看两种最基本的情况LL和RR。

1. LL的情况

如图所示:

当插入节点比两个节点都小，插入之后三个节点变成类似一个从小到大的链表，就是LL，此时需要做一次右旋转：

在上图中，T1~T4看做是一棵棵子树，全都可以为空，这样一般化处理之后，看待整个右旋转更加清晰，其实就是Y的左子树变成X原来的右子树T3，然后Y变成了X的右子树：

temp := X.right  // T3
X.right = Y
Y.left = temp // Y.left = T3

2. RR的情况

如图所示:

当插入节点比两个节点都大，插入之后三个节点变成类似一个从小到大的链表，就是RR，此时需要做一次左旋转：

在上图中，T1~T4看做是一棵棵子树，全都可以为空，这样一般化处理之后，看待整个左旋转更加清晰，其实就是Y的右子树变成X原来的左子树T3，然后Y变成了X的左子树：

temp := X.left  // T3
X.left = Y
Y.right = temp // Y.right = T3

接下来就是LR和RL的情况，其实如果看懂了LL和RR，那么LR和RL就非常好理解，非常简单。

3. LR的情况

如图所示:

插入节点比左边的节点大，比右边的节点小，但是仔细观察就可以发现，只需要引起不平衡的节点的左孩子做一次左旋，这种情况就会转变为LL，那么只需要沿用处理LL的操作，对引起不平衡的节点做一次右旋就可以继续保持平衡：

4. RL的情况

如图所示:

同理，仔细观察就可以发现，与LR相似，只需要引起不平衡的节点的右孩子做一次右旋，这种情况就会转变为RR，那么只需要沿用处理RR的操作，对引起不平衡的节点做一次左旋就可以继续保持平衡：

因为AVL树其实就是二分搜索树，只是自己通过左旋右旋来保证平衡性，所以具体插入和删除的逻辑是和前面的二分搜索树基本一致的，最大的不同就是在插入和删除的时候，需要重新计算平衡因子，判断是LL、RR、LR还是RL进行对应的调整。