数据结构

一、栈

先进后出

二、队列

先进先出

三、数组

查询快,增加修改慢

四、链表

查询慢,增加修改慢

五、二叉树

节点:

查找二叉树

二叉查找树的特点

  • 二叉查找树,又称二叉排序树或者二叉搜索树

  • 每一个节点上最多有两个子节点

  • 左子树上所有节点的值都小于根节点的值

  • 右子树上所有节点的值都大于根节点的值

二叉查找树添加节点规则

  • 小的存左边

  • 大的存右边

  • 一样的不存

数据结构(二叉树)遍历方式

  1. 前序遍历:当前节点,左子节点,右子结点
  2. 中序遍历:左子节点,当前节点,右子结点
  3. 后序遍历:左子节点,右子结点,当前节点
  4. 层序遍历:一层一层的去遍历

平衡二叉树

特点

  • 二叉树左右两个子树的高度差不超过1

  • 任意节点的左右两个子树都是一颗平衡二叉树

平衡二叉树旋转

  • 旋转触发时机

    • 当添加一个节点之后,该树不再是一颗平衡二叉树

  • 左旋

    • 确定支点:从添加的节点开始,不断的往父节点找不平衡的节点

    以不平衡的点作为支点
    将根节点的右侧往左拉
    原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点

右旋

  • 确定支点:从添加的节点开始,不断的往父节点找不平衡的节点

以不平衡的点作为支点
就是将根节点的左侧往右拉
原先的左子节点变成新的父节点,并把多余的右子节点出让,给已经降级的根节点当左子节点

平衡二叉树旋转的四种情况

左左

  • 左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡

  • 如何旋转: 直接对整体进行右旋即可

左右

  • 左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡

  • 如何旋转: 先在左子树对应的节点位置进行左旋,再对整体进行右旋

右右

  • 右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡

  • 如何旋转: 直接对整体进行左旋即可

右左

  • 右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡

  • 如何旋转: 先在右子树对应的节点位置进行右旋,再对整体进行左旋

红黑树

红黑树的特点

红黑树的增删改查性能都很好

  • 平衡二叉B树

  • 每一个节点可以是红或者黑

  • 红黑树不是高度平衡的,它的平衡是通过"自己的红黑规则"进行实现的

节点

红黑规则

  1. 每一个节点是红色的,或者是黑色的
  2. 根节点必须是黑色
  3. 叶节点是黑色的
  4. 两个红色节点不能相连
  5. 任意节点到所有后代叶节点的简单路径上,黑色节点数量相同;

红黑树结构图

红黑树添加节点的默认颜色

  • 添加节点时,默认为红色,效率高

红黑树添加节点后如何保持红黑规则

  • 根节点位置

    • 直接变为黑色

  • 非根节点位置

    • 父节点为黑色

      • 不需要任何操作,默认红色即可

    • 父节点为红色

      • 叔叔节点为红色

        1. 将"父节点"设为黑色,将"叔叔节点"设为黑色

        2. 将"祖父节点"设为红色

        3. 如果"祖父节点"为根节点,则将根节点再次变成黑色

      • 叔叔节点为黑色

        1. 将"父节点"设为黑色

        2. 将"祖父节点"设为红色

        3. 以"祖父节点"为支点进行旋转

实现代码

public class RBTree {
    class Node {
        int val, color;
        Node left, right;
    }
//    使用NIL节点来充当叶节点
    Node NIL;
    Node root;

    public RBTree() {
        NIL = new Node();
        NIL.val = -1;
        NIL.color = 1;
        NIL.left = NIL.right = NIL;
        root = NIL;
    }
    // 创建节点
    private Node getNewNode(int val) {
        Node p = new Node();
        p.val = val;
        p.color = 0;
        p.left = p.right = NIL;
        return p;
    }
    //判断有没有红色孩子
    private boolean has_red_child(Node tree) {
        return tree.left.color == 0 || tree.right.color == 0;
    }
    //左旋
    private Node left_rotate(Node tree) {
        Node temp = tree.right;
        tree.right = temp.left;
        temp.left = tree;
        return temp;
    }
    //右旋
    private Node right_rotate(Node tree) {
        Node temp = tree.left;
        tree.left = temp.right;
        temp.right = tree;
        return temp;
    }

    //寻找前驱
    private Node preNode(Node tree) {
        Node p = tree.left;
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }
    //删除
    public void erase(int val) {
        root = erase(root, val);
    }

    private Node erase(Node tree, int val) {
        tree = __erase(tree, val);
        tree.color = 1;
        return tree;
    }

