I'm trying to solve Question 3 c), originating from here: https://15445.courses.cs.cmu.edu/fall2021/files/hw2-clean.pdf, solutions are available here: https://15445.courses.cs.cmu.edu/fall2021/files/hw2-sols.pdf (so this is no homework ...)
Link to image of question (can not embed images due to low reputation) Extendible hashing question
Starting from the table in the image linked above, delete keys 10,12,7,24 & 8.
The global depth seems to start at 3 as there are 3 bits used.
There are 2 questions:
- Which deletion causes the first reduction in local depth? That's the deletion of 7, I understand that one.
- Which deletion causes the first reduction in global depth? The answer is supposed to be "24", but for the life of me, I don't see it. My answer would be "None of the above". Can somebody shed some light on this please?
edit: I think I understand it, after deletion of 24, the global depth can decrease to 2. All indices ending with the same 2 bits point to the same bucket, so they can be merged. It was not clear to me, because that rule is not described in the assignment, I guess it's a general rule the assignment creator assumed.