درخت باینری کامل در مقابل درخت باینری کامل
درخت باینری درختی است که در آن هر گره یک یا دو فرزند دارد. در یک درخت باینری، یک گره نمی تواند بیش از دو فرزند داشته باشد. در یک درخت دوتایی، کودکان به عنوان فرزندان "چپ" و "راست" نامگذاری می شوند. گره های فرزند حاوی ارجاع به والد خود هستند. درخت دودویی کامل، درختی باینری است که در آن هر سطح از درخت دودویی به جز آخرین سطح به طور کامل پر شده است. در سطح پر نشده، گره ها از سمت چپ ترین موقعیت شروع می شوند. درخت دودویی کامل درختی است که در آن هر گره درخت به جز برگ های درخت دو فرزند دارد.
درخت باینری کامل چیست؟
درخت باینری کامل یک درخت دودویی است که در آن هر گره در درخت دقیقاً صفر یا دو فرزند دارد. به عبارت دیگر، هر گره درخت به جز برگ ها دقیقاً دو فرزند دارد. شکل 1 زیر یک درخت باینری کامل را نشان می دهد. در یک درخت دودویی کامل، تعداد گره‌ها (n)، تعداد لاوها (l) و تعداد گره‌های داخلی (i) به شکل خاصی مرتبط هستند، به طوری که اگر یکی از آنها را می‌شناسید، می‌توانید دو مورد دیگر را تعیین کنید. مقادیر به شرح زیر است:
1. اگر یک درخت باینری کامل دارای گره های داخلی i باشد:
– تعداد برگ l=i+1
– تعداد کل گره ها n=2i+1
2. اگر یک درخت باینری کامل n گره داشته باشد:
– تعداد گره‌های داخلی i=(n-1)/2
– تعداد برگ l=(n+1)/2
3. اگر یک درخت باینری کامل دارای l برگ باشد:
– تعداد کل گره ها n=2l-1
– تعداد گره های داخلی i=l-1
درخت باینری کامل چیست؟
همانطور که در شکل 2 نشان داده شده است، یک درخت باینری کامل، درختی باینری است که در آن تمام سطوح درخت به جز آخرین سطح، به طور کامل پر شده است. همچنین، در آخرین سطح، گره ها باید از سمت چپ ترین موقعیت متصل شوند. یک درخت باینری کامل با ارتفاع h شرایط زیر را برآورده می کند:
– از گره ریشه، سطح بالاتر از آخرین سطح یک درخت باینری کامل با ارتفاع h-1 را نشان می دهد.
– یک یا چند گره در آخرین سطح ممکن است 0 یا 1 فرزند داشته باشد
- اگر a، b دو گره در سطح بالاتر از آخرین سطح باشند، a فرزندان بیشتری از b دارد اگر و فقط اگر a در سمت چپ b قرار گرفته باشد.
تفاوت بین درخت باینری کامل و درخت باینری کامل چیست؟
درختهای باینری کامل و درختان باینری کامل تفاوت آشکاری دارند. در حالی که یک درخت باینری کامل یک درخت دودویی است که در آن هر گره دارای صفر یا دو فرزند است، یک درخت باینری کامل یک درخت دودویی است که در آن هر سطح از درخت باینری به‌جز آخرین سطح به طور کامل پر شده است. برخی از ساختارهای داده خاص مانند heap ها باید درخت های باینری کامل باشند در حالی که نیازی به درخت های باینری کامل ندارند. در یک درخت باینری کامل، اگر تعداد کل گره ها یا تعداد لاوها یا تعداد گره های داخلی را بدانید، می توانید دو تای دیگر را به راحتی پیدا کنید. اما یک درخت باینری کامل دارای خاصیت خاصی در رابطه با این سه ویژگی نیست.