    private Node __erase(Node tree, int val) {
        if (tree == NIL) return tree;
        if (val < tree.val) {
            tree.left = __erase(tree.left, val);
        } else if (val > tree.val) {
            tree.right = __erase(tree.right, val);
        } else {
            if (tree.left == NIL || tree.right == NIL) {
                Node temp = tree.left == NIL ? tree.right : tree.left;
                temp.color += tree.color;
                tree = temp;
                return tree;
            } else {
                Node temp = preNode(tree);
                tree.val = temp.val;
                tree.left = __erase(tree.left, temp.val);
            }
        }
        return erase_maintion(tree);
    }
    //删除调整
    private Node erase_maintion(Node tree) {
        if (tree.left.color != 2 && tree.right.color != 2) return tree;
//        兄弟为红,旋转树,新根节点转为黑,原根节点转为红
        if (has_red_child(tree)) {
            int flag = 0;
            tree.color = 0;
            if (tree.left.color == 0) {
                tree = right_rotate(tree);
                flag = 1;
            } else {
                tree = left_rotate(tree);
            }
            tree.color = 1;
            if (flag == 1) tree.right = erase_maintion(tree.right);
            else tree.left = erase_maintion(tree.left);
            return tree;
        }
//        兄弟为黑色并且没有红色子节点,子节点减黑,根节点加黑
        if (tree.left.color == 1 && !has_red_child(tree.left)
                || tree.right.color == 1 && !has_red_child(tree.right)) {
            tree.color += 1;
            tree.left.color -= 1;
            tree.right.color -= 1;
            return tree;
        }
//        兄弟节点为黑并且有红色子节点
//            |-- 左子树为黑色
//              |-- 左子树的右子树为红色且左子树节点为黑 LR
//                  |-- 子树小左旋,新节点转黑,原节点转红,进入LL形态
//              |-- 左子树的左子树为红色 LL
//                  |-- 整树右旋,新节点改为原根节点的颜色,原根节点已经新叔叔节点转为黑色
//            |-- 右子树为黑色
//              |-- 右子树的左子树为红色且右子树节点为黑 RL
//                  |-- 子树小右旋,新节点转黑,原节点转红,进入RR形态
//              |-- 右子树的右子树为红色 RR
//                  |-- 整树左旋,新节点改为原根节点的颜色,原根节点已经新叔叔节点转为黑色
        if (tree.left.color == 1) {
            tree.right.color = 1;
            if (tree.left.left.color != 0) {
                tree.left.color = 0;
                tree.left = left_rotate(tree.left);
                tree.left.color = 1;
            }
            tree.left.color = tree.color;
            tree = right_rotate(tree);
        } else {
            tree.left.color = 1;
            if (tree.right.right.color != 0) {
                tree.right.color = 0;
                tree.right = right_rotate(tree.right);
                tree.right.color = 1;
            }
            tree.right.color = tree.color;
            tree = left_rotate(tree);
        }
        tree.left.color = 1;
        tree.right.color = 1;
        return tree;
    }
    //添加
    public void insert(int val) {
        root = insert(root, val);
    }

    private Node insert(Node tree, int val) {
        tree = __insert(tree, val);
        tree.color = 1;
        return tree;
    }

    private Node __insert(Node tree, int val) {
        if (tree == NIL) {
            return getNewNode(val);
        }
        if (val < tree.val) {
            tree.left = __insert(tree.left, val);
        } else if (val > tree.val) {
            tree.right = __insert(tree.right, val);
        }
        return insert_maintain(tree);
    }
    //添加调整
    private Node insert_maintain(Node tree) {
        if (!has_red_child(tree)) return tree;
        //节点双红
        if (tree.left.color == 0 && tree.right.color == 0) {
            if (!has_red_child(tree.left) && !has_red_child(tree.right)) return tree;
            tree.color = 0;
            tree.left.color = tree.right.color = 1;
            return tree;
        }
        if (tree.left.color == 0 && !has_red_child(tree.left)) return tree;
        if (tree.right.color == 0 && !has_red_child(tree.right)) return tree;
        // 左子树失衡
        if (tree.left.color == 0) {
            if (tree.left.right.color == 0) {
                tree.left = left_rotate(tree.left);
            }
            tree = right_rotate(tree);
        } else {
            if (tree.right.left.color == 0) {
                tree.right = right_rotate(tree.right);
            }
            tree = left_rotate(tree);
        }
        tree.color = 0;
        tree.left.color = tree.right.color = 1;
        return tree;
    }
    //打印输出
    public void preorder() {
        preorder(root, root.val, 0);
    }

    private void preorder(Node tree, int val, int flag) {
        if (tree == NIL) return;
        if (flag == 0) {
            System.out.printf("%d is root, color is %s\n", val, tree.color == 0 ? "red" : "black");
        } else {
            System.out.printf("%d is %d's %s child, color is %s\n"
                    , tree.val, val, flag == 1 ? "right" : "left", tree.color == 0 ? "red" : "black");
        }
        preorder(tree.left, tree.val, -1);
        preorder(tree.right, tree.val, 1);

    }
}

上一篇:在CentOS 7中查看哪个文件夹占用的磁盘空间最大


下一篇:深度学习十大算法之图神经网络(GNN)