<p>An unsorted array-based list of integers allows for constant-time insert simp

Question

<p>An unsorted array-based list of integers allows for constant-time insert simply by adding a new integer at the end of the list.Unfortunately,searching for the integer with key X requires time&#160;&#952;(n) in the average case for a list of n integers. On the other hand,a sorted array-based list of n integers can be searched in&#160;&#952;(log n) time by using binary search.However, inserting a new integer requires&#160;&#952;(n) time since many integers might be shifted in the array.How might data be organized to support both insertion and search in&#160;&#952;(log n) time?</p>

Explanation / Answer

A balanced binary search tree, whether red black, or other supports insertion and search in T(logn) time. In computer science, a self-balancing (or height-balanced) binary search tree is any node based binary search tree that automatically keeps its height (number of levels below the root) small in the face of arbitrary item insertions and deletions.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.