| dbo:abstract
|
- In computer science, weight-balanced binary trees (WBTs) are a type of self-balancing binary search trees that can be used to implement dynamic sets, dictionaries (maps) and sequences. These trees were introduced by Nievergelt and Reingold in the 1970s as trees of bounded balance, or BB[α] trees. Their more common name is due to Knuth. Like other self-balancing trees, WBTs store bookkeeping information pertaining to balance in their nodes and perform rotations to restore balance when it is disturbed by insertion or deletion operations. Specifically, each node stores the size of the subtree rooted at the node, and the sizes of left and right subtrees are kept within some factor of each other. Unlike the balance information in AVL trees (using information about the height of subtrees) and red–black trees (which store a fictional "color" bit), the bookkeeping information in a WBT is an actually useful property for applications: the number of elements in a tree is equal to the size of its root, and the size information is exactly the information needed to implement the operations of an order statistic tree, viz., getting the n'th largest element in a set or determining an element's index in sorted order. Weight-balanced trees are popular in the functional programming community and are used to implement sets and maps in MIT Scheme, SLIB and implementations of Haskell. (en)
- Drzewo o ograniczonym zrównoważeniu (ang. binary search tree of bounded balance, BB-drzewo, ang. weight balanced binary tree, wt-tree) – zrównoważone binarne drzewo poszukiwań (BST), w którym wielkość lewego i prawego poddrzewa każdego węzła jest nie większa niż o stały czynnik Drzewa takie nie są w pełni zrównoważone (w porównaniu do drzew czerwono-czarnych czy drzew AVL). Warunek, iż jedno z poddrzew jest co najwyżej większe o czynnik jest równoważne stwierdzeniu, że jedno z poddrzew jest wyższe o stały czynnik. W praktyce takie drzewa są proste w implementacji i całkiem szybkie, gwarantując logarytmiczną złożoność wszystkich operacji, a tym samym zabezpieczając przed patologiczną sytuacją wysokiego niezrównoważenia. Drzewa te bywają również użyteczne przy implementacji operacji na zbiorach (takich jak suma, przecięcie – cześć wspólna, różnica, różnica wykluczająca itp.). Drzewa te przywracają częściowe zrównoważenie przy pomocy pojedynczej lub podwójnej rotacji. Drzewa te w każdym węźle przechowują czwórkę: klucz (z wartością), wskaźnik do lewego poddrzewa, wskaźnik do prawego poddrzewa oraz liczbę określającą rozmiar (ilość kluczy) drzewa. Drzewa te są wyjątkowo dobre w przypadku implementacji w językach funkcyjnych, jako że w drzewach tych rzadko dokonuje się procedury wyważania, a w językach funkcyjnych procedura wyważania prowadziła do nowej alokacji pamięci z uwagi na to że raz stworzonych struktur danych nie można już zmienić (w przeciwieństwie do języków imperatywnych, gdzie można dokonać aktualizacji drzewa w miejscu). Parametr najczęściej posiada wartość większą niż 4.646, z uwagi na pewne teoretyczne właściwości rotacji na tych drzewach. W praktyce najmniejsza jego wartość to 5, co przekłada się na największą dopuszczalną różnicę pomiędzy wysokościami dowolnych poddrzew wynoszącą 3. Okazuje się jednak, że prowadzi to do błędnego zachowania algorytmu (przy operacji usuwania elementu mogą powstać drzewa które nie spełniają warunku zbalansowania). Jedynie pewne szczególne wartości gwarantują to zachowanie przy wszystkich możliwych scenariuszach dodawania i usuwania elementów. Szczegóły w referencjach. (pl)
- 在计算机科学里面，加权平衡树（WBTs）是一种可以用来实现集合、字典（映射）和序列的平衡树。这些树结构在20世纪70年代被Nievergelt和Reingold作为有界限的自平衡树或BB[α]树提出。让这些结构普及的是高德纳。 就像其他自平衡树一样，加权平衡树储存的账簿信息可以在树结构被插入和删除操作打乱时，通过平衡结点和操作树旋转来使树结构重新达到平衡。特别的地方是，加权平衡树的每个结点储存这个结点下子树的大小，并且这个结点左右子树的大小保持着某种内在联系。不同于AVL树（储存子树的高度）和红黑树（储存虚构的“颜色”位），加权平衡树储存记账信息的方式是对应用真正有用的属性：一棵树下元素的数量等于它的根的大小，然而这个根的大小是一个用来实现顺序统计树操作的有用数据，也就是说，可以得到一个大小为n的集合下的最大元素或者决定一个顺序结构下一个元素的索引。 加权平衡树在函数程式语言社区下面非常受欢迎以及被用来实现MIT Scheme的集合和映射结构还有Haskell语言的实现。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageInterLanguageLink
| |
| dbo:wikiPageLength
|
- 14153 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdf:type
| |
| rdfs:comment
|
- 在计算机科学里面，加权平衡树（WBTs）是一种可以用来实现集合、字典（映射）和序列的平衡树。这些树结构在20世纪70年代被Nievergelt和Reingold作为有界限的自平衡树或BB[α]树提出。让这些结构普及的是高德纳。 就像其他自平衡树一样，加权平衡树储存的账簿信息可以在树结构被插入和删除操作打乱时，通过平衡结点和操作树旋转来使树结构重新达到平衡。特别的地方是，加权平衡树的每个结点储存这个结点下子树的大小，并且这个结点左右子树的大小保持着某种内在联系。不同于AVL树（储存子树的高度）和红黑树（储存虚构的“颜色”位），加权平衡树储存记账信息的方式是对应用真正有用的属性：一棵树下元素的数量等于它的根的大小，然而这个根的大小是一个用来实现顺序统计树操作的有用数据，也就是说，可以得到一个大小为n的集合下的最大元素或者决定一个顺序结构下一个元素的索引。 加权平衡树在函数程式语言社区下面非常受欢迎以及被用来实现MIT Scheme的集合和映射结构还有Haskell语言的实现。 (zh)
- In computer science, weight-balanced binary trees (WBTs) are a type of self-balancing binary search trees that can be used to implement dynamic sets, dictionaries (maps) and sequences. These trees were introduced by Nievergelt and Reingold in the 1970s as trees of bounded balance, or BB[α] trees. Their more common name is due to Knuth. Weight-balanced trees are popular in the functional programming community and are used to implement sets and maps in MIT Scheme, SLIB and implementations of Haskell. (en)
- Drzewo o ograniczonym zrównoważeniu (ang. binary search tree of bounded balance, BB-drzewo, ang. weight balanced binary tree, wt-tree) – zrównoważone binarne drzewo poszukiwań (BST), w którym wielkość lewego i prawego poddrzewa każdego węzła jest nie większa niż o stały czynnik Drzewa takie nie są w pełni zrównoważone (w porównaniu do drzew czerwono-czarnych czy drzew AVL). Warunek, iż jedno z poddrzew jest co najwyżej większe o czynnik jest równoważne stwierdzeniu, że jedno z poddrzew jest wyższe o stały czynnik. W praktyce takie drzewa są proste w implementacji i całkiem szybkie, gwarantując logarytmiczną złożoność wszystkich operacji, a tym samym zabezpieczając przed patologiczną sytuacją wysokiego niezrównoważenia. Drzewa te bywają również użyteczne przy implementacji operacji na zbi (pl)
|
| rdfs:label
|
- Drzewo o ograniczonym zrównoważeniu (pl)
- Weight-balanced tree (en)
- 加权平衡树 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
