[Powered by Google Translate] چگونه به تمام اعضای خانواده خود را در نمایندگی شما در یک کامپیوتر؟ ما به سادگی می تواند با استفاده از یک لیست، اما سلسله مراتب روشن در اینجا وجود دارد. 

بیایید می گویند که ما در حال شروع با مادر بزرگ خود، آلیس. او دارای 2 پسر، باب و پدر بزرگ خود، چارلی. چارلی دارای 3 فرزند، عموی خود، دیو، عمه، خاله، حوا، و پدر خود، فرد است. شما تنها فرزند فرد. 

چرا باید اعضای خانواده خود را سازماندهی در این راه بهتر از نمایندگی لیست ساده؟ یکی از دلایل این است که این ساختار سلسله مراتبی، درخت نامیده می شود، شامل اطلاعات بیش از یک لیست ساده است. ما می دانیم که روابط خانوادگی بین همه تنها با بررسی درخت. همچنین، می توانید سرعت آن را تا زمان نگاه کردن فوق العاده، اگر داده ها درخت طبقه بندی شده اند. 

ما می توانیم که در اینجا استفاده نمی کنند، اما ما به عنوان مثال از این به زودی را ببینید. هر فرد با یک گره در درخت نشان داده شده است. گره می تواند گره فرزند داشته باشند و همچنین به عنوان یک گره پدر و مادر. اینها شرایط فنی، حتی زمانی که با استفاده از درختان برای چیزهایی علاوه بر خانواده است. گره آلیس دارای 2 فرزند و نه پدر و مادر، در حالی که گره چارلی دارای 3 فرزند و 1 پدر و مادر است. 

یک گره برگ است که هیچ بچه ها ندارد بر روی لبه در خارج از درخت است. بالاترین گره از درخت، گره ریشه، بدون پدر و مادر. 

یک درخت دودویی، یک نوع خاص از درخت است، که در آن هر گره، حداکثر 2 فرزند است. در اینجا این است که ساختار یک گره از یک درخت دودویی در C هر گره دارای برخی از داده های مرتبط با آن و 2 اشاره گر به گره های دیگر است. 

در درخت خانواده ما، داده های مربوط به نام هر فرد بود. در اینجا آن را از نوع int است، هر چند که می تواند هر چیزی باشد. همانطور که معلوم است، یک درخت دودویی خواهد بود نمایندگی خوب برای یک خانواده، از آنجایی که افراد اغلب بیش از 2 فرزند دارند. 

درخت جستجوی دودویی خاص، نوع مرتب از درخت دودویی است که به ما اجازه می دهد تا در ارزش به سرعت. شما ممکن است متوجه که هر گره در زیر ریشه یک درخت ریشه درخت دیگری به نام "زیر درخت. در اینجا، ریشه درخت 6 است، و کودک آن، 2، ریشه درخت است. 

در درخت جستجوی دودویی تمام ارزش یک گره راست زیر درخت بیشتر از مقدار گره است. در اینجا: 6. خوب، ارزش ها در زیر درخت چپ گره کمتر از مقدار گره است. اگر ما نیاز داریم که مسئولیت رسیدگی به ارزش های تکراری، ما می توانید تغییر دهید یا از آن به نابرابری شل، به این معنی که ارزش های یکسان سقوط هم می تواند در سمت چپ یا راست، تا زمانی که ما در مورد آن سازگار در سراسر. این درخت یک درخت جستجوی دودویی چرا که آن را به پیروی از این قوانین است. 

این است که چگونه آن را نگاه اگر ما تمام گره به ساختمانها C تبدیل. توجه داشته باشید که اگر کودک از دست رفته است، اشاره گر تهی است. چگونه می توانم چک کنید و ببینید اگر 7 در درخت است؟ ما در ریشه شروع می شود. هفت بزرگتر از 6 است، به طوری که اگر آن را در درخت، باید آن را به سمت راست می شود. پس از آن، آن است که کمتر از 8 است، بنابراین باید آن را به سمت چپ. در اینجا، ما را در بر داشت 7. در حال حاضر، ما را به مدت 5 را بررسی کنید. پنج کمتر از 6، پس از آن باید به سمت چپ باشد. پنج بزرگتر از 2 است، پس از آن باید به سمت راست، و آن را بزرگتر از 4 است، بنابراین باید آن را دوباره درست شد. با این حال، هیچ بچه ای در اینجا وجود دارد. اشاره گر تهی است. این به این معنی است که 5 است نه در درخت است. 

ما می توانیم از درخت جستجوی دودویی با کد زیر را جستجو کنید: در هر گره، چک کنید و ببینید اگر ما پیدا کرده اند ارزش ما به دنبال. اگر ما آن را پیدا نمی کند، تعیین می کنیم در صورتی که باید آن را در سمت چپ و یا راست را بررسی کنید که زیر درخت است. این حلقه ادامه خواهد داد درخت تا زمانی که هیچ گره کودک در دو سمت چپ یا راست وجود دارد. 

به یاد داشته باشید که 5 در درخت نبود. چگونه می توانم آن را به ما وارد؟ این فرایند به نظر می رسد مشابه را برای جستجو می باشد. ما تکرار پایین درخت شروع از 6 از چپ تا 2، حق تا 4، و دوباره درست شد، ولی 4 هیچ کودکی در این سمت است. این خواهد بود که موقعیت های جدید برای 5 و آن را با هیچ بچه شروع می شود. 

عملیات بر روی درخت جستجوی دودویی با چه سرعتی؟ به یاد داشته باشید که Bigohnotation به دنبال ارائه یک حد بالا است. در بدترین حالت، درخت ما به سادگی می تواند یک لیست پیوندی به این معنی که درج، حذف و جستجو می تواند زمان متناسب با تعداد گره در درخت است. O (n) است. 

به عنوان مثال، در زیر درخت جستجوی دودویی معتبر است. با این حال، اگر ما سعی می کنید برای پیدا کردن 9، ما باید به گذشتن از هر گره است. این بهتر از یک لیست پیوندی است. در حالت ایده آل، ما هر گره را می خواهم درخت جستجو دودویی ما به 2 فرزند است. به این ترتیب، درج، حذف و جستجو می کنند، در بدترین حالت O (log n است) مدت زمان. درخت از قبل می تواند متعادل تر، مثل این. در حال حاضر، به دنبال هر مقدار طول می کشد، در اکثر، 3 مرحله است. این درخت متوازن، به این معنا که حداقل عمق نسبت به تعداد گره ها است. 

در حال جستجو برای یک مقدار در یک درخت دودویی جستجو متوازن شبیه به جستجوی باینری در یک آرایه مرتب شده است. در واقع، اگر ما نیازی به وارد کردن و یا حذف اقلام، دقیقا به همان شیوه رفتار کنند. با این حال، یک ساختار درختی بهتر است برای درج حمل و نقل و حذف 

نام من Bannus ون der Kloot است. این CS50 است.