- CPU core: 1
- Memory: 2 GB
- Execution time limit: 1 second
- C Compiler: GCC
- compiled with -O3 -std=c11 -Wall
- C Standard: C11
- Use header file only from C Standard Library
- OS: Ubuntu 22.04.1 LTS
Write a C function to create an empty F-heap and support the following instructions. Each line in the input file represents one instruction.
- insert x val : insert an element with key x
- extract : print out the minimum in the heap and delete it
- delete x val : delete the node which has key x and value val
- decrease x val y : decrease the key by y on the node which has key x and value y
- quit : terminate the program
Note that all operations must leave behind properly structured F-heaps. Your functions for (3) and (4) must perform cascading cuts.
- โ2147483648 โค ๐ฅ, val โค 2147483647
- 1 โค ๐ฆ โค 2147483647
- 2 โค ๐ โค 105, ๐ is number of instructions
- The key after decreasing will not exceed the boundary of 32-bit signed integer.
Program the search, insert, and delete operations for red-black trees.
- search x : Print out the color of the tree node if the element x exists. If the element x does not exist, print out "Not found\n".
- insert x : Add an integer x to the red-black tree. If x already exists, do nothing.
- delete x : Delete the element x if the element x exists. (Note: The textbook did not describe how to implement delete on red-black tree. Students can write your own delete to satisfy the constraint of the red-black tree.)
The instructions are insert, search, delete and quit. Instruction quit means you should terminate your program.
Please make sure that git, gcc & make
has been installed successfully.
Run
$ make
to compile the src files.
You can now enter the output directory and check out the outputs.
For testing, simly run
$ chmod +x test.sh
$ ./test.sh
to check if the output is valid.