“2–3 tree”的意思、由来-开放百科全书

词条

2–3 tree

释义

Definitions
Properties
Operations
Searching Insertion
See also
References
External links

{{Infobox data structure|name=2-3 tree|type=tree|invented_by=John Hopcroft|invented_year=1970||space_avg= O(n)|space_worst= O(n)|search_avg= O(log n)|search_worst= O(log n)|insert_avg= O(log n)|insert_worst= O(log n)|delete_avg= O(log n)|delete_worst= O(log n)}}

In computer science, a 2–3 tree is a tree data structure, 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. According to Knuth, "a B-tree of order 3 is a 2-3 tree." Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements.^[1]^[2] 2−3 trees were invented by John Hopcroft in 1970.^[3]

2–3 trees are balanced, meaning that each right, center, and left subtree contains the same or close to the same amount of data.

Definitions

We say that an internal node is a 2-node if it has one data element and two children.

We say that an internal node is a 3-node if it has two data elements and three children.

We say that {{mvar|T}} is a 2–3 tree if and only if one of the following statements hold:

{{mvar|T}} is empty. In other words, {{mvar|T}} does not have any nodes.
{{mvar|T}} is a 2-node with data element {{mvar|a}}. If {{mvar|T}} has left child {{mvar|L}} and right child {{mvar|R}}, then
- {{mvar|L}} and {{mvar|R}} are non-empty 2–3 trees of the same height;
- {{mvar|a}} is greater than each element in {{mvar|L}}; and
- {{mvar|a}} is less than or equal to each data element in {{mvar|R}}.
{{mvar|T}} is a 3-node with data elements {{mvar|a}} and {{mvar|b}}, where {{mvar|a}} {{Math| <}} {{mvar|b}}. If {{mvar|T}} has left child {{mvar|L}}, middle child {{mvar|M}}, and right child {{mvar|R}}, then
- {{mvar|L}}, {{mvar|M}}, and {{mvar|R}} are non-empty 2–3 trees of equal height;
- {{mvar|a}} is greater than each data element in {{mvar|L}} and less than or equal to each data element in {{mvar|M}}; and
- {{mvar|b}} is greater than each data element in {{mvar|M}} and less than or equal to each data element in {{mvar|R}}.

Properties

Every internal node is a 2-node or a 3-node.
All leaves are at the same level.
All data is kept in sorted order.

Operations

Searching

Searching for an item in a 2–3 tree is similar to searching for an item in a binary search tree. Since the data elements in each node are ordered, a search function will be directed to the correct subtree and eventually to the correct node which contains the item.

Let {{mvar|T}} be a 2–3 tree and {{mvar|d}} be the data element we want to find. If {{mvar|T}} is empty, then {{mvar|d}} is not in {{mvar|T}} and we're done.
Let {{mvar|r}} be the root of {{mvar|T}}.
Suppose {{mvar|r}} is a leaf. If {{mvar|d}} is not in {{mvar|r}}, then {{mvar|d}} is not in {{mvar|T}}. Otherwise, {{mvar|d}} is in {{mvar|T}}. In particular, {{mvar|d}} can be found at a leaf node. We need no further steps and we're done.
Suppose {{mvar|r}} is a 2-node with left child {{mvar|L}} and right child {{mvar|R}}. Let {{mvar|e}} be the data element in {{mvar|r}}. There are three cases:
- If {{mvar|d}} is equal to {{mvar|e}}, then we've found {{mvar|d}} in {{mvar|T}} and we're done.
- If , then set {{mvar|T}} to {{mvar|L}}, which by definition is a 2–3 tree, and go back to step 2.
- If , then set {{mvar|T}} to {{mvar|R}} and go back to step 2.
Suppose {{mvar|r}} is a 3-node with left child {{mvar|L}}, middle child {{mvar|M}}, and right child {{mvar|R}}. Let {{mvar|a}} and {{mvar|b}} be the two data elements of {{mvar|r}}, where . There are four cases:
- If {{mvar|d}} is equal to {{mvar|a}} or {{mvar|b}}, then {{mvar|d}} is in {{mvar|T}} and we're done.
- If , then set {{mvar|T}} to {{mvar|L}} and go back to step 2.
- If , then set {{mvar|T}} to {{mvar|M}} and go back to step 2.
- If , then set {{mvar|T}} to {{mvar|R}} and go back to step 2.

Insertion

Insertion works by searching for the proper location of the key and adding it there. If the node becomes a 4-node then the node is split into two 2-nodes and the middle key is moved up to the parent. The diagram illustrates the process.

References

1. ^{{Cite book | title = Estructura de Datos y Algoritmos | first1 = R. Hernández, J. C. Lázaro, R. Dormido, S. Ros | last1 = Gross | publisher = Prentice Hall | year = 2001 | isbn = 84-205-2980-X | postscript = }}
2. ^{{cite book|first1=Alfred V.|last1=Aho|first2=John E.|last2=Hopcroft|first3=Jeffrey D.|last3=Ullman|title=The Design and Analysis of Computer Algorithms|publisher=Addison-Wesley|year=1974}}, p.145-147
3. ^{{Cite book|title = Introduction to Algorithms|last = Cormen|first = Thomas|publisher = The MIT Press|year = 2009|isbn = 978-0262033848|location = London|pages = 504}}

External links

[https://ysangkok.github.io/js-clrs-btree/btree.html 2–3 Tree Visualization] (click one "Init" button)
2–3 Tree In-depth description
2–3 Tree in F#

1 : B-tree

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。