Laboratory work number 12. "SEARCH BY WOOD WITH INCLUSION"

Objective: to master the algorithm and method of inserting elements of a binary tree.


The task of the work: to master the skills of writing programs for the study of methods of inserting elements of a binary tree in the programming language PASCAL.


Operating procedure :

• 
  study the description of the laboratory work;

• 
  according to the task given by the teacher, to develop an algorithm for the program for solving the problem;

• 
  write a program in PASCAL;

• 
  debug the program;

• 
  to solve a task;

• 
  issue a report.

Brief theory

SEARCH BY BINARY TREE

To insert an element into a tree, you first need to search the tree for a given key. If such a key is present, the program is terminated; if not, an insertion occurs. The duration of the search operation (the number of nodes that need to be searched for this purpose) depends on the tree structure. Indeed, a tree can be degenerate into a unidirectional list (have a single branch) —this tree can arise if the elements entered the tree in ascending (descending) order of their keys. In this case, the search time will be the same as the unidirectional list, i.e. on average, you will have to sort through N / 2 elements. The greatest effect of using the tree is achieved in the case when the tree is "balanced". In this case, the search will have to go through no more than log ₂ N.


INCLUSION OF THE ELEMENT IN THE TREE

To include a new entry in the tree, first of all you need to find the node to which you can “hang” (attach) a new element. The algorithm for finding the desired node is the same as when searching for a node with a given key. This node will be found at that moment, when the next link, defining the branch of the tree in which to continue the search, will be the NIL link.

However, the search procedure cannot be used directly, because at the end of the calculation, its value does not fix the node from which the NIL link was selected. We modify the description of the search procedure so that, as its side effect, there is a link to the node where the specified key was found (in the case of a successful search), or a link to the node after which processing the search was stopped (in the case of an unsuccessful search).

Algorithm

Consider the algorithm for inserting a node into a binary tree.

Insert the node with the number 150, then it will become the right son of the node with the number 120, since it is large in value of node number 120, but less than the value of node in the head of the tree.

P - working pointer

Q - pointer lagging behind P by one step

V is a pointer to the element that will be inserted into the binary tree.





Illustration of the process of inserting a node 150, in accordance with the above algorithm (in red, new links in the tree are highlighted).





The final version of the tree after insertion:





Program

Pseudocode pascal

Q = nil Q = nil

P = Tree P = Tree

While (P <> nil) do While (P <> nil) do

Q = P Begin

If key = k (P) then Q = P;

search = If key = P ^ .k then

return begin

EndIf search: = P;

If key <k (p) then = "" exit; <br = "">
P = left (P) End;

else if key

P = right (P) P: = P ^ .left;

Endif else

EndWhile P: = P ^ .right;

V = maketree (key, rec) End;

If key <k (q) then = "" v = "maketree (key, rec) <br">
else If key <q ^ .k then <br = "">
Right (Q) = VQ ^ .left: = V

Endif else

search = VQ ^ .right: = V;

Return search: = V

Tasks

Using a random number generator to form a binary tree consisting of 5 elements (provide manual input of elements). Moreover, the numbers should be in the range from -99 to 99. Perform a search with the insertion of elements in accordance with the following options for tasks:


1. The numbers are multiples of N.

2. Odd numbers.

3. Numbers> N.

4. Prime numbers.

5. Numbers to choose from.

6. Random number.

7. Compound numbers.

8. Numbers from X to Y.

9. Numbers whose sum of digits (by module) is> N.

10. Numbers whose sum of numbers (by module) is <N.

11. Numbers, the sum of the digits (modulo) of which lies in the interval from X to Y.

12. Numbers, taken in absolute value, the square root of which is an integer.

where: N, X, Y - is set by the teacher.