Deletion (Another Example)BinarySearchTrees福
Binary Search Trees 11 Deletion (Another Example) v w z v
PerformanceConsider a dictionarywith n itemsimplementedbymeansof abinary searchtreeof height hthe space used is O(n)methodsfind,insertandremovetake O(h)timeTheheighthisO(n)inthe worst case andO(log n) in the bestcaseLater,wewill trytokeep h =O(log n).Reviewthe12BinarySearchTreespast
Binary Search Trees 12 Performance Consider a dictionary with n items implemented by means of a binary search tree of height h ◼ the space used is O(n) ◼ methods find, insert and remove take O(h) time The height h is O(n) in the worst case and O(log n) in the best case Later, we will try to keep h =O(log n). Review the past