Laboratory work number 13. "SEARCH BY TREE WITH EXCLUSION"

Objective: to explore and explore search methods using the tree. The task of the work: to master the skills of writing programs for searching with the help of a binary tree in the PASCAL programming language. 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 Removing a tree node should not disrupt the orderliness of the tree. When deleting the following options for the location of nodes: found node is a leaf - it is simply deleted (Fig. 1); the found node has only a son - in this case the son moves to the place of the removed father (Fig. 2); the removed father has two sons - in this case the main difficulty is to remove the father, since one arrow enters the removed vertex, and two go out. In this case, you need to find a suitable link of the subtree, which could be inserted in place of the deleted, and this suitable link should simply move. Such a link always exists: - this is the rightmost element of the left subtree (to reach this link, you must go to the next vertex on the left branch and then go to the next vertices only on the right branch until the next link is nil); - this is the leftmost element of the right subtree (to reach this link, you must go to the next vertex on the right branch and then go to the next vertices only on the left branch until the next such link is nil). Obviously, such suitable links may have no more than one branch. Algorithm Consider an algorithm in which, instead of the node being deleted, the leftmost node of the right subtree is put. Remove the node with the number 150, then in its place will be the element at number 152, because it is the leftmost of the right subtree. We introduce the following notation: P - working pointer Q - pointer lagging behind P by one step V - pointer to the element that will replace the node to be deleted. T - pointer, one step behind V S - pointer, ahead of V by one step Sample program to remove elements of a binary tree (Pseudocode) Q = nil P = Tree While (P <> nil) and (K (P) <> key) do {find the node with the desired key} If key <k (p) then = "" p = "Left (P) <br"> Else P = Right (P) Endif Endwhile If P = nil then "Key not found" {check if there is no such item} Return {exit} Endif If Left (P) = nil then V = Right (P) {if the left link is nil Else If Right (P) = nil then V = Left (P) Else GetNode (P) T = p V = Right (P) S = Left (V) While S <> nil {search itself} T = V {left el-nta} V = S {right subtree} S = Left (V) Endwhile If T <> P then "V is not a son" Left (T) = Right (V) Right (V) = Right (P) Endif Left (V) = Left (P) If Q = nil then "p - root" Tree = V Return Endif If P = Left (Q) then Left (Q) = V Else Right (Q) = V Endif Endif Endif FreeNode (P) Return Illustration of the process of removing node 150, in accordance with the above algorithm (in red, new links in the tree are highlighted). The final version of the tree after removal

Tasks

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

1. The numbers are multiples of N.

2. Odd numbers.

3. Numbers> N.

4. Numbers <N.

5. Numbers to choose from.

6. Prime numbers.

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.