[数据结构与算法] 数据结构八、AVL平衡二叉树(不仅满还完全的二叉树)以及红黑树(单一黑平衡的二叉树)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构八、AVL平衡二叉树(不仅满还完全的二叉树)以及红黑树(单一黑平衡的二叉树) -> 正文阅读

[数据结构与算法]数据结构八、AVL平衡二叉树(不仅满还完全的二叉树)以及红黑树(单一黑平衡的二叉树)

文章目录

平衡二叉树

(1)平衡二叉树描述

一棵满二叉树和完全二叉树的组合就是平衡二叉树
线段树也是平衡二叉树
平衡二叉树的要求：
- 对于任意一个结点，左子树和右子树的高度差不能超过1

(2)平衡二叉树的搭建

我们由改版形成,源代码请看二分搜索树

(3)平衡二叉树的初始化

平衡二叉树在二分搜索树中引进了树的高的,平衡因子
- 在平衡因子的值的绝对值中总小于等于1的树就是平衡二叉树
  - 初始化时高度必须为→,我们默认添加的是叶子节点
- 获取结点高度
- 获取结点的平衡因子
  - 左子树的高度-右子树的高度
- 判断此树是否为二分搜索树
  - 利用中序遍历
  - 根据左右的顺序将节点存在集合中,
  - 判断集合的前一个数字是否大于后一个数字
  - 若大则是二分搜索树
- 判断此树是否为平衡二叉树
  - 抓住性质
  - 平衡因子的值的绝对值中总小于等于1的树就是平衡二叉树
- 增加操作中更新结点的高度
  - 因为每次添加树的高度都需要做操作
  - head.height = Math.max(getNodeHeight(head.left), getNodeHeight(head.right)) + 1;
  - 树的高等于当前节点的左子树节点与右子树节点的最大值加一

public class MySearchTree<E extends Comparable<E>> {
   private class Node {
        E ele;
        Node left; //左孩子
        Node right;//右孩子
        int height;//以该结点为根的二分搜索树高度

        //构造方法
        public Node(E ele) {
            this.ele = ele;
            left = null;
            right = null;
            height = 1; //只要添加那高度就为1(默认添加的是叶子结点)
        }

        public Node() {
            this(null);
        }
    }
    
    //获取结点的高度
    private int getNodeHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    //获取平衡因子(左子树的高度-右子树的高度)
    private int getBalance(Node node) {
        if (node == null) {
            return 0;
        }
        return getNodeHeight(node.left) - getNodeHeight(node.right);
    }

    //判断树是否为二分搜索树
    public boolean isSearchTree() {
        if (isEmpty()) {
            return true;
        }
        List<E> list = new ArrayList<>();
        midTraver(root, list);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i - 1).compareTo(list.get(i)) > 0) {
                return false;
            }
        }
        return true;
    }
    
    public void midTraver(Node node, List<E> list) {
        if (node == null) {
            return;
        }
        midTraver(node.left, list);
        list.add(node.ele);
        midTraver(node.right, list);
    }

    //判断树是否为平衡二叉树
    public boolean isBalanceTree() {
        return isBalanceTree(root);
    }

    private boolean isBalanceTree(Node node) {
        if (node == null) {
            return true;
        }
        int balance = Math.abs(getBalance(node));
        if (balance > 1) {
            return false;
        }
        return isBalanceTree(node.left) && isBalanceTree(node.right);
    }
    
    //向二分搜索树种添加结点
    public void add(E ele) {
        //向以root为根的二分搜索树中添加元素
        root = add(root, ele);
        if (!isBalanceTree()) {
            System.out.println("是否二分搜索树:" + isSearchTree() + ",是否平衡二叉树:false");
        }
    }

    //向以head为根的二分搜索树中添加元素ele
    public Node add(Node head, E ele) {
        //递归到底的情况
        if (head == null) {
            Node node = new Node(ele);
            size++;
            return node;
        }
        //变成更小的同一问题
        if (head.ele.compareTo(ele) > 0) {
            head.left = add(head.left, ele);
        } else if (head.ele.compareTo(ele) < 0) {
            head.right = add(head.right, ele);
        }
        head.height = Math.max(getNodeHeight(head.left), getNodeHeight(head.right)) + 1;
        return head;
    }
}

