Binary search tree: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 27: Line 27:


== Remark ==
== Remark ==
* Besides the methods of [[Sorted sequence|sorted sequences]], binary search trees in the implementation chosen here have a private method [[Binary Search Tree: Remove node]], which receives a pointer <math>p</math> to a binary search tree node and removes id (possibly by removing another node and overwriting the key to be removed with the key of the other node. Prerequisite: <math> p</math>.left <math>\neq</math>void.
* Besides the methods of [[Sorted sequence|sorted sequences]], binary search trees in the implementation chosen here have a private method [[Binary Search Tree:Remove node]], which receives a pointer <math>p</math> to a binary search tree node and removes id (possibly by removing another node and overwriting the key to be removed with the key of the other node. Prerequisite: <math> p</math>.left <math>\neq</math>void.
* There are variants on binary search trees, such as [http://en.wikipedia.org/wiki/AVL_tree AVL trees] and [http://en.wikipedia.org/wiki/Red_black_tree red-black-trees], for which the height of the tree is guaranteed to be in <math>O \log{n}</math> in these variants (because the additional operations in these methods are necessary to maintain logarithmic height are linear in the height of the tree as well.
* There are variants on binary search trees, such as [http://en.wikipedia.org/wiki/AVL_tree AVL trees] and [http://en.wikipedia.org/wiki/Red_black_tree red-black-trees], for which the height of the tree is guaranteed to be in <math>O \log{n}</math> in these variants (because the additional operations in these methods are necessary to maintain logarithmic height are linear in the height of the tree as well.
* The mathematical concept behind this data structure is described in the section on [[Directed Tree#Binary Search Tree|binary search trees]] of page [[Directed Tree]].
* The mathematical concept behind this data structure is described in the section on [[Directed Tree#Binary Search Tree|binary search trees]] of page [[Directed Tree]].

Revision as of 14:34, 17 May 2015


Simple Binary Search tree

General Information

Abstract data structure: Sorted sequence

Implementation invariant:

  1. There is a tree item type with three components:
    1. key is of generic type [math]\displaystyle{ \mathcal{K} }[/math],
    2. left and right of type "pointer to tree item of type [math]\displaystyle{ \mathcal{K} }[/math]."
  2. An object of the binary search tree type contains a pointer root of type "pointer to tree item of type [math]\displaystyle{ \mathcal{K} }[/math]."
  3. 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 methods of sorted sequences, binary search trees in the implementation chosen here have a private method Binary Search Tree:Remove node, which receives a pointer [math]\displaystyle{ p }[/math] to a binary search tree node and removes id (possibly by removing another node and overwriting the key to be removed with the key of the other node. Prerequisite: [math]\displaystyle{ p }[/math].left [math]\displaystyle{ \neq }[/math]void.
  • 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 logarithmic height are linear in the height of the tree as well.
  • The mathematical concept behind this data structure is described in the section on binary search trees of page Directed Tree.