search

kdn251 / interviews

Everything you need to know to get the job.
https://www.youtube.com/channel/UCKvwPt6BifPP54yzH99ff1g?view_as=subscriber
MIT License
63.67k stars 12.91k forks source link

binary search tree #158

Open markocska opened 4 years ago

markocska commented 4 years ago

Hi,

I would maybe add for binary search trees that the O(log(n)) complexities are correct for the average complexities. For example if the tree has a "shape of a line" (every node has a child on the left : 10->9->8->7->6->5->4->3->2->1 then the worst case complexities will be O(n) ( search, insert, delete, access). If the values are deliberately written for the average complexities, then sorry for the disturbance :)

Kind Regards, Mark

Dzhango commented 3 years ago

I think you are right. I did see him using BST with a balancing factor on youtube, so pontetially O(logn) is implied.