(4)判断该树是否为平衡二叉树测试

使用set中的BSTSet来进行测试
SetDome保持不变
会发现此时添加的几乎都是二分搜索树

(5)AVL的左旋转和右旋转

维护平衡的时机
比如:插入的元素在不平衡结点的左侧的左侧
平衡二叉树的实现,需要用到旋转
无论添加还是删除都需要用到旋转
使用旋转后必须要更新节点高度先y在x
注:
- 右旋向上走,左旋向下走
RR如上图所示
- 需要向左倾斜右旋转
- 会发现5的平衡因子为0,8的平衡因子为1,12的平衡因子为2
- 此时需要用到右旋转将12节点放在8节点的右子节点位置上
LL如上图所示
- 需要向右倾斜左旋转
- 会发现12的平衡因子为0,8的平衡因子为1,5的平衡因子为2
- 此时需要用到左旋转将5节点放在8节点的左子节点位置上
  - RL如上图所示
- 需要先右旋转在左旋转(y<z<x)
- 先右旋转将x元素放在最下边也就是y的右子树为z,z的右子树为x
- 在直接进行左旋转即可
LR如上图所示
- 需要先左旋转在右旋转(y>z>x)此处y=12,z=10,x=8
- 先左旋转将x元素放在最下边也就是y的左子树为z,z的左子树为x
- 在直接进行右旋转即可

   //向左倾斜右旋转
    public Node rightTranslate(Node y) {
        Node x = y.left;
        Node T3 = x.right;
        x.right = y;
        y.left = T3;
        //更新节点高度先y在x
        y.height = 1 + Math.max(getNodeHeight(y.left), getNodeHeight(y.right));
        x.height = 1 + Math.max(getNodeHeight(x.left), getNodeHeight(x.right));
        return x; //返回的是根节点
    }

    //向右倾斜左旋转
    public Node leftTranslate(Node y) {
        Node x = y.right;
        Node T3 = x.left;
        x.left = y;
        x.right = T3;
        //更新节点高度先y在x
        y.height = 1 + Math.max(getNodeHeight(y.left), getNodeHeight(y.right));
        x.height = 1 + Math.max(getNodeHeight(x.left), getNodeHeight(x.right));
        return x; //返回的是根节点
    }

(5)AVL的增

首先需要先搞懂LL,RR,LR,RL,在上述以说明
AVL添加元素其实就是在二分搜索树的添加元素上作一些约束
- 即增加旋转
- 但是旋转也要旋转正确(抓住平衡因子)
如上图所示
- 看到第一眼就想要旋转是不行的(将图画出即可明白,会出现旋转变形)
- 但是请将其平衡因子标出
- 平衡因子的绝对值小于等于1位置的节点是不可进行旋转的,一旋转就失败
- 首先在平衡因子为-2位置的节点,不难发现一串数字7,8,9就可以进行左旋转
- 又或者看上图的平衡因子为2的节点,不难发现一串数字10,7,8不就是上面声明的LR.将头找对,即可发现规律
- 最后节点要对树的高进行维护

   //向二分搜索树种添加结点
    public void add(E ele) {
        //向以root为根的二分搜索树中添加元素
        root = add(root, ele);
        if (!isBalanceTree()) {
            System.out.println("是否二分搜索树:" + isSearchTree() + ",是否平衡二叉树:false");
        }
    }

    //向以head为根的二分搜索树中添加元素ele
    public Node add(Node head, E ele) {
        //递归到底的情况
        if (head == null) {
            Node node = new Node(ele);
            size++;
            return node;
        }
        //变成更小的同一问题
        if (head.ele.compareTo(ele) > 0) {
            head.left = add(head.left, ele);
        } else if (head.ele.compareTo(ele) < 0) {
            head.right = add(head.right, ele);
        }

        //右旋向上走,左旋向下走
        //LL
        if (getBalance(head) < -1 && getBalance(head.right) <= 0) {
            head = leftTranslate(head);
        } else if (getBalance(head) > 1 && getBalance(head.left) >= 0) {
            //RR
            head = rightTranslate(head);
        } else if (getBalance(head) > 1 && getBalance(head.left) < 0) {
            //LR
            head.left = leftTranslate(head.left);
            head = rightTranslate(head);
        } else if (getBalance(head) < -1 && getBalance(head.right) > 0) {
            //RL
            head.right = rightTranslate(head.right);
            head = leftTranslate(head);
        }
        head.height = Math.max(getNodeHeight(head.left), getNodeHeight(head.right)) + 1;
        return head;
    }

