小伙伴们了解跳跃表和红黑树吗?你们知道它们都分别有什么概念及区别吗?下面快跟小编了解一下吧。
一、跳跃表是什么?
跳表就是一个随机化的数据结构，它也可以被看做是二叉树的一个变种，从性能上来说它和红黑树，AVL等树不相上下，但它的原理非常简单，目前在Redis和LeveIDB中被经常用到。
跳跃表会随机决定链表中哪些节点应增加向前指针及在该节点中应增加多少个指针。跳跃表表结构的头节点一定要有足够的指针域，来满足可能构造最大级数的需要，但尾节点不用指针域。
因为是随机的，所以在跳表中的搜索、插入、删除操作的时间复杂度均为O(logn)，但是，在最坏的情况下，它的时间复杂性就会变成O(n)。相对之下，在一个有序数组或链表中进行插入/删除操作的时间为O(n)，最坏情况下为O(n)。
一般来说，跳表处理的都会是有序的链表，如下：
在这个链表中，如果要搜索一个数，需要从头到尾比较每个元素是否匹配，直到找到匹配的数为止，即时间复杂度是 O(n)。同理，插入一个数并保持链表有序，需要先找到合适的插入位置，再执行插入，总计也是 O(n) 的时间。
那要怎么提高搜索的速度呢?就需要使用索引：
如上图，我们新创建一个链表，它包含的元素为前一个链表的偶数个元素。这样在搜索一个元素时，我们先在上层链表进行搜索，当元素未找到时再到下层链表中搜索。例如搜索数字 19 时的路径如下图：
先在上层中搜索，到达节点 17 时发现下一个节点为 21，已经大于 19，于是转到下一层搜索，找到的目标数字 19。
我们知道上层的节点数目为 n/2n/2n/2，因此，有了这层索引，我们搜索的时间复杂度降为了：O(n/2)O(n/2)O(n/2)。同理，我们可以不断地增加层数，来减少搜索的时间：
在上面的 4 层链表中搜索 25，在最上层搜索时就可以直接跳过 21 之前的所有节点，因此十分高效。
二、红黑树是什么?
红黑树，它是一棵节点不是红就是黑的平衡二叉树，一般它会通过颜色的约束来维持二叉树的平衡。
一棵合格红黑树必须有着以下规范：
1)、每个节点必须是红色或黑色
2)、根节点必须是黑色
3)、每个叶节点(NIL节点，空节点)都要是黑色的。
4)、如若它的其中一个结点是红色，那它的另外两个子节点都必须是黑的。意思就是在一条路径上不能出现相邻的两个红色结点。
5)、从它的任一节点到其每个叶子的所有路径都要包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不会多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。所以红黑树它是复杂而高效的，其检索效率O(log n)。
区别：红黑树是一种存在于内存中的结构，可以保证在最坏的情况下，对红黑树进行例如search，insert，以及delete等基本的动态集合操作的时间复杂度为O(lg n)。而跳跃表则是一种随机性的结构，所以在跳表中的搜索、插入、删除操作的时间复杂度就都为O(logn)，但在最坏的情况下，它的时间复杂性又会变成O(n)。
以上就是本篇文章的所有内容了，如若还想了解更多相关java入门知识，就来关注我们的网站了解详情吧。
推荐阅读：