数据结构—平衡二叉树

 二叉排序树集中了数组的查找优势以及链表的插入、删除优势,因此在数据结构中占有一定的地位。但在一定的情况下二叉排序树又有可能变为链表,例如插入从1~100的数,这时进行数据查找的效率就要降低。

为了解决二叉排序树这种左右子树深度不均匀的情况引入了一种平衡二叉树(AVLTree):任何一个节点的左右子树深度差不超过1.通过这个限定,阻止了二叉树的左右子树深度差较大的情况,维持了二叉树的稳定。

  如何让二叉树的左右子树深度差不超过1呢?这就需要对节点进行旋转,也就是当某个节点的左右子树深度超过1时需要对这个节点进行旋转(旋转之后依旧是左子树小于节点小于右子树),重新调整树的结构。

例如:这两棵二叉树虽然结构不同,但是都是二叉排序树,所谓的旋转就是把左边的深度为3的树旋转为右边深度为2的二叉树。

      

在平衡二叉树进行插入操作时遇到的不平衡情况有多种,但是这么多种情况都可以分解为一下四中基础情景:把它叫做:左左、左右、右右、右左。

在解释这四种情景之前需要先明白一个定义:最小不平衡节点—插入一个节点之后,距离这个插入节点最近的不平衡节点就是最小不平衡节点(如上图左树的10节点)。所有的旋转都是在最小不平衡节点的基础上进行的。

继续解释四种情景命名意义:左左:节点插入在最小不平衡节点的左子树的左子树上。     左右:节点插入在最小不平衡节点的左子树的右子树上面

                右:节点插入在最小不平衡树的右子树的右子树上面。   右左:节点插入在最小不平衡树的右子树的左子树上面。

下面就具体分析这四种情况:

  左左:右旋

左左简单不用详解。

左右:先左旋再右旋

这里有人又有疑问了,上面的左左(图2)看明白了,可这里左右情景为什么要旋转两次呢?为什么先左旋,再右旋呢?

先别急,看看这种情况:(图4)

毫无疑问这也是 左右 情景(左左情景有很多种,图3演示的是最基础的情景,所有 的左左情景的旋转情况和图3都是一样的),那么该怎么旋转呢?

直接右旋不对吧?因为6节点的右子树(以根节点10为中心,靠近内部的子树)6-8经过旋转之后要充当10节点的左子树,这样会导致依旧不平衡。所以在这种左右情景下需要进行两次旋转,先把6的右子树降低高度,然后在进行右旋。即:

把图7 情景和图3的情景一样,这就是为什么 左右情景 需要先左旋再右旋的原因。

在这里可以记作:最小不平衡节点的左节点的内部(以根节点做对称轴,偏向对称轴的为内部。也就是以7为节点的子树)的子树高度高于外部子树的高度时需要进行两次旋转。

右右:左旋

右右情景直接左旋即可。不在详解

右左:先右旋,再左旋

为什么这样旋转明白了吧?如同左右情景,考虑到图10的 右左情景

这种情景旋转如图11

旋转的四种情景就这些了。需要说明的是,下面这两对情景旋转是一样的。

图12都是右左情景,具体看代码的旋转方法就明白了在第一次右旋的时候进行的操作。private Node<T> rotateSingleRight(Node<T> node);

图13都是左右情景,第一次左旋见:private Node<T> rotateSingleLeft(Node<T> node);

旋转情景弄明白之后就是怎么代码实现了,在实现代码之前需要考虑如何进行树高判断。这里就根据定义来,|左子树树高-右子树树高|<2。如果大于等于2则该节点就不在 平衡,需要进行旋转操作。因此在程序中节点中需要定义一个height属性来存储该节点的树高。

由于平衡二叉树的性质,二叉树的高度不会很高,程序使用递归进行数据插入查找不会造成栈溢出异常,所以程序采用递归操作进行插入查找。

平衡的判定策略是在进行递归回溯的时候依照回溯路径更新节点的树高,然后根据|左子树树高-右子树树高|<2来判定该节点是否失衡,进一步对是够旋转进行判定。

程序中的平衡判定策略比较漂亮,当时就是一直卡在这里无法继续进行,然后参考了 AVL树-自平衡二叉查找树(Java实现) 之后采用这种方法才得以解决。

平衡二叉树的删除操作。