(6)AVL的删

删和增异曲同工
都是需要进行树的维护但有三点需要注意
- 首先保存删除节点后的根节点Node returnNode;
- 最后删除的节点也可能是最后一个节点,需要对其进行维护,即返回空
  - if (returnNode == null) {
    return null;
    }
- 最后就是删除所查找的不是最小结点,而是任意节点
  - Node tempNode = removeElement(node.right, preNode.ele);

// 从二分搜素树中删除任意结点
    public void removeElement(E ele) {
        // 1、找到删除的结点
        Node delNode = searchEle(root, ele);
        if (delNode == null) {
            throw new IllegalArgumentException("cann't find delNode！");
        }
        root = removeElement(root, ele);
    }

    // 从以node为根的二分搜索树中删除ele所在的结点
    private Node removeElement(Node node, E ele) {
        // 递归到底的情况
        if (node == null) {
            return null;
        }
        Node returnNode;
        if (node.ele.compareTo(ele) > 0) {
            node.left = removeElement(node.left, ele);
            returnNode = node;
        } else if (node.ele.compareTo(ele) < 0) {
            node.right = removeElement(node.right, ele);
            returnNode = node;
        } else {
            /**
             * node结点就是就是要删除的结点
             * 2.找到待删除的结点
             * 1>只有左子树
             * 2>只有右子树
             * 3>左右子树都不为空(Hibbaed Deletion)
             */
            if (node.left == null) {
                //获取到右子树
                Node rightNode = node.right;
                size--;
                node.right = null;
                returnNode = rightNode;
            } else if (node.right == null) {
                //获取到左子树
                Node leftNode = node.left;
                size--;
                node.left = null;
                returnNode = leftNode;
            } else {
                //左右子树都不为空
                //1.找到待删除的结点
                //2.从待删除结点的右孩子中找到最小结点
                Node preNode = mixElement(node.right);
                // 3、从待删除结点的右子树中删除最小结点
                Node tempNode = removeElement(node.right, preNode.ele);
                //4.重新组装前驱preNode即让待删除结点的后继替换待删除结点
                preNode.right = tempNode;
                preNode.left = node.left;
                node.left = node.right = null;
                returnNode = preNode;
            }
        }
        //维护平衡
        if (returnNode == null) {
            return null;
        }
        //右旋向上走,左旋向下走
        //LL
        if (getBalance(returnNode) < -1 && getBalance(returnNode.right) <= 0) {
            returnNode = leftTranslate(returnNode);
        } else if (getBalance(returnNode) > 1 && getBalance(returnNode.left) >= 0) {
            //RR
            returnNode = rightTranslate(returnNode);
        } else if (getBalance(returnNode) > 1 && getBalance(returnNode.left) < 0) {
            //LR
            returnNode.left = leftTranslate(returnNode.left);
            returnNode = rightTranslate(returnNode);
        } else if (getBalance(returnNode) < -1 && getBalance(returnNode.right) > 0) {
            //RL
            returnNode.right = rightTranslate(returnNode.right);
            returnNode = leftTranslate(returnNode);
        }
        returnNode.height = Math.max(getNodeHeight(returnNode.left), getNodeHeight(returnNode.right)) + 1;
        return returnNode;
    }

红黑树

(1)2-3树的引进

满足二分搜索树的基本性质
结点可以存放一个元素或者两个元素
- 因此：每个结点有2个或3个孩子
由下图得2-3树是一棵绝对平衡的树

(2)2-3树如何维护平衡的

二叉树的平衡维护1

如上图
- 先添加第一个元素42,不发生变化
- 在添加第二个元素37,形成一个节点存放俩个元素
- 在添加第二个元素12,形成一个节点存放三个元素
- 可以直接分裂成二分搜索树的样式
如上图
- 添加元素12后,可以进行组合在分裂
- 组合成一个节点存三个元素,而子节点共4个元素
- 变成124的样式可以直接分裂成为二分搜索树的样式

(3)红黑树的引进

