The university gave the following task:

Write a program to work on operator requests with an ordered table, implemented as a binary search tree with firmware.

Key is an integer. Information - a string of arbitrary length.

The tree node contains a key, pointers to the right and left subtrees, a pointer to the next node in the reverse order of the keys and a pointer to the information field.

When performing a delete and add operation, the tree should not lose order.

I have the following questions:

  1. What is the pointer to the next node in reverse order? Those. is it a pointer to the previous node?

  2. How can I maintain tree ordering when deleting and adding an item?

    How rational is the following idea: To bypass the modified tree and build a new tree from it?

  3. Do I understand correctly that by firmware is meant the link of leaf pointers to the root of a tree?

  • one
    1) Do you know what a tree walk is in reverse order? So, the “next node in the reverse order” is the node following the data, when going around in the reverse order. Look at the outline. - VladD
  • one
    2) The algorithm for adding a node to a stitched tree is, for example, in TAOCP. To build a new tree is usually irrational. - VladD
  • 3
    3) No. Read what a stitched tree is , it explains. In short: firmware is the arrangement of pointers to the next / previous nodes in some places in the reverse order. - VladD
  • 1) The left subtree, right, then the node is bypassed 3) As I understood it, for each traversal of the tree its own firmware. Should the thread point to the next item on the selected walk? In red, I marked prntscr.com/6yg3oc . Did I understand the firmware correctly? - iluxa1810
  • 1) Well, now you know the answer 3) firmware only for reverse order, EMNIP. - VladD

0