对于平衡二叉树的删除操作,只要明白一点就可以了:

    如果该节点没有左右子树(该节点为叶子节点)或者只有其中一个子树则可以直接进行删除

       否则需要继续进行判定该节点:如果该节点的外部(内外:以根节点做对称轴,靠近对称轴的子树为内部子树)子树树高低于内部子树树高,则找到该节点内部子树的最值(最值:如果内部子树是该节点的右子树则数值为右子树的最小值;如果内部节点是该节点的左子树则数值为该节点左子树的最大值)进行数值交换,交换之后删除该节点即可。

删除之后进行回溯的时候要更新节点的树高,然后判断节点是否平衡,不平衡进行旋转。这时对旋转次数的判定就不同于插入时的判定。

如图14 删除11节点

这种情景需不需要进行两次旋转?该如何判定?

毫无疑问肯定是要进行一次右旋的,但是在右旋之前是不是要进行一次左旋呢?

  这就要根据最小不平衡节点的左节点6进行判定,如果6的左节点树高低于6的右节点树高则需要进行一次左旋,最后进行一次右旋结束。

   如果6的左子树树高高于6的右子树树高则不需进行左旋可以直接对10节点进行右旋结束操作。

如图15,这种情况肯定需要进行左旋,至于在左旋之前要不要对13节点进行右旋,相信知道该如何判断了。

  根据13节点的左右子树高度来判断,左子树(内部)高于右子树(外部)高度则需要进行左旋,图15这种情景是不需要的。

知道了各种旋转的判定标准,程序中就没有其他什么难点了,下面看一下代码:

