Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Weight-balanced tree
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, weight-balanced binary trees (WBTs) are a type of <a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">self-balancing binary search trees</a> that can be used to implement <a href="/facts/Set_(abstract_data_type)/ovoXUmF9">dynamic sets</a>, <a href="/facts/Associative_array/IFGd2xcP">dictionaries</a> (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 <a href="/facts/Donald_Knuth/GozNzDM6">Knuth</a>. </p><p>A well known example is a <a href="/facts/Huffman_coding/dBgMBz48">Huffman coding</a> of a <a href="/facts/Text_corpus/bYeEQQdh">corpus</a>. </p><p>Like other self-balancing trees, WBTs store bookkeeping information pertaining to balance in their nodes and perform <a href="/facts/Tree_rotation/R3SlGyI0">rotations</a> 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 <a href="/facts/AVL_tree/DfexIbS6">AVL trees</a> (using information about the height of subtrees) and <a href="/facts/Red%25E2%2580%2593black_tree/ckgWTV7G">red–black trees</a> (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 <a href="/facts/Order_statistic_tree/WjpoSRY4">order statistic tree</a>, viz., getting the n'th largest element in a set or determining an element's index in sorted order. </p><p>Weight-balanced trees are popular in the <a href="/facts/Functional_programming/cdxqPEIM">functional programming</a> community and are used to implement sets and maps in <a href="/facts/MIT_Scheme/GoT5CKoC">MIT Scheme</a>, <a href="/facts/SLIB/Dzka5VtY">SLIB</a>, <a href="/facts/Standard_ML_of_New_Jersey/5WUYMHsD">SML-NJ</a>, and implementations of <a href="/facts/Haskell_(programming_language)/4Htv9WLu">Haskell</a>. </p>