2-3 tree

2-3 tree

A 2-3 tree in computer science is a type of data structure, a B-tree where every node with children (internal node) has either two children and one data element (2-nodes) or three children and two data elements (3-nodes). Nodes on the outside of the tree (leaf nodes) have no children and two data elements.

2-3 trees are an isometry of AA trees, meaning that they are equivalent data structures. In other words, for every 2-3 tree, there exists at least one AA tree with data elements in the same order. 2-3 trees are balanced, meaning that each right, center, and left subtree contains the same or close to the same amount of data.

Properties

* Every non-leaf node has 2 or 3 children
* All leaves are at the same level (the bottom level)
* All data is kept in sorted order
* Every non-leaf node will contain 1 or 2 fields.

Non-leaf nodes

These contain one or two fields which indicate the range of values in its subtrees. If a node has two children, it will have one field; if the node has three children, it will have two fields. Each non-leaf node will contain a value in field 1 which is greater than the largest item in its left sub-tree, but less than or equal to the smallest item in its right sub-tree (or center sub-tree, if it has three children). If that node has three children, field 2 contains a value which is greater than the largest value in the center sub-tree, but less than or equal to the smallest item in its right sub-tree. The purpose of these values is to direct a search function to the correct sub-tree and eventually to the correct data node.

See also

* B-tree
* AA tree (a 2-3 tree implemented using a binary tree)
* 2-3-4 tree

External links

* [http://www.cs.ucr.edu/cs14/cs14_06win/slides/2-3_trees_covered.pdf 2-3 Trees Complete Description]
* [http://slady.net/java/bt/ B-Tree animation (Java Applet)]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Tree — /tree/, n. Sir Herbert Beerbohm /bear bohm/, (Herbert Beerbohm), 1853 1917, English actor and theater manager; brother of Max Beerbohm. * * * I Woody perennial plant. Most trees have a single self supporting trunk containing woody tissues, and in …   Universalium

  • Tree — (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree, oak, do ry… …   The Collaborative International Dictionary of English

  • Tree bear — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree beetle — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree bug — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree cat — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree clover — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree crab — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree creeper — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree cricket — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree crow — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”