package com.zpj.datastructure.avlTree;/**
 * @author PerKins Zhu
 * @date:2016年8月30日 下午8:01:03
 * @version :1.1
 * 
 */// 存储数据类型必须实现Comparable接口,实现比较方法public class AVLTree<T extends Comparable<T>> {    private Node<T> root;    // 定义节点存储数据
    private static class Node<T> {
        Node<T> left;// 左孩子
        Node<T> right;// 右孩子
        T data; // 存储数据
        int height; // 树高

        public Node(Node<T> left, Node<T> right, T data) {            this.left = left;            this.right = right;            this.data = data;            this.height = 0;
        }
    }    // 对外公开的方法进行插入
    public Node<T> insert(T data) {        return root = insert(data, root);
    }    // 私有方法进行递归插入,返回插入节点
    private Node<T> insert(T data, Node<T> node) {        // 递归终止条件
        if (node == null)            return new Node<T>(null, null, data);        // 比较插入数据和待插入节点的大小
        int compareResult = data.compareTo(node.data);        if (compareResult > 0) {// 插入node的右子树
            node.right = insert(data, node.right);            // 回调时判断是否平衡
            if (getHeight(node.right) - getHeight(node.left) == 2) {// 不平衡进行旋转                // 判断是需要进行两次旋转还是需要进行一次旋转
                int compareResult02 = data.compareTo(node.right.data);                if (compareResult02 > 0)// 进行一次左旋(右右)
                    node = rotateSingleLeft(node);                else
                    // 进行两次旋转,先右旋,再左旋
                    node = rotateDoubleLeft(node);
            }
        } else if (compareResult < 0) {// 插入node的左子树
            node.left = insert(data, node.left);            // 回调时进行判断是否平衡
            if (getHeight(node.left) - getHeight(node.right) == 2) {// 进行旋转                // 判断是需要进行两次旋转还是需要进行一次旋转
                int intcompareResult02 = data.compareTo(node.left.data);                if (intcompareResult02 < 0)// 进行一次左旋(左左)
                    node = rotateSingleRight(node);                else
                    // 进行两次旋转,先左旋,再右旋
                    node = rotateDoubleRight(node);
            }
        }        // 重新计算该节点的树高
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;        return node;
    }    // 右右情况--进行左旋
    private Node<T> rotateSingleLeft(Node<T> node) {
        Node<T> rightNode = node.right;
        node.right = rightNode.left;
        rightNode.left = node;        // 旋转结束计算树高
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        rightNode.height = Math.max(node.height, getHeight(rightNode.right)) + 1;        return rightNode;
    }    // 左左情况--进行右旋
    private Node<T> rotateSingleRight(Node<T> node) {
        Node<T> leftNode = node.left;
        node.left = leftNode.right;
        leftNode.right = node;        // 旋转结束计算树高
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        leftNode.height = Math.max(getHeight(leftNode.left), node.height) + 1;        return leftNode;
    }    // 右左情况--先右旋再左旋
    private Node<T> rotateDoubleLeft(Node<T> node) {        // 先进行右旋
        node.right = rotateSingleRight(node.right);        // 再加上左旋
        node = rotateSingleLeft(node);        return node;
    }    // 左右--先左旋再右旋
    private Node<T> rotateDoubleRight(Node<T> node) {        // 先进行左旋
        node.left = rotateSingleLeft(node.left);        // 在进行右旋
        node = rotateSingleRight(node);        return node;
    }    // 计算树高
    private int getHeight(Node<T> node) {        return node == null ? -1 : node.height;
    }    // public 方法供外部进行删除调用
    public Node<T> remove(T data) {        return root = remove(data, root);
    }    // 递归进行删除,返回比较节点
    private Node<T> remove(T data, Node<T> node) {        if (node == null) {// 不存在此节店,返回null.不需要调整树高
            return null;
        }        int compareResult = data.compareTo(node.data);        if (compareResult == 0) {// 存在此节点进入
            /**
             * 找到节点之后进行节点删除操作 判断node是否有子树,如果没有子树或者只有一个子树则直接进行删除
             *     如果有两个子树,则需要判断node的平衡系数balance
             *         如果balance为0或者1则把node和node的左子树的最大值进行交换 否则把node和右子树的最小值进行交换
             *         交换数据之后删除该节点 删除之后判断delete节点的父节点是否平衡,如果不平衡进行节点旋转
             * 旋转之后返回delete节点的父节点进行回溯
             * */
            if (node.left != null && node.right != null) { // 此节点存在左右子树                // 判断node节点的balance,然后进行数据交换删除节点
                int balance = getHeight(node.left) - getHeight(node.right);
                Node<T> temp = node;// 保存需要进行删除的node节点
                if (balance == -1) {                    // 与右子树的最小值进行交换                    exChangeRightData(node, node.right);
                } else {                    // 与左子树的最大值进行交换                    exChangeLeftData(node, node.left);
                }                // 此时已经交换完成并且把节点删除完成,则需要重新计算该节点的树高
                temp.height = Math.max(getHeight(temp.left), getHeight(temp.right)) + 1;                // 注意此处,返回的是temp,也就是保存的需要删除的节点,而不是替换的节点
                return temp;
            } else {                // 把node的子节点返回调用处等于删除了node节点                // 此处隐含了一个node.left ==null && node.right == null 的条件,这时返回null
                return node.left != null ? node.left : node.right;
            }
        } else if (compareResult > 0) {// 没找到需要删除的节点继续递归进行寻找
            node.right = remove(data, node.right);            // 删除之后进行树高更新
            node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;            // 如果不平衡则进行右旋调整。
            if (getHeight(node.left) - getHeight(node.right) == 2) {// 进行旋转
                Node<T> leftSon = node.left;                // 判断是否需要进行两次右旋还是一次右旋                // 判断条件就是比较leftSon节点的左右子节点树高
                if (leftSon.left.height > leftSon.right.height) {                    // 右旋一次
                    node = rotateSingleRight(node);
                } else {                    // 两次旋转,先左旋,后右旋
                    node = rotateDoubleRight(node);
                }
            }            return node;
        } else if (compareResult < 0) {// 没找到需要删除的节点继续递归进行寻找
            node.left = remove(data, node.left);            // 删除之后进行树高更新
            node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;            // 如果不平衡进行左旋操作
            if (getHeight(node.left) - getHeight(node.right) == 2) {// 进行旋转
                Node<T> rightSon = node.right;                // 判断是否需要进行两次右旋还是一次右旋                // 判断条件就是比较rightSon节点的左右子节点树高
                if (rightSon.right.height > rightSon.left.height) {
                    node = rotateSingleLeft(node);
                } else {                    // 先右旋再左旋
                    node = rotateDoubleLeft(node);
                }
            }            return node;
        }        return null;
    }    // 递归寻找right节点的最大值
    private Node<T> exChangeLeftData(Node<T> node, Node<T> right) {        if (right.right != null) {
            right.right = exChangeLeftData(node, right.right);
        } else {            // 数据进行替换
            node.data = right.data;            // 此处已经把替换节点删除
            return right.left;
        }
        right.height = Math.max(getHeight(right.left), getHeight(right.right)) + 1;        // 回溯判断left是否平衡,如果不平衡则进行左旋操作。
        int isbanlance = getHeight(right.left) - getHeight(right.right);        if (isbanlance == 2) {// 进行旋转
            Node<T> leftSon = node.left;            // 判断是否需要进行两次右旋还是一次右旋            // 判断条件就是比较leftSon节点的左右子节点树高
            if (leftSon.left.height > leftSon.right.height) {                // 右旋一次
                return node = rotateSingleRight(node);
            } else {                // 两次旋转,先左旋,后右旋
                return node = rotateDoubleRight(node);
            }
        }        return right;
    }    // 递归寻找left节点的最小值
    private Node<T> exChangeRightData(Node<T> node, Node<T> left) {        if (left.left != null) {
            left.left = exChangeRightData(node, left.left);
        } else {
            node.data = left.data;            // 此处已经把替换节点删除
            return left.right;
        }
        left.height = Math.max(getHeight(left.left), getHeight(left.right)) + 1;        // 回溯判断left是否平衡,如果不平衡则进行左旋操作。
        int isbanlance = getHeight(left.left) - getHeight(left.right);        if (isbanlance == -2) {// 进行旋转
            Node<T> rightSon = node.right;            // 判断是否需要进行两次右旋还是一次右旋            // 判断条件就是比较rightSon节点的左右子节点树高
            if (rightSon.right.height > rightSon.left.height) {                return node = rotateSingleLeft(node);
            } else {                // 先右旋再左旋
                return node = rotateDoubleLeft(node);
            }
        }        return left;
    }    // ************************中序输出  输出结果有小到大*************************************
    public void inorderTraverse() {
        inorderTraverseData(root);
    }    // 递归中序遍历
    private void inorderTraverseData(Node<T> node) {        if (node.left != null) {
            inorderTraverseData(node.left);
        }
        System.out.print(node.data + "、");        if (node.right != null) {
            inorderTraverseData(node.right);
        }
    }

}

