You get a bonus - 1 coin for daily activity. Now you have 1 coin

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

Lecture





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:

  1. found node is a leaf - it is simply deleted (Fig. 1);


  Laboratory work number 13. SEARCH BY TREE WITH EXCLUSION


  1. the found node has only a son - in this case the son moves to the place of the removed father (Fig. 2);


  Laboratory work number 13. SEARCH BY TREE WITH EXCLUSION


  1. 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


  Laboratory work number 13. SEARCH BY TREE WITH EXCLUSION


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).


  Laboratory work number 13. SEARCH BY TREE WITH EXCLUSION


The final version of the tree after removal


  Laboratory work number 13. SEARCH BY TREE WITH EXCLUSION


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.

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Structures and data processing algorithms.

Terms: Structures and data processing algorithms.