Explore BrainMass
Share

Hashing: separate chaining method

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Are there any advantages to using binary search trees instead of linked lists in the separate chaining method? Please Explain.

© BrainMass Inc. brainmass.com March 21, 2019, 7:59 pm ad1c9bdddf
https://brainmass.com/computer-science/trees/hashing-separate-chaining-method-316934

Solution Preview

To be precise, it should be balanced binary tree as in worst case a normal binary tree can reduce down to a single chain similar to a linked list - for example it can happen when all the insertions happen on the right or on the left.

A brief comparative analysis of linked list and balanced binary search tree is given below to help you understand the topic better. Below, "n" refers to number of elements in the linked list / balanced binary search tree, and "lg" refers to log-base-2.

Adding a new node in linked list is constant time i.e. O(1) operation if you are maintaining an unsorted ...

Solution Summary

The solution makes use of brief comparative analysis of linked list and balanced binary search tree.

$2.19