这段测试程序可以进行测试:

package com.zpj.datastructure.avlTree;import org.junit.Test;/**
 * @author PerKins Zhu
 * @date:2016年8月30日 下午8:42:15
 * @version :1.1
 * 
 */public class AVLTreeTest {

    @Test    public void test01() {
        AVLTree tree = new AVLTree();        int array[] = { 28, 35, 5, 35, 26, 30, 1, 21, 18, 35, 7, 30, 25, 1, 7, };        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ",");
            tree.insert(array[i]);
        }
        System.out.println();
        tree.inorderTraverse();
        tree.remove(12);
        System.out.println();
        tree.inorderTraverse();
    }

    @Test    public void test02() {
        AVLTree tree = new AVLTree();        int temp = 0;        for (int i = 0; i < 15; i++) {            int num = (int) (Math.random() * 40);
            System.out.print(num + ",");
            tree.insert(num);
            temp = num;
        }
        System.out.println();
        tree.inorderTraverse();
        tree.remove(temp);// 删除插入的最后一个数据        System.out.println();
        tree.inorderTraverse();
    }

}

时间: 04-26

数据结构—平衡二叉树的相关文章

数据结构-平衡二叉树

平衡二叉树的重点在于对不平衡的进行旋转从而使它达到平衡. 下面是我理解的平衡二叉树的操作总结: 平衡因子(BF): 这是一个描述平衡度的一个量,计算的方式为 左子树的深度-右子树的深度. 我们可以从BF中就能知道左子树和右子树之间的平衡程度. 插入数据 平衡二叉树最复杂的就是将数据插入到树中了,因为要涉及到位置的调整.对于位置的调整在平衡二叉树中成为树的旋转.根据平衡因子的状态分为左旋和右旋. 那什么时候需要进行旋转呢? 这个问题确实值得思考,一般都是在平衡因子的绝对值大于1的时候就需要进行旋转

大话数据结构—平衡二叉树(AVL树)

平衡二叉树(Self-Balancing Binary Search Tree/Height-Balanced Binary Search Tree),是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1. 平衡二叉树的前提是二叉排序树,不是二叉排序树的都不是平衡二叉树. 平衡因子BF(Balance Factor):二叉树上节点的左子树深度减去右子树深度的值. 最小不平衡子树:距离插入节点最近的,且平衡因子的绝对值大于1的节点为根的子树. 下图中,新插入节点37时,距离它最近的平

