In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Rotación de árboles (es)
- Rotation d'un arbre binaire de recherche (fr)
- Rotasi pohon (in)
- Rotazione (informatica) (it)
- 木の回転 (ja)
- Rotacja drzewa (pl)
- Tree rotation (en)
- 树旋转 (zh)
- Поворот дерева (uk)
|
| rdfs:comment
| - En algorithmique, la rotation d'un arbre binaire de recherche permet de changer la structure d'un arbre binaire de recherche ou ABR sans invalider l'ordre des éléments. Une telle rotation consiste en fait à faire remonter un nœud dans l'arbre et à en faire redescendre un autre. Cette opération est très utilisée dans les arbres équilibrés en général car elle permet de réduire la hauteur d'un arbre en faisant descendre les petits sous-arbres et remonter les grands, ce qui permet de « rééquilibrer » les arbres et d'accélérer de nombreuses opérations sur ces arbres. (fr)
- Rotasi pohon adalah suatu operasi dalam pohon biner terurut yang mengubah strukturnya tanpa mengganggu urutan dari elemen. Sebuah rotasi pohon menggerakan satu simpul ke atas dan satu simpul ke bawah dalam pohon. Itu digunakan untuk mengganti bentuk dari pohon dan khususnya untuk mengurangi tinggi pohon tersebut dengan memindahkan sub-pohon yang lebih kecil ke bawah dan sub-pohon yang lebih besar ke atas, menghasilkan peningkatan kemampuan dari banyak operasi pohon. (in)
- 木の回転（きのかいてん、英: tree rotation）は、2分探索木の操作の一種で、要素の順序を崩さずに構造を変更するものである。木の回転は木の中の1つのノードを上にし、別のノードを下にする。木の形状を変化させるのに使い、特に大きい部分木を持ち上げて小さい部分木を下げることで全体の木の高さを低くするのに使う。それによって各種操作の性能を向上させる。 なお、回転の方向によって「右回転」、「左回転」と言うが、どちらが右でどちらが左なのかは必ずしも決まっていない。図示したときにノードがずれる方向を回転の方向とする場合もあれば、どちら側の子ノードが根ノードになるかを回転の方向とする場合もある（前者の逆になる）。本項ではノードがずれる方向を回転の方向とする。 (ja)
- Rotacja drzewa – operacja polegająca na lokalnej zmianie struktury binarnego drzewa poszukiwań (BST) z zachowaniem porządku wierzchołków. Rotacje stosuje się w drzewach BST do uzyskania wyważenia drzewa i minimalizacji jego wysokości, co prowadzi do zmniejszenia kosztu operacji na drzewie.Matematycznie rotacja jest dopuszczalna jeżeli relacja opisana drzewem jest łączna. Binarne drzewa poszukiwań są generalnie łączne ze względu na łączność relacji porządkującej klucze. Jeżeli rozpatrywane jest drzewo składniowe opisujące wyrażenie arytmetyczne to rotacje są dozwolone tylko między operacjami, które są łączne - np. dodawanie można obracać względem dodawania lub odejmowania, ale nie względem mnożenia. (pl)
- La rotazione è, in informatica, un procedimento attuato su un albero binario di ricerca per renderlo bilanciato senza intaccare le regole di ordinamento degli elementi o nodi dell'albero. (it)
- Поворот дерева — операція над бінарним деревом, яка змінює його структуру без втручання в порядок елементів. Поворот дерева пересуває одну вершину вверх дерева і одну вниз. Використовується для зміни обрису дерева, особливо для зменшення висоти, пересуваючи менші піддерева вниз, а більші догори, в результаті покращення виконання багатьох операцій на дереві. Домовленість, у який бік зсуваються вершини і є напрямком повороту. (uk)
- 在数据结构中，树旋转（英語：Tree rotation）是对二叉树的一种操作，不影响元素的顺序，但会改变树的结构，将一个节点上移、一个节点下移。树旋转会改变树的形状，因此常被用来将较小的子树下移、较大的子树上移，从而降低树的高度、提升许多树操作的效率。 树的旋转方向有很多不同的定义，有些定义彼此之间还存在冲突。有些人认为旋转方向应该反映节点的移动方向（左子树旋转到父节点的位置为右旋），有些人则认为旋转方向应该反映被旋转的子树是哪棵（左子树旋转到父节点的位置为左旋，与前一种说法相反）。这篇维基文章采用前者的定义：旋转方向为节点的移动方向。 (zh)
- En matemáticas discretas, Rotación de árboles es una operación en un árbol binario que cambia la estructura sin interferir con el orden de los elementos. Un árbol de rotación se mueve hasta un nodo en el árbol y un nodo hacia abajo. Se utiliza para cambiar la forma del árbol, y en particular para disminuir su altura moviendo subárboles más pequeños hacia abajo y subárboles más grande, lo que resulta en un mejor rendimiento de muchas operaciones de los árboles. (es)
- In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations. (en)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| Link from a Wikipa... related subject.
| |
| has abstract
| - En algorithmique, la rotation d'un arbre binaire de recherche permet de changer la structure d'un arbre binaire de recherche ou ABR sans invalider l'ordre des éléments. Une telle rotation consiste en fait à faire remonter un nœud dans l'arbre et à en faire redescendre un autre. Cette opération est très utilisée dans les arbres équilibrés en général car elle permet de réduire la hauteur d'un arbre en faisant descendre les petits sous-arbres et remonter les grands, ce qui permet de « rééquilibrer » les arbres et d'accélérer de nombreuses opérations sur ces arbres. (fr)
- En matemáticas discretas, Rotación de árboles es una operación en un árbol binario que cambia la estructura sin interferir con el orden de los elementos. Un árbol de rotación se mueve hasta un nodo en el árbol y un nodo hacia abajo. Se utiliza para cambiar la forma del árbol, y en particular para disminuir su altura moviendo subárboles más pequeños hacia abajo y subárboles más grande, lo que resulta en un mejor rendimiento de muchas operaciones de los árboles. Existe una inconsistencia en diferentes descripciones en cuanto a la definición de la dirección de las rotaciones. Algunos dicen que la dirección de la rotación depende del lado que los nodos del árbol se desplazan al mismo tiempo que otros dicen que depende de qué nodo toma el lugar de la raíz (enfrente de la primera). En este artículo se adopta el enfoque del lado a donde los nodos quedan cambiados. (es)
- Rotasi pohon adalah suatu operasi dalam pohon biner terurut yang mengubah strukturnya tanpa mengganggu urutan dari elemen. Sebuah rotasi pohon menggerakan satu simpul ke atas dan satu simpul ke bawah dalam pohon. Itu digunakan untuk mengganti bentuk dari pohon dan khususnya untuk mengurangi tinggi pohon tersebut dengan memindahkan sub-pohon yang lebih kecil ke bawah dan sub-pohon yang lebih besar ke atas, menghasilkan peningkatan kemampuan dari banyak operasi pohon. (in)
- 木の回転（きのかいてん、英: tree rotation）は、2分探索木の操作の一種で、要素の順序を崩さずに構造を変更するものである。木の回転は木の中の1つのノードを上にし、別のノードを下にする。木の形状を変化させるのに使い、特に大きい部分木を持ち上げて小さい部分木を下げることで全体の木の高さを低くするのに使う。それによって各種操作の性能を向上させる。 なお、回転の方向によって「右回転」、「左回転」と言うが、どちらが右でどちらが左なのかは必ずしも決まっていない。図示したときにノードがずれる方向を回転の方向とする場合もあれば、どちら側の子ノードが根ノードになるかを回転の方向とする場合もある（前者の逆になる）。本項ではノードがずれる方向を回転の方向とする。 (ja)
- In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations. There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of rotation reflects the direction that a node is moving upon rotation (a left child rotating into its parent's location is a right rotation) while others say that the direction of rotation reflects which subtree is rotating (a left subtree rotating into its parent's location is a left rotation, the opposite of the former). This article takes the approach of the directional movement of the rotating node. (en)
- Rotacja drzewa – operacja polegająca na lokalnej zmianie struktury binarnego drzewa poszukiwań (BST) z zachowaniem porządku wierzchołków. Rotacje stosuje się w drzewach BST do uzyskania wyważenia drzewa i minimalizacji jego wysokości, co prowadzi do zmniejszenia kosztu operacji na drzewie.Matematycznie rotacja jest dopuszczalna jeżeli relacja opisana drzewem jest łączna. Binarne drzewa poszukiwań są generalnie łączne ze względu na łączność relacji porządkującej klucze. Jeżeli rozpatrywane jest drzewo składniowe opisujące wyrażenie arytmetyczne to rotacje są dozwolone tylko między operacjami, które są łączne - np. dodawanie można obracać względem dodawania lub odejmowania, ale nie względem mnożenia. (pl)
- La rotazione è, in informatica, un procedimento attuato su un albero binario di ricerca per renderlo bilanciato senza intaccare le regole di ordinamento degli elementi o nodi dell'albero. (it)
- Поворот дерева — операція над бінарним деревом, яка змінює його структуру без втручання в порядок елементів. Поворот дерева пересуває одну вершину вверх дерева і одну вниз. Використовується для зміни обрису дерева, особливо для зменшення висоти, пересуваючи менші піддерева вниз, а більші догори, в результаті покращення виконання багатьох операцій на дереві. Домовленість, у який бік зсуваються вершини і є напрямком повороту. (uk)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[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)
