| rdfs:comment
| - Una skip list és una estructura de dades probabilística a base de llistes encadenades paral·leles. (ca)
- Una skip list o lista por saltos es una Estructura de datos, basada en Listas enlazadas paralelas con eficiencia comparable a la de un árbol binario (tiempo en orden O(log n) para la mayoría de las operaciones). (es)
- En informatique, et plus précisément en algorithmique, une skip list, ou liste à enjambements, ou liste à saut, est une structure de données probabiliste, à base de listes chaînées parallèles. La plupart de ses opérations s'effectuent en temps O(log n) avec une grande probabilité, où n est le nombre d'éléments contenus dans la liste. (fr)
- In informatica, una skip list è una struttura dati probabilistica per la memorizzazione di una lista ordinata di elementi. Essa utilizza una gerarchia di liste concatenate che connettono sottosequenze di elementi. Queste liste ausiliarie permettono di percorrere la lista con grande efficienza, paragonabile a quella di un albero di ricerca binario bilanciato. Il livello più basso rappresenta la lista concatenata. (it)
- スキップリスト（英: skip list）は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log n)である。1989年にウィリアム・ピューが発表した。 スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され（高さ1が確率50%、高さ2が25%、高さ3が12.5%など）、リスト上の探索において連結リストの一部を高速に飛ばすことができる。 (ja)
- Список с пропусками (англ. Skip List) — вероятностная структура данных, основанная на нескольких параллельных отсортированных связных списках с эффективностью, сравнимой с двоичным деревом (порядка O(log n) среднее время для большинства операций). В основе списка с пропусками лежит расширение отсортированного связного списка дополнительными связями, добавленными в случайных путях с геометрическим/негативным биномиальным распределением, таким образом, чтобы поиск по списку мог быстро пропускать части этого списка. Вставка, поиск и удаление выполняются за логарифмическое случайное время. (ru)
- 在计算机科学中，跳跃列表是一种数据结构。它使得包含n个元素的有序序列的查找和插入操作的平均时间复杂度都是，优于数组的复杂度。 快速的查询效果是通过维护一个多层次的链表实现的，且与前一层（下面一层）链表元素的数量相比，每一层链表中的元素的数量更少（见右下角示意图）。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。跳过的元素的方法可以是随机性选择或确定性选择，其中前者更为常见。 (zh)
- В інформатиці, список з пропусками (англ. skip list) — структура даних, яка дозволяє швидкий пошук в упорядкованій послідовності елементів. Швидкий пошук стає можливим через утримання зв'язаної ієрархії підпослідовностей, кожна з яких пропускає кілька елементів з попереднього списку. Пошук стартує в найрозрідженішому списку, і триває допоки не знайдені два послідовних елементи один менший і один більший від шуканого елементу. Через ієрархічні зв'язки ці два елементи зв'язані з елементами наступного по щільності списку, в якому пошук продовжується. Таким чином ми доходимо до повного списку, без пропусків. Елементи пропущені у розріджених списках можуть обиратись імовірнісно. (uk)
- In computer science, a skip list (or skiplist) is a probabilistic data structure that allows average complexity for search as well as average complexity for insertion within an ordered sequence of elements. Thus it can get the best features of a sorted array (for searching) while maintaining a linked list-like structure that allows insertion, which is not possible with a static array. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one (see the picture below on the right). Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for. Via the linked hierarchy, these two elements (en)
- Lista z przeskokami (ang. skip list) – probabilistyczna struktura danych przeznaczona do przechowywania danych uporządkowanych (np. posortowanych rosnąco liczb), będąca rozwinięciem listy jednokierunkowej, a stanowiąca alternatywę dla drzew zbalansowanych (wyważonych), takich jak drzewa AVL czy czerwono-czarne. Została opracowana przez Williama Pugha w 1989 roku. Oczekiwana złożoność operacji wyszukiwania, wstawiania nowego elementu do listy oraz usunięcia elementu wynosi (pl)
- SkipList é uma estrutura de dados probabilística, baseada em listas ligadas paralelas, com eficiência comparável à de uma árvore binária (ordem de O(log n)) para a maioria das operações.Basicamente, uma skip list é um aglomerado de listas encadeadas com ligações adicionais, adicionadas de modo aleatório de acordo com a distribuição Geométrica/Negativa Binomial, os quais permitem evitar a busca em parte da lista, 'pulando' alguns valores. Inserção, busca e remoção são operadas em tempo logarítmico. (pt)
- En skipplista är en länkad lista där vissa element har pekare som går flera steg framåt (framåtpekare). En vanlig konfiguration är att låta antalet steg framåt vara en tvåpotens, som nedan <pre>|------------------------------>| ||-------------->|-------------->| ||------>|------>|------>|------>| ||-->|-->|-->|-->|-->|-->|-->|-->|-->|0 1 2 3 4 5 6 7 8 9</pre> en sådan skipplista kallas för en perfekt balanserad skipplista. Notera att listan utnyttjar sina pekare optimalt om antalet element är en tvåpotens. Listans nivå är lika med antalet pekare i header-noden. I exemplet ovan är listans nivå 4. (sv)
|
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
![[RDF Data]](/fct/images/sw-rdf-blue.png)