I've been asked to create a movie data baseusing a hash table (w/ linked-list collision resolution) and a BST. Both of them contain a field that points a given structure (we'll call it *pMovie and its of type MOVIE) in memory. For example, if i'm going to insert "The Matrix" into the MOVIE structure and intend to insert MOVIE into the BST and Hash, both of their pMovie fields will point to that structure. So far, I've been able to do all of the project's requirements except for the deletion. For the hash table, it's no problem. However, come deletion for the BST, I'm a at a loss for ideas.
A few of my classmates have thought of creating a flag field to implement what they call "lazy deletion" so they can simply leave the nodes in the tree where they are w/o even physically deleting them. Unfortunately, my teacher didn't approve of that, stating that she wanted the nodes to be physically deleted. That idea is definitely out. :cry:
Besides rotation, which I'm not wholly familiar with, I don't see any other way of doing this. Any ideas you guys could fish out would be most helpful.