Please read the new rule regarding the restriction on the use of AI tools. ×

JasonMendoza2008's blog

Randomized Binary Search Tree
By JasonMendoza2008, history, 3 hours ago, In English

I saw somewhere that if you were to pick randomly the next element to insert when building a binary search tree from an array, you would have 1/3 on the left and 2/3 on the right (or conversely) on average. I get that the best case is half-half and the worst case in everything in one of the branches but how do get formally to the 1/3-2/3?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

You either didn't read well or you didn't express the question right. If you randomly choose the root of a tree you will be expecting nodes to distribute half left half right (expected values of nodes to the right: $$$EV = \frac 1 n (0+1+2+...+(n-1)) $$$).

→ Reply
  • »
    »
    100 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Having a 50/50 distribution would be the best case (as balanced as it gets)? How could the best case be the average case?

    → Reply