| dbo:abstract
|
- AA strom (Arne Andersson strom) je červeno-černý strom s jedním přídavným pravidlem. Na rozdíl od červeno-černého stromu mohou být červené uzly vkládány pouze do pravého potomka, což znamená, že žádný červený uzel nemůže být levý potomek. Takto získáme strom izomorfní s B-stromem třetí úrovně (2-3 strom). Značně se tak usnadní implementace stromových operací. Pro správné vyvážení červeno-černých stromů musí vyvažovací algoritmy uvažovat sedm různých tvarů: Díky omezení, že pouze pravé hrany mohou být červené, stačí u AA stromů brát v potaz jen dva případy: Podobným způsobem k zjednodušení úlohy přistupují tzv. , které zakazují červené pravé potomky určitého vrcholu s tou výjimkou, kdy je červený zároveň i levý potomek toho vrcholu. Tak vzniká struktura izomorfní s . Pro další úvahy budeme předpokládat, že je v každém uzlu uložena proměnná úroveň, uchovávající počet levých hran, které musíme sledovat, než narazíme na nulový ukazatel. Listy tedy budou mít úroveň jedna. Původní strom: 4 / \ 2 10 / \ / \1 3 6 12 / \ / \ 5 8 11 13 / \ 7 9 strom, ve kterém jsou uloženy úrovně: 4,3 / \ 2,2 10,3 / \ / \1,1 3,1 6,2 12,2 / \ / \ 5,1 8,2 11,1 13,1 / \ 7,1 9,1 a strom zaznamenaný v notaci červeno-černých stromů (B – černá, R – červená): B(4) / \ B(2) R(10) / \ / \B(1) R(3) B(6) B(12) / \ / \ B(5) R(8) B(11) R(13) / \ B(7) B(9) Pro AA strom platí následující pravidla: 1.
* Levý potomek nesmí mít stejnou úroveň jako jeho rodič 2.
* Nejsou povoleny dva praví potomci se stejnou úrovní jako rodič Pokud bychom chtěli tato pravidla zapsat v terminologii červeno-černých stromů, zněla by následovně: 1.
* Červené levé hrany nejsou povoleny 2.
* Dvě po sobě jdoucí červené hrany nejsou povoleny Díky vlastnostem AA stromu, kdy může být pouze pravý potomek červený, jsou dva výše zmíněné zápisy pravidel ekvivalentní a budeme je v článku různě střídat. (cs)
- An AA tree in computer science is a form of balanced tree used for storing and retrieving ordered data efficiently. AA trees are named after , the one who theorized them. AA trees are a variation of the red–black tree, a form of binary search tree which supports efficient addition and deletion of entries. Unlike red–black trees, red nodes on an AA tree can only be added as a right subchild. In other words, no red node can be a left sub-child. This results in the simulation of a 2–3 tree instead of a 2–3–4 tree, which greatly simplifies the maintenance operations. The maintenance algorithms for a red–black tree need to consider seven different shapes to properly balance the tree: An AA tree on the other hand only needs to consider two shapes due to the strict requirement that only right links can be red: (en)
- En informática un árbol AA es un tipo de árbol binario de búsqueda auto-balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente. Los árboles AA reciben el nombre de su inventor, . Los árboles AA son una variación del árbol rojo-negro, que a su vez es una mejora del árbol binario de búsqueda. A diferencia de los árboles rojo-negro, los nodos rojos en un árbol AA sólo pueden añadirse como un hijo derecho. En otras palabras, ningún nodo rojo puede ser un hijo izquierdo. De esta manera se simula un árbol 2-3 en lugar de un , lo que simplifica las operaciones de mantenimiento. Los algoritmos de mantenimiento para un árbol rojo-negro necesitan considerar siete diferentes formas para balancear adecuadamente el árbol: En un árbol AA, al cumplirse el estricto requisito de que sólo los enlaces derechos pueden ser rojos, sólo es necesario considerar dos formas: (es)
- AA木（英: AA tree）は、平衡2分探索木の一種であり、順序のあるデータを効率的に格納し検索する。Arne Andersson が1993年に発表した。名称は考案者の名前のイニシャルに由来する。 赤黒木とは異なり、AA木では右の子ノードだけが赤となる。逆に言えば、左の子ノードは赤にはならない。結果として2-3-4木ではなく2-3木に相当したものとなり、操作時の処理が大幅に簡略化される。赤黒木では、平衡を保つために以下のような木構造の断片をそれぞれ異なるものとして扱う必要がある。 これに対してAA木では、右のリンクだけが赤になりうるため、以下の2種類だけを考慮すればよい。 (ja)
- AA 樹在電腦科學一種形式的自平衡二元搜尋樹用於高效存儲和檢索序數據。 AA 樹的名稱是由它的發明者而來。 AA樹是紅黑樹的一種變種，是Arne Andersson教授在1993年年在他的論文"Balanced search trees made simple"中介紹，設計的目的是減少紅黑樹考慮的不同情況，區別於紅黑樹的是，AA樹的紅節點只能作為右葉子，從而大大簡化了維護2-3樹的模擬。維護紅黑樹的平衡需要考慮7種不同的情況: 因為AA樹有嚴格的條件(紅節點只能為右節點)，故只需考慮2種情形: (zh)
|
| rdfs:comment
|
- AA木（英: AA tree）は、平衡2分探索木の一種であり、順序のあるデータを効率的に格納し検索する。Arne Andersson が1993年に発表した。名称は考案者の名前のイニシャルに由来する。 赤黒木とは異なり、AA木では右の子ノードだけが赤となる。逆に言えば、左の子ノードは赤にはならない。結果として2-3-4木ではなく2-3木に相当したものとなり、操作時の処理が大幅に簡略化される。赤黒木では、平衡を保つために以下のような木構造の断片をそれぞれ異なるものとして扱う必要がある。 これに対してAA木では、右のリンクだけが赤になりうるため、以下の2種類だけを考慮すればよい。 (ja)
- AA 樹在電腦科學一種形式的自平衡二元搜尋樹用於高效存儲和檢索序數據。 AA 樹的名稱是由它的發明者而來。 AA樹是紅黑樹的一種變種，是Arne Andersson教授在1993年年在他的論文"Balanced search trees made simple"中介紹，設計的目的是減少紅黑樹考慮的不同情況，區別於紅黑樹的是，AA樹的紅節點只能作為右葉子，從而大大簡化了維護2-3樹的模擬。維護紅黑樹的平衡需要考慮7種不同的情況: 因為AA樹有嚴格的條件(紅節點只能為右節點)，故只需考慮2種情形: (zh)
- AA strom (Arne Andersson strom) je červeno-černý strom s jedním přídavným pravidlem. Na rozdíl od červeno-černého stromu mohou být červené uzly vkládány pouze do pravého potomka, což znamená, že žádný červený uzel nemůže být levý potomek. Takto získáme strom izomorfní s B-stromem třetí úrovně (2-3 strom). Značně se tak usnadní implementace stromových operací. Pro správné vyvážení červeno-černých stromů musí vyvažovací algoritmy uvažovat sedm různých tvarů: Díky omezení, že pouze pravé hrany mohou být červené, stačí u AA stromů brát v potaz jen dva případy: Původní strom: (cs)
- An AA tree in computer science is a form of balanced tree used for storing and retrieving ordered data efficiently. AA trees are named after , the one who theorized them. AA trees are a variation of the red–black tree, a form of binary search tree which supports efficient addition and deletion of entries. Unlike red–black trees, red nodes on an AA tree can only be added as a right subchild. In other words, no red node can be a left sub-child. This results in the simulation of a 2–3 tree instead of a 2–3–4 tree, which greatly simplifies the maintenance operations. The maintenance algorithms for a red–black tree need to consider seven different shapes to properly balance the tree: (en)
- En informática un árbol AA es un tipo de árbol binario de búsqueda auto-balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente. Los árboles AA reciben el nombre de su inventor, . En un árbol AA, al cumplirse el estricto requisito de que sólo los enlaces derechos pueden ser rojos, sólo es necesario considerar dos formas: (es)
|