红黑树与2-3树的等价
如上图所示(可以这样理解)
- 上图2-3树,后续共插入了3个节点,6,17,66
- 将此三个节点由黑转红
- 在分裂至下一次(即红黑树的维护)
注:
- 所有的红色节点都是左倾的 (要么全左倾,要么全右倾不可发生任何改变)
- 红色结点向左倾斜
- 红色结点表示融合的结点

(4)红黑树的性质即原理

每个节点不是红色就是黑色
根节点全是黑色的
每一个叶子结点(最后的空节点)都是黑色的
如果一个节点是红色的,那么他的孩子节点都是黑色的
从任意一个节点到叶子结点,经过的黑色节点是一样的
注:
- 叶子结点一定是最后的空节点
如上图所示
- 此树非红黑树
- 12节点也可以拥有一个假想的空叶子结点
- 那么从15节点开始到5节点下方的叶子节点共4个黑色节点
- 从15节点到12节点下方的叶子节点共3个黑色节点
- 4!=3
- 所以该树不是红黑树

(5)红黑树与平衡二叉树的区别

红黑树不是平衡二叉树，而是保持“黑平衡”的二叉树
时间复杂度不同
- 红黑树的时间复杂度为O(2logn)
- 平衡二叉树的时间复杂度为O(logn)
因为红黑树是黑平衡的二叉树,万一一个黑节点一个红节点,取最大值即高为2h,时间复杂度即O(2logn)

(6)初始化红黑树

我们由改版形成,源代码请看二分搜索树

初始化黑色和红色
初始化节点，给予节点红黑判断
- 构造方法中，默认节点是红色的,因为二叉树不能向空节点添加元素，所以当我们需要添加元素时,添加的元素默认为红节点
获取结点的颜色

    private static final boolean BLACK = false;
    private static final boolean RED = true;

    //结点的数据结构
    private class Node {
        E ele;
        Node left; //左孩子
        Node right;//右孩子
        Boolean isRed;//节点是不是红色

        //构造方法
        public Node(E ele) {
            this.ele = ele;
            left = null;
            right = null;
            isRed = RED;//默认是红色节点,因为二叉树不能向空节点添加元素我们需要添加元素,添加的元素默认为红节点
        }

        public Node() {
            this(null);
        }
    }
    
    //获取颜色的方法
    private Boolean getNodeColor(Node node) {
        if (node == null) {
            return false;
        }
        return node.isRed;
    }

(7)红黑树的左旋转和右旋转

红黑树是黑平衡树，带有二叉树的部分特性，所以也需要旋转，
但是红黑树中红不平衡，所以需要颜色转换和颜色翻转

左旋转

左旋转
- 如上图所示原理同平衡二叉树一致
- 每次旋转后需要更改节点颜色

颜色翻转.png

颜色翻转
- 已有42节点，插入37和66节点
- 理解成为37,42,66三个元素共一个节点的2-3树
- 在将其分裂变成3个节点，此时42为黑色节点，37和66为红色节点，需要节点颜色转换即颜色翻转
右旋转
- 每次旋转后需要更改节点颜色，即37改为红色节点12和42为黑色节点
- 原理同平衡二叉树一致

 //左旋转+颜色转换
    private Node leftTranslate(Node node) {
        Node x = node.right;
        Node T2 = x.left;
        node.right = T2;
        x.left = node;

        //颜色转换
        x.isRed = node.isRed;
        node.isRed = RED;
        return x;
    }

    //右旋转+颜色转换
    private Node rightTranslate(Node node) {
        Node x = node.left;
        Node T1 = x.right;
        node.left = T1;
        x.right = node;

        //颜色转换
        x.isRed = node.isRed;
        node.isRed = RED;
        return x;
    }

    //颜色翻转
    private void flipColor(Node node) {
        node.isRed = RED;
        node.left.isRed = node.right.isRed = BLACK;

    }

(8)红黑树的添加

首先必须保证根节点为黑色
红黑树的增需要满足三个情况
左旋转，右旋转，颜色翻转，三者不可缺少相辅相成
左旋转
- 当前节点的右子节点为红色
- 当前节点的左子节点不为红色
- 时发生旋转
右旋转
- 当前节点的左子节点为红色
- 当前节点的左子节点的左子节点为红色
- 时发生旋转
颜色翻转
- 当前节点的左子节点为红色
- 当前节点的右子节点为红色
- 时发生颜色翻转
三者配合可以面对LL，RL等一切情况

