| dbpprop:abstract
|
- Červeno-černý strom je binární vyhledávací strom. Jedná se o datovou strukturu často používanou pro implementaci asociativního pole. Autor algoritmu, Rudolf Bayer, jej nejprve nazval symetrický binární B-strom, své moderní jméno získal až v práci Lea J. Guibase a Roberta Sedgewicka z roku 1978. Červeno-černý strom musí splňovat následující pravidla: Každý vrchol je buď červený, nebo černý. Listy (nil) jsou pokládány za černé vrcholy. Každý červený vrchol má dva černé syny. Každá cesta z jednoho vrcholu do jeho podřízených listů obsahují stejný počet černých vrcholů.
- Ein Rot-Schwarz-Baum ist in der Informatik eine vom binären Suchbaum abgeleitete Datenstruktur, die sehr schnellen Zugriff auf die in ihr gespeicherten Werte garantiert. Rot-Schwarz-Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben, welcher sie symmetric binary B-trees nannte. Der heutige Name geht auf Leo J. Guibas und Robert Sedgewick zurück, die 1978 die rot-schwarze Farbkonvention einführten. Die schnellen Zugriffzeiten auf die einzelnen im Rot-Schwarz-Baum gespeicherten Elemente werden durch fünf Eigenschaften erreicht, die zusammen garantieren, dass ein Rot-Schwarz-Baum immer balanciert ist, wodurch die Höhe eines Rot-Schwarz-Baumes mit n Werten nie größer wird als 2 log2 (n+1). Somit können die wichtigsten Operationen in Suchbäumen – suchen, einfügen und löschen – garantiert in O(log n) ausgeführt werden.
- A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf BayerFact|date=February 2009 who called them "symmetric binary B-trees", but acquired its modern name in a paper in 1978 by Leonidas J. Guibas and Robert Sedgewick. It is complex, but has good worst-case running time for its operations and is efficient in practice: it can search, insert, and delete in O(log n) time, where n is total number of elements in the tree. Put very simply, a red-black tree is a binary search tree which inserts and removes intelligently, to ensure the tree is reasonably balanced.
- Un árbol rojo negro es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. La estructura original fue creada por Rudolf Bayer en 1972, que le dio el nombre de “árboles-B binarios simétricos”, pero tomó su nombre moderno en un trabajo de Leo J. Guibas y Robert Sedgewick realizado en 1978. Es complejo, pero tiene un buen peor caso de tiempo de ejecución para sus operaciones y es eficiente en la práctica. Puede buscar, insertar y borrar en un tiempo O(log n), donde n es el número de elementos del árbol. Sería ideal exponer la especificación algebraica completa de este tipo abstracto de datos (TAD) escrita en algún lenguaje de especificación de TADs como podría ser Maude; sin embargo, la complejidad de la estructura hace que la especificación quede bastante ilegible, y no aportaría nada. Por tanto, explicaremos su funcionamiento con palabras, esquemas e implementaciones de funciones en el lenguaje de programación C.
- Punamusta puu on tasapainotettu binäärinen hakupuu. Punamusta puu sisältää solmuja, joista jokaisella voi olla korkeintaan kaksi lapsisolmua. Binäärisestä hakupuusta punamusta puu eroaa ylimääräisen väribitin perusteella: jokainen puun solmu voi olla väriltään joko punainen tai musta. Tämä yksi bitti/solmu on riittävä määrä tietoa, jolla puu voidaan pitää tasapainoisena. Punamustan puun keksi vuonna 1972 Rudolf Bayer, joka kutsui keksintöään symmetrisiseksi binääripuuksi. Menetelmä on jonkin verran monimutkaisempi kuin AVL-puu tai tavallinen binäärinen hakupuu. Hakurakenteena se on tehokas. Punamustalle puulle voidaan suorittaa hakuja, lisäyksiä ja poistoja pahimmassakin tapauksessa logaritmisessa ajassa suhteessa puuhun talletettujen alkioiden kokonaismäärään.
- Un arbre bicolore ou arbre rouge et noir est un type particulier d'arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomma "symetric binary B-trees". Leur principal intérêt réside dans la complexité logarithmique des opérations suivantes : l'insertion, la recherche et la suppression. Ils sont cependant assez complexes à mettre en œuvre, car les opérations d'insertion et de suppression font appel à de nombreuses études de cas. Enfin, ils sont isomorphes aux arbres 2-3-4.
- Un albero rosso-nero è un tipo di albero binario di ricerca auto-aggiustante, una struttura dati usata in Informatica, tipicamente utilizzata per implementare array associativi. La struttura originale è stata inventata nel 1972 da Rudolf Bayer che la chiamò "B-alberi binari simmetrici", ma ha acquisito il nome attuale a partire da un articolo del 1978 di Leo J. Guibas e Robert Sedgewick. È complessa, ma ha un eccellente tempo di esecuzione nel caso peggiore ed è molto efficiente: effettua ricerche, inserimenti e cancellazioni in un tempo di O(log n), dove n è il numero di elementi nell'albero.
- 赤黒木（あかくろき）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。 このデータ構造は1972年のルドルフ・ベイヤー の発明である"symmetric binary B-trees"が元となっており、赤黒木という名前自体は 1978年にレオニダス・ギッバス (Leonidas J. Guibas) とロバート・セジウィック によって発表された論文による。 赤黒木は、探索、挿入、削除などの操作における最悪時間計算量がO(log n)（nはツリーの要素数）と短く、複雑ではあるが実用的なデータ構造として知られている。
- Drzewo czerwono-czarne – rodzaj samoorganizującego się binarnego drzewa poszukiwań - struktury danych stosowanej w informatyce najczęściej do implementacji tablic asocjacyjnych. Została ona wynaleziona przez Rudolfa Bayera w 1972 roku, który nazwał je symetrycznymi binarnymi B-drzewami. Współczesną nazwę oraz dokładne zbadanie ich właściwości zawdzięcza się pracy "A dichromatic framework for balanced trees" z 1978 roku autorstwa Leo J. Guibasa oraz Roberta Sedgewicka. Drzewa czerwono-czarne są skomplikowane w implementacji, lecz charakteryzują się niską złożonością obliczeniową elementarnych operacji takich, jak wstawianie, wyszukiwanie czy usuwanie elementów z drzewa.
- Uma árvore rubro-negra é um tipo de árvore de busca binária balanceada, uma estrutura de dados usada em ciência da computação, tipicamente para implementar vetores associativos. A estrutura original foi inventada em 1972 por Rudolf BayerFact|date=February 2009 que a chamou de "Árvores Binárias B Simétricas", mas adquiriu este nome moderno em um artigo de 1978 escrito por Leonidas J. Guibas e Robert Sedgewick.. Ela é complexa, mas tem um bom pior-caso de tempo de execução para suas operações e é eficiente na prática: pode-se buscar, inserir, e remover em tempo O(log n), onde n é o número total de elementos da árvore. De maneira simplificada, uma árvore rubro-negra é uma árvore de busca binária que insere e remove de forma inteligente, para assegurar que a árvore permaneça aproximadamente balanceada.
- Красно-чёрное дерево (Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся [[Двоичное дерево (структура данных) | двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее [[Двоичное дерево (структура данных)#Основные операции в двоичном дереве поиска | основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счет введения дополнительного атрибута узла дерева — «цвет». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный». Красно-чёрное дерево обладает следующими свойствами: Корень должен быть чёрным. Потомки красного узла должны быть чёрными (т. е. запрещена ситуация с двумя красными узлами подряд). На всех ветвях дерева, ведущих от его корня к листьям, число чёрных узлов одинаково. При этом для удобства листьями красно-чёрного дерева считаются фиктивные «нулевые» узлы, не содержащие данных. Из указанных свойств очевидно, что красно-черное дерево имеет дисбаланс не более чем в 2 раза, иными словами, длина кратчайшего и длиннейшего пути в дереве от корня до листа не могут отличаться больше, чем в 2 раза. Это очевидно из того, что "черная длина" пути везде одинакова, а красных узлов на каждом пути не более чем столько же, сколько черных (иначе появятся 2 соседних красных узла). Есть алгоритмы выполнения операции добавления узлов (INSERT) и удаления узла (DELETE), которые сохраняют все свойства красно-чёрного дерева. При этом алгоритм добавления требует как максимум 2 поворота дерева, и удаления - как максимум 3 поворота. Красно-чёрные деревья являются одними из наиболее активно используемых на практике самобалансирующихся деревьев поиска. В частности, контейнер map в большинстве реализаций библиотеки STL, также как и многие другие реализации [[Ассоциативный массив|ассоциативного массива в различных библиотеках, основан на красно-чёрных деревьях. Популярность красно-чёрных деревьев связана с тем, что на них часто достигается подходящий баланс между степенью сбалансированности и сложностью поддержки сбалансированности. В частности, при сравнении с идеально сбалансированными деревьями часто обнаруживается, что последние имеют слишком жесткое условие сбалансированности и при выполнении операций удаления из дерева много времени тратится на поддержание необходимой сбалансированности.
- Röd-svart träd, datastruktur i form av ett så gott som balanserat binärt sökträd. Strukturen använder en extra bit för att hålla sig balanserat. Inget löv i trädet ligger mer än 2 ggr så långt från roten som något annat löv. Ett röd-svart träd med n interna noder har som mest höjden log2(n+1). Trädet har också kallats symmetriskt binärt B-träd.
- Kırmızı-siyah ağaç bilgisayar biliminde bir çeşit kendini-dengeleyen ikili arama ağacı veri yapısıdır. Orijinali ilk olarak 1972 yılında yapıyı "simetrik ikili B-ağaçları" olarak adlandıran Rudolf Bayer tarafından bulunmuştur. Bugünkü ismini 1978 yılında Leo J. Guibas ve Robert Sedgewick tarafından yayımlanan bir makaleyle almıştır. Karmaşık ancak çalışma süresi en kötü durumda bile iyi ve pratikte verimlidir: O(log n) (n ağaçtaki eleman sayısını gösterir) zamanda arama, ekleme ve çıkarma işlemleri yapabilir.
- Червоно-чорне дерево — в інформатиці — різновид бінарного дерева пошуку, вершини якого мають додаткові властивості (RB-властивості), зокрема «колір» (червоний або чорний). Червоно-чорні дерева — різновид збалансованих дерев, в яких за допомогою спеціальних трансформацій гарантується, що висота дерева h не буде перевищувати O(log n). Зважаючи на те, що час виконання основних операцій на бінарних деревах (пошук, видалення, додавання елементу) є O(h), ці структури даних на практиці є набагато ефективнішими, аніж звичайні бінарні дерева пошуку.
- 红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
|
| rdfs:comment
|
- Červeno-černý strom je binární vyhledávací strom. Jedná se o datovou strukturu často používanou pro implementaci asociativního pole. Autor algoritmu, Rudolf Bayer, jej nejprve nazval symetrický binární B-strom, své moderní jméno získal až v práci Lea J. Guibase a Roberta Sedgewicka z roku 1978. Červeno-černý strom musí splňovat následující pravidla: Každý vrchol je buď červený, nebo černý. Listy (nil) jsou pokládány za černé vrcholy.
- Ein Rot-Schwarz-Baum ist in der Informatik eine vom binären Suchbaum abgeleitete Datenstruktur, die sehr schnellen Zugriff auf die in ihr gespeicherten Werte garantiert. Rot-Schwarz-Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben, welcher sie symmetric binary B-trees nannte. Der heutige Name geht auf Leo J. Guibas und Robert Sedgewick zurück, die 1978 die rot-schwarze Farbkonvention einführten.
- Un árbol rojo negro es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. La estructura original fue creada por Rudolf Bayer en 1972, que le dio el nombre de “árboles-B binarios simétricos”, pero tomó su nombre moderno en un trabajo de Leo J. Guibas y Robert Sedgewick realizado en 1978.
- A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf BayerFact|date=February 2009 who called them "symmetric binary B-trees", but acquired its modern name in a paper in 1978 by Leonidas J. Guibas and Robert Sedgewick.
- Punamusta puu on tasapainotettu binäärinen hakupuu. Punamusta puu sisältää solmuja, joista jokaisella voi olla korkeintaan kaksi lapsisolmua. Binäärisestä hakupuusta punamusta puu eroaa ylimääräisen väribitin perusteella: jokainen puun solmu voi olla väriltään joko punainen tai musta. Tämä yksi bitti/solmu on riittävä määrä tietoa, jolla puu voidaan pitää tasapainoisena.
- Un arbre bicolore ou arbre rouge et noir est un type particulier d'arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomma "symetric binary B-trees". Leur principal intérêt réside dans la complexité logarithmique des opérations suivantes : l'insertion, la recherche et la suppression.
- Un albero rosso-nero è un tipo di albero binario di ricerca auto-aggiustante, una struttura dati usata in Informatica, tipicamente utilizzata per implementare array associativi. La struttura originale è stata inventata nel 1972 da Rudolf Bayer che la chiamò "B-alberi binari simmetrici", ma ha acquisito il nome attuale a partire da un articolo del 1978 di Leo J. Guibas e Robert Sedgewick.
- 赤黒木（あかくろき）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。 このデータ構造は1972年のルドルフ・ベイヤー の発明である"symmetric binary B-trees"が元となっており、赤黒木という名前自体は 1978年にレオニダス・ギッバス (Leonidas J.
- Drzewo czerwono-czarne – rodzaj samoorganizującego się binarnego drzewa poszukiwań - struktury danych stosowanej w informatyce najczęściej do implementacji tablic asocjacyjnych. Została ona wynaleziona przez Rudolfa Bayera w 1972 roku, który nazwał je symetrycznymi binarnymi B-drzewami. Współczesną nazwę oraz dokładne zbadanie ich właściwości zawdzięcza się pracy "A dichromatic framework for balanced trees" z 1978 roku autorstwa Leo J. Guibasa oraz Roberta Sedgewicka.
- Uma árvore rubro-negra é um tipo de árvore de busca binária balanceada, uma estrutura de dados usada em ciência da computação, tipicamente para implementar vetores associativos. A estrutura original foi inventada em 1972 por Rudolf BayerFact|date=February 2009 que a chamou de "Árvores Binárias B Simétricas", mas adquiriu este nome moderno em um artigo de 1978 escrito por Leonidas J. Guibas e Robert Sedgewick..
- Röd-svart träd, datastruktur i form av ett så gott som balanserat binärt sökträd. Strukturen använder en extra bit för att hålla sig balanserat. Inget löv i trädet ligger mer än 2 ggr så långt från roten som något annat löv. Ett röd-svart träd med n interna noder har som mest höjden log2(n+1). Trädet har också kallats symmetriskt binärt B-träd.
- Kırmızı-siyah ağaç bilgisayar biliminde bir çeşit kendini-dengeleyen ikili arama ağacı veri yapısıdır. Orijinali ilk olarak 1972 yılında yapıyı "simetrik ikili B-ağaçları" olarak adlandıran Rudolf Bayer tarafından bulunmuştur. Bugünkü ismini 1978 yılında Leo J. Guibas ve Robert Sedgewick tarafından yayımlanan bir makaleyle almıştır.
- Червоно-чорне дерево — в інформатиці — різновид бінарного дерева пошуку, вершини якого мають додаткові властивості (RB-властивості), зокрема «колір» (червоний або чорний).
- 红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J.
|
![[RDF Data]](/statics/sw-cube.png)
