ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

2ʬõ

2ʬõڡbinary search treeȤϡ2ʬڤˤ줾ǡǼƤơɤäƤ⼡ε§ΩĤΤǤ롣

  • ΥǡˡʱʬڤΤ٤ƤΥǡ
  • ʺʬڤΤ٤ƤΥǡˡΥǡ

2ʬõڤȥǡ¤

2ʬõڤǤϡΥǡӤϤơŪΥǡɤ餫ˤ뤫ȽꤷʬƤĤޤꡢ򤵤˹פơǤɲäȤˤ羮طθĤĺ2ĤʬꥹȤȤΤȤʤ櫓Ǥ롣ڤɽƤΤϤޤdzǰǤꡢԥ塼ǤϼºݤΥ꤬2ʬ櫓ǤϤʤץˤäŪ˼¸롣

2ʬõڤ¸뤿ˤϡθġǤ˥ǡ2ĤΥǥåղäФ褤

ħ

  • ꥹȤȯŸΤʤΤǡǤɲäϸΨŪ˹Ԥ롣
  • ǡθΨŪñʤȤäˤϡƬ饤ǥåνǤ򻲾ȤŪΥǡ򸫤ĤʤФʤʤФ2ʬõڤʤŪΥǡɤ߽ФƤǡ꾮ХꥹȤκ¦礭ХꥹȤα¦éФ褤ΤǡŪΥǡ᤯ȯǤ롣

2ʬõڤˤ׻

Ūʴ2ʬõڤη򤷤2ʬõڤǤϡǡθĿnĤΤȤ\log_2~nӤդã롣äơõפ׻̤ϺξO~(~\log_2~n)Ǥ롣

ޤǰξϡΤ褦2ʬõڤξǤ롣

ϥǡ礭ν˥ǡ򤷤ȯ뤬׻̤O~(~n~)Ǥ롣

ʸ

  • إץϤʤưΤ
  • إեȥȯѼԻкԥ塼­ܸ齬