Java数据结构-二叉查找树续以及平衡二叉查找树

傷城~ 2022-08-04 12:47 239阅读 0赞

前面一篇文章讲到了[二叉查找树的实现][Link 1]，其中的插入操作是使用非递归方法实现的，这里再增加一种递归实现插入的操作，Java代码如下，建议增加到前一篇文章对应的`FOBinarySearchTree.java`中；

/**
     * @TODO 二叉排序树插入元素(递归方法)
     * @param e 需要插入的元素
     * @return true or false
     */
    public boolean insert(E e){
        insert(root,e);
        return true;
    }
    /**
     * @TODO 二叉排序树插入元素的实现(递归方法)
     * @param node 二叉排序树跟结点
     * @param e 需要插入的元素
     * @return true or false
     */
    private FOBinarySearchTreeNode<E> insert(FOBinarySearchTreeNode<E> node , E e){
        if (node == null) {
            return new FOBinarySearchTreeNode<E>(e,null,null,null);
        }
        int cmpResult = e.compareTo(node.getE());
        if (cmpResult > 0) {
            node.setRightChild(insert(node.getRightChild(),e));
            node.getRightChild().setParent(node);
        } else if(cmpResult < 0){
            node.setLeftChild(insert(node.getLeftChild(),e));
            node.getLeftChild().setParent(node);
        }else{
            ;
        }
        return node;
    }

至于二叉查找树的删除操作的递归方法这里就没有实现了，而是继续采用上篇文章的“找到要删除结点的前驱或者后继方法来进行删除操作”。

平衡二叉查找树：  
  在二叉查找树的定义基础上增加了平衡的概念，即每个节点的左子树和右子树的高度最多差1的二叉查找树。

平衡二叉查找树的主要知识点就在其旋转算法，它的旋转算法（即二叉平衡查找树失去平衡需要作出的操作）有以下四种情况：

**LL**：也称之为“左左”；对根结点的左儿子的左子树进行一次插入；插入一个节点后，根节点的左子树的左子树还有非空子节点，导致”根的左子树的高度”比”根的右子树的高度”大2，导致AVL树失去了平衡。

**LR**：也称为”左右”。对根结点的左儿子的右子树进行一次插入；插入一个节点后，根节点的左子树的右子树还有非空子节点，导致”根的左子树的高度”比”根的右子树的高度”大2，导致AVL树失去了平衡。

**RL**：称为”右左”。对根结点的右儿子的左子树进行一次插入；插入一个节点后，根节点的右子树的左子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。

*\* RR\**：称为”右右”。对根结点的右儿子的右子树进行一次插入；插入一个节点后，根节点的右子树的右子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。

下面对着四种旋转情况举出两种例子：  
  这里摘自<[http://www.cnblogs.com/skywang12345/p/3576969.html][http_www.cnblogs.com_skywang12345_p_3576969.html]>的一些讲解，讲解的不错，可以直接进入其博客查看。

**LL的旋转**

LL失去平衡的情况，可以通过一次旋转让AVL树恢复平衡。如下图：

![avl.jpg][]

图中左边是旋转之前的树，右边是旋转之后的树。从中可以发现，旋转之后的树又变成了AVL树，而且该旋转只需要一次即可完成。

对于LL旋转，你可以这样理解为：LL旋转是围绕”失去平衡的AVL根节点”进行的，也就是节点k2；而且由于是LL情况，即左左情况，就用手抓着”左孩子，即k1”使劲摇。将k1变成根节点，k2变成k1的右子树，”k1的右子树”变成”k2的左子树”。

**LR的旋转**

LR失去平衡的情况，需要经过两次旋转才能让AVL树恢复平衡。如下图：

![avl2.jpg][]

第一次旋转是围绕”k1”进行的”RR旋转”，第二次是围绕”k3”进行的”LL旋转”。

[Link 1]: http://panhainan.com/2015/08/23/Java%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%A0%91%E7%9A%84%E5%BA%94%E7%94%A8-%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91/
[http_www.cnblogs.com_skywang12345_p_3576969.html]: http://www.cnblogs.com/skywang12345/p/3576969.html
[avl.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/arithmetic/avl.jpg
[avl2.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/arithmetic/avl2.jpg