Toothbrush Receding Gums

representation and manipulation of trees.

This extra task on binary trees, is information from wikipedia, clearing my doubts .

A binary search tree is a particular type of binary tree that has a data structure in a tree used in computing.


all empty tree is a binary search tree.
A nonempty binary tree, rooted in R is a binary search tree if:
• In If you have left subtree, the root R must be greater than the maximum value stored in the hive
left and the left subtree is a binary tree search
.

• If you have the right subtree, the root R must be less than the minimum value stored in the hive
right, and that the right subtree is a binary tree search
.

may have different binary search trees for the same set of elements.

The interest of binary search trees (ABB) is that their tour inorder provides the elements sorted in increasing and that the search for an item is usually very efficient.
Depending on user needs dealing with a structure of this type may allow strict equality in, any or both of the subtrees hanging from the root. Allow the use of equality leads to the appearance of double values \u200b\u200band makes the search more complex. SEARCH
The search is access to the root of the tree, if the element to locate it matches the search has completed successfully, if the item is less you search the left subtree and if it is greater in the right . If a leaf node is reached and the element was not found are not supposed to exists in the tree. Note that the search on this type of tree is very efficient, is a logarithmic function. The maximum number of comparisons would need to determine whether an item is in a binary search tree would be between [log2 (N +1)] and N, N being the number of nodes. The search for an item in an ABB (binary search tree) can be done in two ways, iterative or recursive.



Example iterative version in the C programming language, assuming that we are looking for a key hosted on a node where the relevant "fact" that we need find:


data Buscar_ABB (abb t, key k)

abb {p;
data e;
e = NULL;
p = t;
if (! isEmpty (p))

{while (! isEmpty (p) & & (p-> k! = k))

{if (k \u0026lt; p-> k)

{p = p-> l;

} if (p-> k \u0026lt;k)

{p = p-> r;}


} if (! IsEmpty (p) & & (p-> d! = NULL)) {

copiaDato e = (p-> d);}


} return e;}



Insertion Insertion is similar to the search and can be given an iterative solution both as a resource. If we initially empty tree as a parameter creates a new node as a single content item to insert. If not is, it checks if the given element is less than the initial tree root that is inserted into the left subtree and if more is inserted into the right subtree. In this way the inserts are made in the leaves.


As in the case of the search can be several alternatives when implementing the inclusion in the ADT (abstract data type), and is the decision to take when the item (or key item) to add is already in the tree, this may be modified or ignored it insertion. It is obvious that this operation modifies the losing ABB previous version. PROC

InsertarABB (tree: TABB; data: TElement)


ele VARIABLES: TElement

HOME IF (ABBVacío (tree)) THEN
tree \u0026lt;- NEW (TNodoABB)
tree ^. left \u0026lt;- NULL
tree ^. der \u0026lt;- NULL
tree ^. elem \u0026lt;- data


otherwise


InfoABB ele = (tree)
SI (dato.clave \u0026lt;ele.clave) THEN
InsertarABB (tree ^. Left, data)

otherwise


InsertarABB (tree ^. dch, data)
FINSI
FINSI
FIN

Disposal:
The operation deletion is more complicated, the search and insertion.
There are several cases to consider:
* Remove a node or leaf node with no children, only clears and sets to zero the pointing of his father.
* Remove a child node to a subtree: elnodo clears and is assigned its subtree subtree son as his father. * Remove a child node with two hives: the solution is to replace the value of the node by its predecessor or its successor in the inorder and then delete this node.


inorder Its predecessor is the node to the right of its left subtree (left-most node of the subtree), and its successor node to the left of its right subtree (subtree node lower right).


reviewing and understand a little better.
this information can be found at: wikipedia / / binary tree