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 < arr.length; i++) {
avlTree.insert(arr[i]);
}
System.out.println(isBalanced(root));
}
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode parent;
public int balanceFactor;
public TreeNode(int val) {
this.val = val;
}
}
public static TreeNode root;
public boolean insert(int val) {
TreeNode nTreeNode = new TreeNode(val);
//前部分是二叉树的插入
if (root == null) {
root = nTreeNode;
return true;
}
TreeNode curNode = nTreeNode;
TreeNode prevNode = null;
while (curNode != null) {
prevNode = curNode;
if (nTreeNode.val > curNode.val) {
curNode = curNode.left;
} else if (nTreeNode.val < curNode.val) {
curNode = curNode.right;
} else {
return false;
}
}
//判断位置
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 < Ppaernt.val) {
Ppaernt.left = Rpaernt;
} else {
Ppaernt.right = Rpaernt;
}
}
RLparent.balanceFactor = 0;
parent.balanceFactor = 0;
}
private static void rightRotation(TreeNode parent) {
TreeNode LRparent = parent.left.right;
TreeNode Lparent = parent.left;
TreeNode pParent = parent.parent;
Lparent.right = parent;
parent.left = LRparent;
parent.parent = Lparent;
if (LRparent != null) {
LRparent.parent = parent;
}
//判断是不是根结点
if (parent == root) {
root = Lparent;
root.parent = null;
} else {
//不是根结点就判断是左子树还是右子树
if (pParent.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) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}
}
性能分析
AVL树对于静态数据来说,查找效率极高,但对于需要频繁修改的数据来说则效率并不理想,因为AVL的高效是为了保持平衡而旋转付出的代价
红黑树
特点
红黑树中结点的非黑及红
不存在两个连续的红色结点(黑色可以)
最长路径不能大于最短路径的两倍
根结点是黑色的
一个结点向下延伸的每条路径中黑色结点的是相同的
每个叶子结点都是黑色的,且都是空结点
红黑树是为了保持相对平衡,而不是像AVL树一样保持绝对平衡
如果黑色节点是X个,因为根结点是黑色的,且根结点到每个叶子节点的黑色节点数量相同,红色节点的子节点必是两个黑色节点,则红色节点最多X-1个,考虑最短路径纯黑色节点和最长路径红色以最多的形式在路径插入,查找的时间复杂度都是logN
红黑树节点初始化的时候把颜色设置为红色,因为当你插入一个颜色为黑色时,又需要保持各个路径黑色节点数目相同,就会增加多余的节点或者进行更复杂的调整,如果初始化为红色,则会较黑色节点减少复杂程度和开销
红黑树插入实现
public class rbTree {
public static void main(String[] args) {
rbTree rbtree = new rbTree();
int[] arr = {4, 2, 6, 1, 3, 5, 15, 7, 16,14};
for (int i = 0; i < arr.length; i++) {
rbtree.insert(arr[i]);
}
System.out.println(isRBTree(root));
inOrder(root);
}
static class rbTreeNode {
public int val;
public rbTreeNode left;
public rbTreeNode right;
public rbTreeNode parent;
public Color color;
public rbTreeNode(int val) {
this.val = val;
this.color = Color.Red;
}
}
static rbTreeNode root;
public static boolean insert(int val) {
rbTreeNode node = new rbTreeNode(val);
if (root == null) {
root = node;
root.color = Color.Black;
return true;
}
rbTreeNode cur = root;
rbTreeNode prev = null;
while (cur != null) {
prev = cur;
if (cur.val > val) {
cur = cur.left;
} else if (cur.val < val) {
cur = cur.right;
} else {
System.out.println("已存在,无法存入");
return false;
}
}
if (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 < 0) {
throw new ArrayIndexOutOfBoundsException();
}
int byteIndex = val / 8;
while (byteIndex > elements.length - 1) {
elements = Arrays.copyOf(elements, elements.length + 1);
}
int bitIndex = val % 8;
elements[byteIndex] |= (1 << bitIndex);
usedSize++;
}
public boolean get(int val) {
if (val < 0) {
throw new ArrayIndexOutOfBoundsException();
}
int byteIndex = val / 8;
if (byteIndex > elements.length - 1) {
System.out.println("坐标越界违法");
return false;
}
int bitIndex = val % 8;
if (((elements[byteIndex]) & (1 << bitIndex)) != 0) {
return true;
}
return false;
}
public void reSet(int val) {
if (val < 0) {
throw new ArrayIndexOutOfBoundsException();
}
int byteIndex = val / 8;
if (byteIndex > elements.length - 1) {
System.out.println("坐标越界违法");
return;
}
int bitIndex = val % 8;
elements[byteIndex] &= ~(1<<bitIndex);
usedSize--;
}
public int getUsedSize() {
return usedSize;
}
}
布隆过滤器
布隆过滤器是判断某样东西一定不存在或者可能存在,布隆过滤器是位图和多个哈希函数的结合,使用哈希函数就存在哈希碰撞,在一个元素插入的时候,使用位图多个位置来标记,难免后面出现元素会与其中一个位置或者多个位置重合,但是如果当元素判断的几个位置标记中有一个为0,那么就肯定不存在,而且对于布隆过滤器来说是不可以删除的,因为其中一个元素的删除,其中与之重合位置的其他元素会被认为不存在
实现
package bloomfilter;
import java.util.BitSet;
class SimpleHash {
public int cap;//容量
public int rand;//随机种子
public SimpleHash(int cap, int rand) {
this.cap = cap;
this.rand = rand;
}
/**
* 哈希函数
*
* @param s 根据字符串返回一个哈希值
* @return
*/
int hash(String s) {
int res = 0;
for (int i = 0; i < s.length(); i++) {
res = res * rand + s.charAt(i);
}
return res & (cap - 1);
}
}
public class BloomFilter {
public static void main(String[] args) {
BloomFilter b = new BloomFilter();
b.add("www");
b.add("aaa");
b.add("acb");
b.add("abc");
System.out.println(b.contains("abc"));
}
private static int DEFAULT_SIZE;
BitSet bitSet;
public int usedSize;//存储的个数
public int[] rad = {1, 3, 7, 13, 26, 74};//随机种子
SimpleHash[] simpleHashes;
public BloomFilter() {
bitSet = new BitSet(DEFAULT_SIZE);
simpleHashes = new SimpleHash[rad.length];
//根据每个随机种子生成对应的哈希函数
for (int i = 0; i < rad.length; i++) {
simpleHashes[i] = new SimpleHash(DEFAULT_SIZE, rad[i]);
}
}
public void add(String s) {
for (int i = 0; i < simpleHashes.length; i++) {
bitSet.set(simpleHashes[i].hash(s));
}
usedSize++;
}
public boolean contains(String s) {
for (int i = 0; i < simpleHashes.length; i++) {
if (!bitSet.get(simpleHashes[i].hash(s))) {
return false;
}
}
return true;
}
}
优点:
对于数据量庞大时,可以对数据全量进行存储
时间复杂度取决于哈希函数的个数,与数据量无关
极大的节省空间
缺点:
对数据容易产生误判,但是可以确定一定不存在的数据
不支持删除操作
无法获取元素
海量数据问题
1. 对于一个100多G的文件,存放着IP,如何知道出现次数最多的IP?
首先不能使用<K,V>结构,因为数据太大,内存存不下,那我们就要对文件进行细分
但是不能均分来分别统计小文件中的最大值,因为IP随机分布,且小文件的最大值并不能代表大文件的最大值
我们可以分出200份小文件,大小0.5G,然后对大文件进行遍历,将大文件的IP通过哈希函数得到对应的下标,写入对应的文件,每个文件存储相同的IP,最后使用Map统计每个小文件IP出现的次数进行比较得到对应的IP
2. 给定100亿个整数，设计算法找到只出现一次的整数？
(1)采用刚才的方法,进行哈希切割,创建足够数量的小文件,使用哈希函数来放入,最后统计出现一次的整数
(2)也可以采用两个位图的方法进行,对一个数据出现次数的不同对两个位图相应位置进行调整,比如出现一次第一个位图表示0,第二个位图表示1,表示01;出现两次后,把第一个位图改为1,第二个位图改为0,表示10,以此类推
(3)或者可以使用一个位图,但是你要用两个位来表示.一个数据用以统计出现次数
3. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
(1)采用哈希分割,两个文件分别采用哈希函数写入各自的几百个小文件,然后因为采用相同的哈希函数,下标相同的文件中对于相同的数字建立一个大文件接收
(2)使用位图,先将一个文件放在位图里,然后遍历另一个文件,对于B文件中出现的可以在A文件中找到就放到一个新的大文件来储存
(3)仍是采用位图,将两个文件分别存入不同的位图,使用按位与运算得到交集,同样的,采用这个方法还可以通过按位或运算得到并集,通过按位异或得到差集
4. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
(1) 采用哈希切割
(2) 使用两个位图,标记次数,00,01,10,11
5. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
(1) 采用哈希切割,对于两个文件分别建立足够数量恰当大小的小文件,通过哈希函数分别将query存储到对于小文件,然后最后对于下标相同的小文件进行查找合并交集
(2) 使用布隆过滤器,将第一个文件放到布隆过滤器,然后对第二个文件中出现的数据去布隆过滤器查找,但是布隆过滤器存在误判,不能准确判断
一堆数据要存放到多个服务器,如果使用一般哈希函数取余服务器的数量,就会导致增加服务器或者服务器崩溃时,原来在缓存中的数据一时间无法对映,会使数据访问压力剧增,可能会宕机
基于上述情况,可以采用一致性哈希解决,采用环形哈希,将服务器分布在哈希环上,数据的哈希函数会使得数据在哈希环上分布,顺时针缓存到遇到的第一个服务器,但是理想情况下是服务器分布分散,使得数据在各个服务器分布均匀,但是如果服务器分布集中就可能会使大量数据存储在一个服务器而使服务器压力很大
为了解决服务器在哈希环上分布不均匀的问题,就引入虚拟节点,使得服务器尽量均匀,每个虚拟节点对应一个服务器
并查集
并查集可以将数据进行划分不同的集合,并可以合并集合
实现并查集
import java.util.Arrays;
public class unionFindSet {
int[] array;
public unionFindSet(int num) {
array = new int[num];
//初始化为-1
Arrays.fill(array, -1);
}
/**
* 判断两个元素是不是同一个集合
*
* @param a
* @param b
* @return
*/
public boolean isSameFindSet(int a, int b) {
return findRoot(a) == findRoot(b);
}
/**
* 查找元素根结点
*
* @param a
* @return 返回根结点下标
*/
private int findRoot(int a) {
//如果下标负数,则违法抛出异常
if (a < 0) {
throw new ArrayIndexOutOfBoundsException();
}
while (array[a] >= 0) {
a = array[a];
}
return a;
}
/**
* 合并集合
*
* @param x1
* @param x2
*/
public boolean union(int x1, int x2) {
//合并两个数要合并根结点
//先要判断是不是同一集合
int root1 = findRoot(x1);
int root2 = findRoot(x2);
if (root1 == root2) {
System.out.println("属于同一集合,不需要合并");
return false;
}
array[root1] += array[root2];
array[root2] = root1;
return true;
}
/**
* 得到数据中有集合个数
*
* @return
*/
public int getSet() {
int count = 0;
for (int x : array) {
if (x < 0) {
count++;
}
}
return count;
}
public void print() {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
}
如果把true改为false就会是
如果使用false,打印的顺序是插入顺序,使用true的话,就会结合访问顺序,每次访问一个元素,会放置尾部,容量满且需要插入时,就会从头部删除
实现LRUCache
import java.util.HashMap;
public class LRUCache {
static class DLinkNode {
int key;
int value;
DLinkNode prev;
DLinkNode next;
public DLinkNode(int key, int value) {
this.key = key;
this.value = value;
}
public DLinkNode() {
}
}
public DLinkNode head;//头结点
public DLinkNode tail;//尾节点
public int capacity;//容量
public int usedSize;
HashMap<Integer, DLinkNode> map = new HashMap<>();
public LRUCache(int capacity) {
head = new DLinkNode();
tail = new DLinkNode();
head.next = tail;
tail.prev = head;
this.capacity = capacity;
}
public void put(int key, int value) {
DLinkNode node = map.get(key);
//不存在该元素
if (node == null) {
//创建新的节点
DLinkNode newNode = new DLinkNode(key, value);
map.put(key, newNode);
//尾插
insertTail(newNode);
usedSize++;
//检查是否元素填满
if (usedSize > 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<bTreeNode, Integer> 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 < parent.keys[index]) {
parent.keys[index + 1] = parent.keys[index];
} else {
//大于情况,等于已经在find判断过了
break;
}
index--;
}
parent.keys[index + 1] = val;
parent.usedSize++;
if (parent.usedSize >= 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 < sNode.usedSize) {
newNode.keys[i] = sNode.keys[j];
newNode.childs[i] = sNode.childs[j];
//分裂节点孩子节点在转移的时候要修改他们的父结点
if (sNode.childs[i] != null) {
sNode.childs[i].parent = newNode;
}
j++;
i++;
}
//将最后一个孩子节点记录下来,重复一次
newNode.childs[i] = sNode.childs[j];
if (sNode.childs[i] != null) {
sNode.childs[i].parent = newNode;
}
newNode.usedSize = i;
//更新原来节点的有效数据数量
//减去右侧数据的数量,再减去中间数据,因为中间数据要被提到分裂节点的父结点中去
sNode.usedSize = sNode.usedSize - i - 1;
//更新新节点的父亲节点和有效数据数量
if (sNode == root) {
root = new bTreeNode();
root.keys[0] = sNode.keys[mid];
root.childs[0] = sNode;
root.childs[1] = newNode;
sNode.parent = root;
newNode.parent = root;
root.usedSize = 1;
return;
}
newNode.parent = psNode;
//将分裂节点的中间值提到父亲节点
int fIndexEnd = psNode.usedSize - 1;
//中间值
int midValue = sNode.keys[mid];
while (fIndexEnd >= 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<bTreeNode, Integer> findVal(int val) {
bTreeNode cur = root;
bTreeNode parent = null;
while (cur != null) {
int i = 0;
while (i < cur.usedSize) {
if (cur.keys[i] == val) {
return new Pair<>(cur, i);
} else if (cur.keys[i] < val) {
i++;
} else {
break;
}
}
parent = cur;
cur = cur.childs[i];
}
return new Pair<>(parent, -1);
}
public static void main(String[] args) {
bTree myBtree = new bTree();
int[] array = {53, 139, 75, 49, 145, 36,101};
for (int i = 0; i < array.length; i++) {
myBtree.insert(array[i]);
}
System.out.println("fdsafafa");
myBtree.inorder(myBtree.root);
}
private void inorder(bTreeNode root){
if(root == null)
return;
for(int i = 0; i < root.usedSize; ++i){
inorder(root.childs[i]);
System.out.println(root.keys[i]);
}
inorder(root.childs[root.usedSize]);
}
}
B+树
B+树特点:
使用B+树搜索数据一定要遍历整个树的高度,B树不一定
对于<K,V>结构而言,非叶子节点存储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 < matrix.length; i++) {
Arrays.fill(matrix[i], Integer.MAX_VALUE);
}
this.isDirect = Direct;
}
public void initArrayV(char[] array) {
for (int i = 0; i < arrayV.length; i++) {
arrayV[i] = array[i];
}
}
/**
* @param srcV 起点
* @param destV 终点
* @param weight 权重
*/
public void addEdge(char srcV, char destV, int weight) {
int srcVIndex = getIndexOfV(srcV);
int destVIndex = getIndexOfV(destV);
matrix[srcVIndex][destVIndex] = weight;
//判断是不是无向图
//因为无向图的邻接矩阵对称
if (!isDirect) {
matrix[destVIndex][srcVIndex] = weight;
}
}
private int getIndexOfV(char v) {
for (int i = 0; i < arrayV[i]; i++) {
if (v == arrayV[i]) {
return i;
}
}
return -1;
}
public void printGraph() {
for (int i = 0; i < arrayV.length; i++) {
System.out.print(arrayV[i] + " ");
}
System.out.println();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == Integer.MAX_VALUE) {
System.out.print("∞ ");
} else {
System.out.print(matrix[i][j] + " ");
}
}
System.out.println();
}
}
/**
* 获取顶点的度
*
* @param v
* @return
*/
public int getDevOfV(char v) {
int count = 0;
int index = getIndexOfV(v);
for (int i = 0; i < matrix[index].length; i++) {
if (matrix[index][i] != Integer.MAX_VALUE) {
count++;
}
}
//判断是不是有向图,有向图顶点的度包括入度和出度
if (isDirect) {
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][index] != Integer.MAX_VALUE) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
GraphByMatrix graph = new GraphByMatrix(4, true);
char[] array = {'A', 'B', 'C', 'D'};
graph.initArrayV(array);
graph.addEdge('A', 'B', 1);
graph.addEdge('A', 'D', 1);
graph.addEdge('B', 'A', 1);
graph.addEdge('B', 'C', 1);
graph.addEdge('C', 'B', 1);
graph.addEdge('C', 'D', 1);
graph.addEdge('D', 'A', 1);
graph.addEdge('D', 'C', 1);
System.out.println();
graph.printGraph();
System.out.println(graph.getDevOfV('A'));
}
}
邻接表
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<Node> edgList;//存储边
public boolean isDirect;
public GraphByNode(boolean isDirect, int size) {
this.arrayV = new char[size];
edgList = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
edgList.add(null);
}
this.isDirect = isDirect;
}
public void initArrayV(char[] array) {
for (int i = 0; i < array.length; i++) {
arrayV[i] = array[i];
}
}
public void addEdge(char srcV, char destV, int weight) {
int srcIndex = getIndexOfV(srcV);
int destIndex = getIndexOfV(destV);
addEdgeChild(srcIndex, destIndex, weight);
if (!isDirect) {
addEdgeChild(destIndex, srcIndex, weight);
}
}
private void addEdgeChild(int srcIndex, int destIndex, int weight) {
Node cur = edgList.get(srcIndex);
while (cur != null) {
//是否存在该值
if (cur.dest == destIndex) {
return;
}
cur = cur.next;
}
//不存在,创建
Node newNode = new Node(srcIndex, destIndex, weight);
newNode.next = edgList.get(srcIndex);
edgList.set(srcIndex, newNode);
}
private int getIndexOfV(char v) {
for (int i = 0; i < arrayV.length; i++) {
if (arrayV[i] == v) {
return i;
}
}
return -1;
}
public void printGraph() {
for (int i = 0; i < arrayV.length; i++) {
System.out.print(arrayV[i]);
Node cur = edgList.get(i);
while (cur != null) {
System.out.print("->" + 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 < arrayV.length; i++) {
//入度不需要考虑从本身出发的点
if (i == srcIndex) {
continue;
} else {
cur = edgList.get(i);
while (cur != null) {
if (cur.dest == srcIndex) {
count++;
}
cur = cur.next;
}
}
}
}
return count;
}
public static void main(String[] args) {
GraphByNode graph = new GraphByNode(false, 4);
char[] array = {'A', 'B', 'C', 'D'};
graph.initArrayV(array);
graph.addEdge('A', 'B', 1);
graph.addEdge('A', 'D', 1);
graph.addEdge('B', 'A', 1);
graph.addEdge('B', 'C', 1);
graph.addEdge('C', 'B', 1);
graph.addEdge('C', 'D', 1);
graph.addEdge('D', 'A', 1);
graph.addEdge('D', 'C', 1);
System.out.println("getDevOfV:: "+graph.getDevOfV('A'));
graph.printGraph();
}
}
深度优先遍历&广度优先遍历
/**
* 广度优先遍历
*
* @param v
*/
public void bfs(char v) {
//得到起点的坐标
int src = getIndexOfV(v);
//标记是否出现过
boolean[] visited = new boolean[arrayV.length];
Queue<Integer> 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 < arrayV.length; i++) {
if (matrix[top][i] != Integer.MAX_VALUE && !visited[i]) {
queue.offer(i);
visited[i] = true;
}
}
}
}
/**
* 深度优先遍历
*
* @param v
*/
public void dfs(char v) {
//得到起始位置
int index = getIndexOfV(v);
boolean[] visited = new boolean[arrayV.length];
dfsChild(index, visited);
}
private void dfsChild(int index, boolean[] visited) {
System.out.print(arrayV[index] + "->");
visited[index] = true;
for (int i = 0; i < arrayV.length; i++) {
if (matrix[index][i] != Integer.MAX_VALUE && !visited[i]) {
dfsChild(i, visited);
}
}
}