//向红黑树中添加结点
    public void add(E ele) {
        //向以root为根的红黑树中添加元素
        root = add(root, ele);
        //保证根节点为黑色
        if (root != null) {
            root.isRed = BLACK;
        }
    }

    //向以head为根的红黑树中添加元素ele
    public Node add(Node head, E ele) {
        //递归到底的情况
        if (head == null) {
            Node node = new Node(ele);
            size++;
            return node;
        }
        //变成更小的同一问题
        if (head.ele.compareTo(ele) > 0) {
            head.left = add(head.left, ele);
        } else if (head.ele.compareTo(ele) < 0) {
            head.right = add(head.right, ele);
        }
        Node resuslt = head;

        //是否满足左旋转
        if (getNodeColor(resuslt.right) && !getNodeColor(resuslt.left)) {
            resuslt = leftTranslate(resuslt);
        }
        //是否满足右旋转
        if (getNodeColor(resuslt.left) && getNodeColor(resuslt.left.left)) {
            resuslt = rightTranslate(resuslt);
        }
        //是否颜色翻转
        if (getNodeColor(resuslt.left) && getNodeColor(resuslt.right)) {
            flipColor(resuslt);
        }
        return resuslt;
    }

(9)红黑树的删除

删和增异曲同工
都是需要进行树的维护但有三点需要注意
- 首先保存删除节点后的根节点Node resuslt ;
- 最后删除的节点也可能是最后一个节点,需要对其进行维护,即返回空
  - if (resuslt ==null){
    return null;
    }
- 最后就是删除所查找的不是最小结点,而是任意节点
  - Node tempNode = removeElement(node.right,ele);

// 从二分搜素树中删除任意结点
    public void removeElement(E ele) {
        // 1、找到删除的结点
        Node delNode = searchEle(root, ele);
        if (delNode == null) {
            throw new IllegalArgumentException("cann't find delNode！");
        }
        root = removeElement(root, ele);
    }

    // 从以node为根的二分搜索树中删除ele所在的结点
    private Node removeElement(Node node, E ele) {
        // 递归到底的情况
        if (node == null) {
            return null;
        }
        Node resuslt;
        if (node.ele.compareTo(ele) > 0) {
            node.left = removeElement(node.left, ele);
            resuslt= node;
        } else if (node.ele.compareTo(ele) < 0) {
            node.right = removeElement(node.right, ele);
            resuslt= node;
        } else {
            /**
             * node结点就是就是要删除的结点
             * 2.找到待删除的结点
             * 1>只有左子树
             * 2>只有右子树
             * 3>左右子树都不为空(Hibbaed Deletion)
             */
            if (node.left == null) {
                //获取到右子树
                Node rightNode = node.right;
                size--;
                node.right = null;
                resuslt= rightNode;
            } else if (node.right == null) {
                //获取到左子树
                Node leftNode = node.left;
                size--;
                node.left = null;
                resuslt= leftNode;
            } else {
                //左右子树都不为空
                //1.找到待删除的结点
                //2.从待删除结点的右孩子中找到最小结点
                Node preNode = mixElement(node.right);
                // 3、从待删除结点的右子树中删除最小结点
                Node tempNode = removeElement(node.right,ele);
                //4.重新组装前驱preNode即让待删除结点的后继替换待删除结点
                preNode.right = tempNode;
                preNode.left = node.left;
                node.left = node.right = null;
                resuslt= preNode;
            }
        }
        //对删除之后以result为根的树进行相关的操作
        if (resuslt ==null){
            return null;
        }
        //是否满足左旋转
        if (getNodeColor(resuslt.right) && !getNodeColor(resuslt.left)) {
            resuslt = leftTranslate(resuslt);
        }
        //是否满足右旋转
        if (getNodeColor(resuslt.left) && getNodeColor(resuslt.left.left)) {
            resuslt = rightTranslate(resuslt);
        }
        //是否颜色翻转
        if (getNodeColor(resuslt.left) && getNodeColor(resuslt.right)) {
            flipColor(resuslt);
        }
        return resuslt;
    }