2-3 tree
Wikipedia on Answers.com:
Top
2-3 tree
In computer science, a 2-3 tree is a type of data structure, a tree where every node with children (internal node) has either two children (2-node) and one data element or three children (3-nodes) and two data elements. Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements.[1]
-
2 node
-
3 node
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.
|
Contents
|
Properties
- Every non-leaf is a 2-node or a 3-node. A 2-node contains one data item and has two children. A 3-node contains two data items and has 3 children.
- All leaves are at the same level (the bottom level)
- All data are kept in sorted order
- Every 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.
References
- ^ Gross, R. Hernández, J. C. Lázaro, R. Dormido, S. Ros (2001). Estructura de Datos y Algoritmos. Prentice Hall. ISBN 84-205-2980-X
See also
External links
- 2-3 Trees Complete Description
- 2-3 Tree Java Applet
- 2-3 Tree In-depth description
- 2-3 Tree in F#
- 2-3 Tree in Python
|
||||||||||||||||||||||||||
|
|||||||||||||||||||||||
 |
This computer programming-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
Related Videos:
Top
2-3 tree
Post a question - any question - to the WikiAnswers community:
Copyrights:
Wikipedia on Answers.com
This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article 2-3 tree.
Read more