Use the attached "words.txt" file to store the words along with their ranks in an AVL tree.

Then provide the user the option to search for any word. If the word exists the program displays the rank and the number of comparisons required to locate the words. If the word does no exist, it displays a message to indicate that, along with the number of comparisons.

Write a function to compute the average number of comparisons per search using all stored words. Compare the result with the theoretical average.

In C++

words.txt file:

1       the 2       be 3       and 4       a 5       of 6       to 7       in 8       i 9       you

10      it 11      have 12      to 13      that 14      for 15      do 16      he 17      with 18      on 19      this 20      n’t 21      we 22      that 23      not 24      but 25      they 26      say 27      at 28      what 29      his 30      from 31      go 32      or 33      by 34      get 35      she 36      my 37      can 38      as 39      know 40      if 41      me 42      your 43      all 44      who 45      about 46      their 47      will 48      so 49      would 50      make 51      just 52      up 53      think 54      time 55      there 56      see 57      her 58      as 59      out 60      one 61      come 62      people 63      take 64      year 65      him 66      them 67      some 68      want 69      how 70      when 71      which 72      now 73      like 74      other 75      could 76      our 77      into 78      here 79      then 80      than 81      look 82      way 83      more 84      these 85      no 86      thing 87      well 88      because 89      also 90      two 91      use 92      tell 93      good 94      first 95      man 96      day 97      find 98      give 99      more 100     new 101     one 102     us 103     any 104     those 105     very 106     her 107     need 108     back 109     there 110     should 111     even 112     only 113     many 114     really 115     work 116     life 117     why 118     right 119     down 120     on 121     try 122     let 123     something 124     too 125     call 126     woman 127     may 128     still 129     through 130     mean 131     after 132     never 133     no 134     world 135     in 136     feel 137     yeah 138     great 139     last 140     child 141     oh 142     over 143     ask 144     when 145     as 146     school 147     state 148     much 149     talk 150     out 151     keep 152     leave 153     put 154     like 155     help 156     big 157     where 158     same 159     all 160     own 161     while 162     start 163     three 164     high 165     every 166     another 167     become 168     most 169     between 170     happen 171     family 172     over 173     president 174     old 175     yes 176     house 177     show 178     again 179     student 180     so 181     seem 182     might 183     part 184     hear 185     its 186     place 187     problem 188     where 189     believe 190     country 191     always 192     week 193     point 194     hand 195     off 196     play 197     turn 198     few 199     group 200     such 201     against 202     run 203     guy 204     about 205     case 206     question 207     work 208     night 209     live 210     game 211     number 212     write 213     bring 214     without 215     money 216     lot 217     most 218     book 219     system 220     government 221     next 222     city 223     company 224     story 225     today 226     job 227     move 228     must 229     bad 230     friend 231     during 232     begin 233     love 234     each 235     hold 236     different 237     american 238     little 239     before 240     ever 241     word 242     fact 243     right 244     read 245     anything 246     nothing 247     sure 248     small 249     month 250     program 251     maybe 252     right 253     under 254     business 255     home 256     kind 257     stop 258     pay 259     study 260     since 261     issue 262     name 263     idea 264     room 265     percent 266     far 267     away 268     law 269     actually 270     large 271     though 272     provide 273     lose 274     power 275     kid 276     war 277     understand 278     head 279     mother 280     real 281     best 282     team 283     eye 284     long 285     long 286     side 287     water 288     young 289     wait 290     okay 291     both 292     yet 293     after 294     meet 295     service 296     area 297     important 298     person 299     hey 300     thank 301     much 302     someone 303     end 304     change 305     however 306     only 307     around 308     hour 309     everything 310     national 311     four 312     line 313     girl 314     around 315     watch 316     until 317     father 318     sit 319     create 320     information 321     car 322     learn 323     least 324     already 325     kill 326     minute 327     party 328     include 329     stand 330     together 331     back 332     follow 333     health 334     remember 335     often 336     reason 337     speak 338     ago 339     set 340     black 341     member 342     community 343     once 344     social 345     news 346     allow 347     win 348     body 349     lead 350     continue 351     whether 352     enough 353     spend 354     level 355     able 356     political 357     almost 358     boy 359     university 360     before 361     stay 362     add 363     later 364     change 365     five 366     probably 367     center 368     among 369     face 370     public 371     die 372     food 373     else 374     history 375     buy 376     result 377     morning 378     off 379     parent 380     office 381     course 382     send 383     research 384     walk 385     door 386     white 387     several 388     court 389     home 390     grow 391     better 392     open 393     moment 394     including 395     consider 396     both 397     such 398     little 399     within 400     second 401     late 402     street 403     free 404     better 405     everyone 406     policy 407     table 408     sorry 409     care 410     low 411     human 412     please 413     hope 414     TRUE 415     process 416     teacher 417     data 418     offer 419     death 420     whole 421     experience 422     plan 423     easy 424     education 425     build 426     expect 427     fall 428     himself 429     age 430     hard 431     sense 432     across 433     show 434     early 435     college 436     music 437     appear 438     mind 439     class 440     police 441     use 442     effect 443     season 444     tax 445     heart 446     son 447     art 448     possible 449     serve 450     break 451     although 452     end 453     market 454     even 455     air 456     force 457     require 458     foot 459     up 460     listen 461     agree 462     according 463     anyone 464     baby 465     wrong 466     love 467     cut 468     decide 469     republican 470     full 471     behind 472     pass 473     interest 474     sometimes 475     security 476     eat 477     report 478     control 479     rate 480     local 481     suggest 482     report 483     nation 484     sell 485     action 486     support 487     wife 488     decision 489     receive 490     value 491     base 492     pick 493     phone 494     thanks 495     event 496     drive 497     strong 498     reach 499     remain 500     explain 501     site 502     hit 503     pull 504     church 505     model 506     perhaps 507     relationship 508     six 509     fine 510     movie 511     field 512     raise 513     less 514     player 515     couple 516     million 517     themselves 518     record 519     especially 520     difference 521     light 522     development 523     federal 524     former 525     role 526     pretty 527     myself 528     view 529     price 530     effort 531     nice 532     quite 533     along 534     voice 535     finally 536     department 537     either 538     toward 539     leader 540     because 541     photo 542     wear 543     space 544     project 545     return 546     position 547     special 548     million 549     film 550     need 551     major 552     type 553     town 554     article 555     road 556     form 557     chance 558     drug 559     economic 560     situation 561     choose 562     practice 563     cause 564     happy 565     science 566     join 567     teach 568     early 569     develop 570     share 571     yourself 572     carry 573     clear 574     brother 575     matter 576     dead 577     image 578     star 579     cost 580     simply 581     post 582     society 583     picture 584     piece 585     paper 586     energy 587     personal 588     building 589     military 590     open 591     doctor 592     activity 593     exactly 594     american 595     media 596     miss 597     evidence 598     product 599     realize 600     save 601     arm 602     technology 603     catch 604     comment 605     look 606     term 607     color 608     cover 609     describe 610     guess 611     choice 612     source 613     mom 614     soon 615     director 616     international 617     rule 618     campaign 619     ground 620     election 621     face 622     uh 623     check 624     page 625     fight 626     itself 627     test 628     patient 629     produce 630     certain 631     whatever 632     half 633     video 634     support 635     throw 636     third 637     care 638     rest 639     recent 640     available 641     step 642     ready 643     opportunity 644     official 645     oil 646     call 647     organization 648     character 649     single 650     current 651     likely 652     county 653     future 654     dad 655     whose 656     less 657     shoot 658     industry 659     second 660     list 661     general 662     stuff 663     figure 664     attention 665     forget 666     risk 667     no 668     focus 669     short 670     fire 671     dog 672     red 673     hair 674     point 675     condition 676     wall 677     daughter 678     before 679     deal 680     author 681     truth 682     upon 683     husband 684     period 685     series 686     order 687     officer 688     close 689     land 690     note 691     computer 692     thought 693     economy 694     goal 695     bank 696     behavior 697     sound 698     deal 699     certainly 700     nearly 701     increase 702     act 703     north 704     well 705     blood 706     culture 707     medical 708     ok 709     everybody 710     top 711     difficult 712     close 713     language 714     window 715     response 716     population 717     lie 718     tree 719     park 720     worker 721     draw 722     plan 723     drop 724     push 725     earth 726     cause 727     per 728     private 729     tonight 730     race 731     than 732     letter 733     other 734     gun 735     simple 736     course 737     wonder 738     involve 739     hell 740     poor 741     each 742     answer 743     nature 744     administration 745     common 746     no 747     hard 748     message 749     song 750     enjoy 751     similar 752     congress 753     attack 754     past 755     hot 756     seek 757     amount 758     analysis 759     store 760     defense 761     bill 762     like 763     cell 764     away 765     performance 766     hospital 767     bed 768     board 769     protect 770     century 771     summer 772     material 773     individual 774     recently 775     example 776     represent 777     fill 778     state 779     place 780     animal 781     fail 782     factor 783     natural 784     sir 785     agency 786     usually 787     significant 788     help 789     ability 790     mile 791     statement 792     entire 793     democrat 794     floor 795     serious 796     career 797     dollar 798     vote 799     sex 800     compare 801     south 802     forward 803     subject 804     financial 805     identify 806     beautiful 807     decade 808     bit 809     reduce 810     sister 811     quality 812     quickly 813     act 814     press 815     worry 816     accept 817     enter 818     mention 819     sound 820     thus 821     plant 822     movement 823     scene 824     section 825     treatment 826     wish 827     benefit 828     interesting 829     west 830     candidate 831     approach 832     determine 833     resource 834     claim 835     answer 836     prove 837     sort 838     enough 839     size 840     somebody 841     knowledge 842     rather 843     hang 844     sport 845     tv 846     loss 847     argue 848     left 849     note 850     meeting 851     skill 852     card 853     feeling 854     despite 855     degree 856     crime 857     that 858     sign 859     occur 860     imagine 861     vote 862     near 863     king 864     box 865     present 866     figure 867     seven 868     foreign 869     laugh 870     disease 871     lady 872     beyond 873     discuss 874     finish 875     design 876     concern 877     ball 878     east 879     recognize 880     apply 881     prepare 882     network 883     huge 884     success 885     district 886     cup 887     name 888     physical 889     growth 890     rise 891     hi 892     standard 893     force 894     sign 895     fan 896     theory 897     staff 898     hurt 899     legal 900     september 901     set 902     outside 903     et 904     strategy 905     clearly 906     property 907     lay 908     final 909     authority 910     perfect 911     method 912     region 913     since 914     impact 915     indicate 916     safe 917     committee 918     supposed 919     dream 920     training 921     shit 922     central 923     option 924     eight 925     particularly 926     completely 927     opinion 928     main 929     ten 930     interview 931     exist 932     remove 933     dark 934     play 935     union 936     professor 937     pressure 938     purpose 939     stage 940     blue 941     herself 942     sun 943     pain 944     artist 945     employee 946     avoid 947     account 948     release 949     fund 950     environment 951     treat 952     specific 953     version 954     shot 955     hate 956     reality 957     visit 958     club 959     justice 960     river 961     brain 962     memory 963     rock 964     talk 965     camera 966     global 967     various 968     arrive 969     notice 970     bit 971     detail 972     challenge 973     argument 974     lot 975     nobody 976     weapon 977     best 978     station 979     island 980     absolutely 981     instead 982     discussion 983     instead 984     affect 985     design 986     little 987     anyway 988     respond 989     control 990     trouble 991     conversation 992     manage 993     close 994     date 995     public 996     army 997     top 998     post 999     charge

1000    seat

~end of text file