浅谈数据结构-平衡二叉树

平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树.1962年,G.M. Adelson-Velsky 和 E.M. Landis发明了这棵树,所以它又叫AVL树.平衡二叉树要求对于每一个节点来说,它的左右子树的高度之差不能超过1,如果插入或者删除一个节点使得高度之差大于1,就要进行节点之间的旋转,将二叉树重新维持在一个平衡状态.这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(

数据结构 平衡二叉树avl c++

平衡二叉树:一颗空树,或者是具有以下性质的二叉树 左子树和右子树都是平衡二叉树 左子树和右子树的深度只差不超过1 把二叉树节点的平衡因子BF(Balance Factor)定义为该节点的左子树深度减去右子树深度,则平衡二叉树所有结点的平衡因子只能是-1,0,1.只要有一个结点的平衡因子绝对值大于一就是不平衡的: 平衡二叉树的构造 对二叉树结点做一下定义,bf用来记录结点的平衡因子 1 typedef struct BSTNode{ 2 int val; 3 int bf; 4 struct BS

数据结构-平衡二叉树(AVL树)

一.平衡二叉树的定义 使树的高度在每次插入元素后仍然能保持O(logn)的级别 AVL仍然是一棵二叉查找树 左右子树的高度之差是平衡因子,且值不超过1 //数据类型 struct node{ int v, height; node *lchild, *rchild; }; //新建一个结点 node* newNode(int v){ node* Node = new node; Node->v = v; Node->height = 1; Node->lchild = Node->

20172310 2017-2018《程序设计与数据结构》(下)第七周学习总结

20172310 2017-2018<程序设计与数据结构>(下)第七周学习总结 教材学习内容总结 本章学习的是二叉查找树 11.1 概述 二叉查找树(binay scarch tree)是种带有附加属性的二叉树,即对树中的每个结点,其左孩子都要小于其父结点,而父结点又小于或等于其右孩子. 二叉查找树的定义是上章中讨论的二叉树定义的扩展.因此,下面的操作是二叉树中已定义的那些操作的补充.二叉查找树和平衡二叉查找树的接口是一样的程序列表. 11.2 用链表实现二叉查找树 BinaryTreeNod

网络爬虫(java)

   陆陆续续做了有一个月,期间因为各种技术问题被多次暂停,最关键的一次主要是因为存储容器使用的普通二叉树,在节点权重相同的情况下导致树高增高,在进行遍历的时候效率大大降低,甚至在使用递归的时候导致栈内存溢出.后来取消递归遍历算法,把普通的二叉排序树升级为平衡二叉树这才解决这些问题.着这个过程中把栈.队列.链表.HashMap.HashTable各种数据结构都重新学习了一遍,使用红黑二叉树实现的TreeMap暂时还没有看,后期需要把TreeMap的实现源码学习一下. 为了把项目做成可扩展性的,方

第十章笔记&#183;优先级队列

需求与动机 什么是优先级队列 优先队列是计算机科学中的一类抽象数据类型.优先队列中的每个元素都有各自的优先级,优先级最高的元素最先得到服务:优先级相同的元素按照其在优先队列中的顺序得到服务.优先队列往往用堆来实现. --wikipedia 应用需求 在医院门诊,如果只有一个医生,多位病人.按照通常流程来说,采用先到先服务的顺序(FIFO).但是如果病人中有人患有心脏病,那么显然这个病人需要得到优先治疗. 在计算机系统中,绝大多数支持多任务,这种多任务调度也类似于医院门诊.CPU相当于医生,计算任

要善于总结,实践,才有出路

1.之前对pjsip会话状态机,voip skeleton,Email Server和iptable,nginx等程序的总结不够,没有形成清晰的认识 2.对学过的shell,makefile知识点要写好总结,以免以后用到能够快速地学习 3.对学过的算法(快排,堆,合并,希尔,二叉树的遍历等)和数据结构(平衡二叉树,红黑树等), 要时时复习,多点写代码测试 4.之前做过的<深入理解操作系统>的几个lab,要不断地完善,学习 6.总结来自学习和实践,总结出来的精华用来指导实践和学习 7.简历要凝练