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
文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。
