Binary search tree: Difference between revisions
Jump to navigation
Jump to search
(→Remark) |
No edit summary |
||
| Line 1: | Line 1: | ||
[[Category:Checkup]] | |||
[[Category:Data Structures]] | [[Category:Data Structures]] | ||
[[Category:Trees]] | [[Category:Trees]] | ||
| Line 6: | Line 8: | ||
<div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Binary Search Tree</div> | <div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Binary Search Tree</div> | ||
<div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center"> | <div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center">[[Sorted sequence]]</div> | ||
<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/binary-search-tree-1938 Openlearnware]</div> | <div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/binary-search-tree-1938 Openlearnware]</div> | ||
| Line 13: | Line 15: | ||
== General Information == | == General Information == | ||
''' Abstract data structure:''' | |||
[[Sorted sequence]] | [[Sorted sequence]] | ||
'''Implementation invariant:''' | |||
# There is a tree item type with three components: | # There is a tree item type with three components: | ||
Revision as of 06:31, 1 October 2014
General Information
Abstract data structure: Sorted sequence
Implementation invariant:
- There is a tree item type with three components:
- key is of generic type [math]\displaystyle{ \kappa }[/math]
- left and right of type "pointer to tree item of type [math]\displaystyle{ \kappa }[/math]"
- An object of the binary search tree type contains a pointer root of type "pointer to tree item of type [math]\displaystyle{ \kappa }[/math]"
- The pointer root points to a well-formed binary search tree. In accordance with the definition of directed trees, "well-formed" means that, for any node, there is exactly one path from the root to that node.
Remark
- Besides the methos of sorted sequences, binary search trees have a private method Binary Search Tree:Remove node, which receives a pointer p to a binary search tree node and removes id (possibly by removeing another node and overwriting the key to be removed with the key of the other node. Prerequisite: [math]\displaystyle{ p.left \neq void }[/math]
- There are variants on binary search trees, such as AVL trees and red-black-trees, for which the height of the tree is guaranteed to be in [math]\displaystyle{ O \log{n} }[/math] in these variants (because the additional operations in these methods are necessary to maintain logatihmic height are linear in the height of the tree as well=.
- For further information, see section "Binary search tree" of page Directed Tree.