AVL树&红黑树&位图&布隆过滤器&并查集&B树&图

AVL树

二叉树在数据有序时,会变成单链表,使得搜索效率极大的降低,为了维持二叉树的搜索特性,使得整体保持平衡,从而诞生二叉搜索树

AVL树的插入&旋转&验证

public class AVLTree {    public static void main(String[] args) {        AVLTree avlTree = new AVLTree();        int[] arr = {4, 2, 6, 1, 3, 5, 15, 7, 16,14};        for (int i = 0; i  curNode.val) {                curNode = curNode.left;            } else if (nTreeNode.val  prevNode.val) {            prevNode.right = nTreeNode;        } else {            prevNode.left = nTreeNode;        }        //修改平衡因子        while (prevNode != null) {            curNode = nTreeNode;            prevNode = curNode.parent;            if (prevNode.right == curNode) {                prevNode.balanceFactor++;            } else {                prevNode.balanceFactor--;            }            if (prevNode.balanceFactor == 0) {                //平衡因子为0,树的高度没有发生变化,不影响上面树的平衡因子                return true;            } else if (prevNode.balanceFactor == -1 || prevNode.balanceFactor == 1) {            } else {                if (prevNode.balanceFactor == 2) {                    if (curNode.balanceFactor == 1) {                        leftRotation(prevNode);                    } else {                        LRrotation(prevNode);                    }                } else {                    //prevNode.balanceFactor == -2                    if (curNode.balanceFactor == 1) {                        RLrotation(prevNode);                    } else {                        rightRotation(prevNode);                    }                }                break;            }        }        return true;    }    private void RLrotation(TreeNode prevNode) {        TreeNode Rnode = prevNode.right;        TreeNode RLnode = Rnode.left;        int bf = RLnode.balanceFactor;        rightRotation(Rnode);        leftRotation(prevNode);        if (bf == 1) {            prevNode.balanceFactor = -1;            Rnode.balanceFactor = 0;            RLnode.balanceFactor = 0;        } else if (bf == -1) {            prevNode.balanceFactor = 0;            RLnode.balanceFactor = 0;            Rnode.balanceFactor = 1;        }    }    private void LRrotation(TreeNode prevNode) {        TreeNode Lnode = prevNode.left;        TreeNode LRnode = Lnode.right;        int bf = LRnode.balanceFactor;        leftRotation(Lnode);        rightRotation(prevNode);        if (bf == 1) {            prevNode.balanceFactor = 0;            LRnode.balanceFactor = 0;            Lnode.balanceFactor = -1;        } else if (bf == -1) {            prevNode.balanceFactor = 1;            Lnode.balanceFactor = 0;            LRnode.balanceFactor = 0;        }    }    private static void leftRotation(TreeNode parent) {        TreeNode Rpaernt = parent.right;        TreeNode RLparent = parent.right.left;        TreeNode Ppaernt = parent.parent;        parent.parent = Rpaernt;        parent.right = RLparent;        if (RLparent != null) {            RLparent.parent = parent;        }        Rpaernt.left = parent;        //判断是不是根结点        if (parent == root) {            root = Rpaernt;            root.parent = null;        } else {            if (Rpaernt.val  Lparent.val) {                pParent.left = Lparent;            } else {                pParent.right = Lparent;            }        }        Lparent.balanceFactor = 0;        pParent.balanceFactor = 0;    }    /**     * 中序遍历     */    public static void inorderTree(TreeNode root) {        if (root == null) {            return;        }        inorderTree(root.left);        System.out.print(root.val + " ");        inorderTree(root.right);    }    private static int getHeight(TreeNode node) {        if (node == null) {            return 0;        }        int leftH = getHeight(node.left);        int rightH = getHeight(node.right);        return leftH > rightH ? leftH + 1 : rightH + 1;    }    public static boolean isBalanced(TreeNode root) {        if (root == null) return true;        int leftH = getHeight(root.left);        int rightH = getHeight(root.right);        if (rightH - leftH != root.balanceFactor) {            return false;        }        return Math.abs(root.balanceFactor)  val) {                cur = cur.left;            } else if (cur.val  prev.val) {            prev.right = node;        } else {            prev.left = node;        }        node.parent = prev;        cur = node;        //进行颜色调整        while (prev != null && prev.color == Color.Red) {            //prev节点是红色,必存在祖父节点            rbTreeNode grandfather = prev.parent;            if (prev == grandfather.left) {                rbTreeNode uncle = grandfather.right;                if (uncle != null && uncle.color == Color.Red) {                    prev.color = Color.Black;                    uncle.color = Color.Black;                    grandfather.color = Color.Red;                    cur = grandfather;                    prev = cur.parent;                } else {                    //叔叔节点为空或者叔叔节点的颜色是黑色                    //右旋                    if (cur == prev.right) {                        left(prev);                        rbTreeNode tmp = cur;                        cur = prev;                        prev = tmp;                    }                    right(grandfather);                    grandfather.color = Color.Red;                    prev.color = Color.Black;                }            } else {                rbTreeNode uncle = grandfather.left;                if (uncle != null && uncle.color == Color.Red) {                    prev.color = Color.Black;                    uncle.color = Color.Black;                    grandfather.color = Color.Red;                    cur = grandfather;                    prev = cur.parent;                } else {                    //叔叔节点为空或者叔叔节点的颜色是黑色                    //右旋                    if (cur == prev.left) {                        right(prev);                        rbTreeNode tmp = cur;                        cur = prev;                        prev = tmp;                    }                    left(grandfather);                    grandfather.color = Color.Red;                    prev.color = Color.Black;                }            }        }        root.color = Color.Black;        return true;    }    public static void inOrder(rbTreeNode root) {        if(root==null) {            return;        }        inOrder(root.left);        System.out.print(root.val+" ");        inOrder(root.right);    }    private static void left(rbTreeNode node) {        rbTreeNode Rnode = node.right;        rbTreeNode RLnode = Rnode.left;        rbTreeNode pPnode = node.parent;        Rnode.left = node;        node.right = RLnode;        node.parent = Rnode;        if (RLnode != null) {            RLnode.parent = node;        }        //是不是根结点        if (node == root) {            //是根节点            root = Rnode;            Rnode.parent = null;        } else {            if (pPnode.left == node) {                pPnode.left = Rnode;            } else {                pPnode.right = Rnode;            }            Rnode.parent = pPnode;        }    }    private static void right(rbTreeNode node) {        rbTreeNode Lnode = node.left;        rbTreeNode LRnode = Lnode.right;        rbTreeNode pPnode = node.parent;        Lnode.right = node;        node.left = LRnode;        node.parent = Lnode;        if (LRnode != null) {            LRnode.parent = node;        }        //是不是根结点        if (node == root) {            //是根节点            root = Lnode;            Lnode.parent = null;        } else {            if (pPnode.left == node) {                pPnode.left = Lnode;            } else {                pPnode.right = Lnode;            }            Lnode.parent = pPnode;        }    }    public static boolean isRBTree(rbTreeNode root) {        if (root == null) {            return true;        }        if(root.color!=Color.Black) {            System.out.println("违反性质: 根结点的颜色是黑色");            return false;        }        //判断是否存在连续红色节点,可以根据每个红色节点是否有父红色节点来判断        if (!isRed(root)) {            System.out.println("违法了性质: 红黑树不存在两个连续的红色节点");            return false;        }        int blacknum = 0;        rbTreeNode cur = root;        while (cur != null) {            if (cur.color == Color.Black) {                blacknum++;            }            cur = cur.left;        }        int pathnum = 0;        if (!blackNum(root, blacknum, pathnum)) {            System.out.println("违反性质: 每条路径的黑色节点数目相同");            return false;        }        return true;    }    private static boolean blackNum(rbTreeNode root, int blacknum, int pathnum) {        if (root == null) {            return true;        }        if (root.color == Color.Black) {            pathnum++;        }        if (root.left == null && root.right == null ) {            if(pathnum != blacknum) {                System.out.println(root.val);                return false;            }        }        return blackNum(root.left, blacknum, pathnum) && blackNum(root.right, blacknum, pathnum);    }    private static boolean isRed(rbTreeNode root) {        if (root == null) {            return true;        }        if (root.color == Color.Red && root.parent.color == Color.Red) {            return false;        }        return isRed(root.left) && isRed(root.right);    }}

位图

位图是为了在海量数据中,整数且无重复的场景进行对某个数据存在的判断

实现

public class BitMap {    byte[] elements;    int usedSize;    public BitMap(int num) {        elements = new byte[num / 8 + 1];    }    public void insert(int val) {        if (val  elements.length - 1) {            elements = Arrays.copyOf(elements, elements.length + 1);        }        int bitIndex = val % 8;        elements[byteIndex] |= (1  elements.length - 1) {            System.out.println("坐标越界违法");            return false;        }        int bitIndex = val % 8;        if (((elements[byteIndex]) & (1  elements.length - 1) {            System.out.println("坐标越界违法");            return;        }        int bitIndex = val % 8;        elements[byteIndex] &= ~(1 capacity) {                //头删                int headKey = deleteHead().key;                map.remove(headKey);                usedSize--;            }        } else {            //存在该元素            node.value = value;            //删除该元素            deleteNode(node);            //尾插元素            insertTail(node);        }    }    private DLinkNode deleteHead() {        DLinkNode del = head.next;        head.next = del.next;        del.next.prev = head;        return del;    }    public int get(int key) {        DLinkNode node = map.get(key);        if (node == null) {            //不存在            return -1;        }        deleteNode(node);        insertTail(node);        return node.value;    }    private void deleteNode(DLinkNode node) {        node.prev.next = node.next;        node.next.prev = node.prev;    }    private void insertTail(DLinkNode newNode) {        DLinkNode tmpNode = tail.prev;        tail.prev = newNode;        newNode.next = tail;        newNode.prev = tmpNode;        tmpNode.next = newNode;    }    private void print() {        DLinkNode cur = head.next;        while (cur != tail) {            System.out.print(cur.value + " ");            cur = cur.next;        }        System.out.println();    }    public static void main(String[] args) {        LRUCache lruCache = new LRUCache(3);        lruCache.put(100, 10);        lruCache.put(110, 11);        lruCache.put(120, 12);        System.out.println("获取元素");        lruCache.print();        System.out.println(lruCache.get(110));        lruCache.print();        System.out.println(lruCache.get(100));        lruCache.print();        System.out.println("存放元素,会删除头节点，因为头节点是最近最少使用的: ");        lruCache.print();        lruCache.put(999, 99);        lruCache.print();    }}

B-树

当数据量非常大时,对文件进行搜索,无法将数据都加载到内存,我们使用平衡二叉树,节点存储搜索有关的数据量和原数据的地址,搜索最差效率与树的高度有关,而且当你要搜索的数据量大时,节点内存无法存储,需要多次IO进行

所以我们可以从提高IO效率和减少树的高度来提高搜索的效率

数据存储到HashMap和存储到文件中,有什么区别?

1. HashMap存储在内存中,读取速度快

2. HashMap数据因为存储到内存中,所以断电丢失

M叉树的孩子节点M个,存储M-1个数据,但是为了后面分裂的方便,我们将多添加一个孩子节点和一个数据,那么就是M+1个孩子,存储M个数据,因为我们判断分裂的条件是当要插入数据时,存储数据个数等于M-1个数据,就需要进行分裂,但是因为你加上原来要插入的数据是M个,但是节点只能存储M-1,这就需要我们对于中间节点进行分类讨论判断,如果你多添加一个数据,就会多留出一个位置用于排序,直接对中间和两边的数据进行分裂即可

总结:

M叉树

1. 根结点关键字的数量范围[1,M-1],孩子节点的数量[2,M]

2. 非根结点关键字的数量范围[M/2-1,M-1],孩子节点数量[M/2,M];

3. 孩子节点的数量总是比关键字数量多1

B树满的时候会进行分裂,新节点和老节点在同一层,根结点分裂会增加树的高度,B树是天然平衡的

B-树插入实现

public class bTree {    class bTreeNode {        int[] keys;        int usedSize;        bTreeNode[] childs;        bTreeNode parent;        public bTreeNode() {            keys = new int[M];            childs = new bTreeNode[M + 1];        }    }    public static final int M = 3;    bTreeNode root;    public boolean insert(int val) {        //B树为空,直接插入        if (root == null) {            root = new bTreeNode();            root.keys[0] = val;            root.usedSize++;            return true;        }        //B树不为空        //判断树里有没有这个值        Pair pair = findVal(val);        //根据value值判断这个值是不是在树中        if (pair.getValue() != -1) {            //等于-1,不存在该值            //不等于,存在该值            //存在该值无法进行插入,退出返回false            return false;        }        bTreeNode parent = pair.getKey();        //进行插入        int index = parent.usedSize - 1;        while (index >= 0) {            if (val = M) {            split(parent);        }        return true;    }    /**     * 表示当前要分裂的节点     *     * @param sNode     */    private void split(bTreeNode sNode) {        bTreeNode newNode = new bTreeNode();        bTreeNode psNode = sNode.parent;        //分裂节点的父节点        //对分裂节点区域进行划分        int i = 0;        int mid = sNode.usedSize / 2;        int j = mid + 1;        while (j = 0) {            if (sNode.parent.keys[fIndexEnd] > midValue) {                sNode.parent.keys[fIndexEnd + 1] = sNode.parent.keys[fIndexEnd];                sNode.parent.childs[fIndexEnd + 2] = sNode.parent.childs[fIndexEnd + 1];            } else {                break;            }            fIndexEnd--;        }        psNode.keys[fIndexEnd + 1] = midValue;        psNode.childs[fIndexEnd + 2] = newNode;        psNode.usedSize++;        if (psNode.usedSize >= M) {            split(psNode);        }    }    private Pair findVal(int val) {        bTreeNode cur = root;        bTreeNode parent = null;        while (cur != null) {            int i = 0;            while (i  
B+树
 
B+树特点:
 
使用B+树搜索数据一定要遍历整个树的高度,B树不一定
 
对于结构而言,非叶子节点存储K值,叶子节点存储K,V值
 
内存读取速度快,硬盘速度相较于较慢,从硬盘读取数据到内存,但是硬盘读取太慢了,内存的高速就无法发挥用处,需要使用缓存,让硬盘一次性读取很多数据,然后内存再从缓存中读取,减少IO次数,提高效率
 
图
 
图是由顶点集合和顶点关系组成的一种数据结构
 
图包括有向图和无向图
 
无向图边的条数到达N*(N-1)/2时,称为无向完全图,有向图则是达到N*(N-1)为有向完全图
 
树是一种特殊的图,图不一定是树
 
无向图的邻接矩阵是沿着对角线对称的,有向图不一定
 
邻接矩阵
 
import java.util.Arrays;/** * 邻接矩阵 */public class GraphByMatrix {    private char[] arrayV;//顶点数组    private int[][] matrix;    private boolean isDirect;    /**     * @param size   顶点个数     * @param Direct 是否是有向图     */    public GraphByMatrix(int size, boolean Direct) {        arrayV = new char[size];        matrix = new int[size][size];        //使得二维数组矩阵用无穷大来进行初始化        for (int i = 0; i  
邻接表
 
import java.util.ArrayList;public class GraphByNode {    static class Node {        public int src;//起点        public int dest;//终点        public int weight;//权重        public Node next;        public Node(int src, int dest, int weight) {            this.src = src;            this.dest = dest;            this.weight = weight;        }    }    public char[] arrayV;    public ArrayList edgList;//存储边    public boolean isDirect;    public GraphByNode(boolean isDirect, int size) {        this.arrayV = new char[size];        edgList = new ArrayList(size);        for (int i = 0; i " + arrayV[cur.dest]);                cur = cur.next;            }            System.out.println();        }    }    public int getDevOfV(char v) {        int srcIndex = getIndexOfV(v);        int count = 0;        Node cur = edgList.get(srcIndex);        while (cur != null) {            count++;            cur = cur.next;        }        //有向图额外考虑入度        if (isDirect) {            for (int i = 0; i  
深度优先遍历&广度优先遍历
 
/**     * 广度优先遍历     *     * @param v     */    public void bfs(char v) {        //得到起点的坐标        int src = getIndexOfV(v);        //标记是否出现过        boolean[] visited = new boolean[arrayV.length];        Queue queue = new LinkedList();        queue.offer(src);        while (!queue.isEmpty()) {            int top = queue.poll();            System.out.print("->" + arrayV[top]);            //弹出置为true            visited[top] = true;            for (int i = 0; i ");        visited[index] = true;        for (int i = 0; i