LSM-Tree Memtable Using a Skip List

Write a C program that implements a skip list memtable for key-value pairs.

Requirements:

• Define MAX_LEVEL as 4 and a Node struct with key, value, and forward array of size MAX_LEVEL
• Implement create_node(key, value, level) that allocates a node
• Implement random_level() that returns a level from 0 to MAX_LEVEL-1 with probability 1/2 for each increment (coin flip)
• Implement skiplist_insert(list, key, value): find insertion position at each level, link the new node
• Implement skiplist_search(list, key): return value or -1 if not found
• Implement skiplist_print(list): print all key-value pairs at level 0
• Insert these pairs: (10,100), (20,200), (15,150), (5,50), (25,250), (30,300)
• Print the skip list after all insertions
• Search for keys: 15, 100 (not found)
• Print the level of each node to show the probabilistic structure
• Calculate and print the average number of comparisons per search vs a linked list
• Include a note about why skip lists are preferred over balanced trees for memtables