کارگزاران فارکس

درخت باینری

سیامک تیموری جمعه 08 فروردین 1399

ساختار داده های درخت باینری

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

ریشه درخت باینری عنصری است که درست در بالای ساختار داده و سلسله مراتب قرار دارد. تمام عناصر سمت چپ ریشه را شاخه چپ و تمام عناصر سمت راست درخت را شاخه راست می نامند. هر عنصر در یک درخت را می توان به عنوان یک گره در نظر گرفت. گره اساسا دارای سه عنصر است.

  • داده ها
  • اشاره به سمت چپ کودک
  • به کودک مناسب اشاره کنید.

در صورتی که گره فرزندی نداشته باشد، اشاره گر به null اشاره می کند.

پیاده سازی درختان در جاوا

کلاس زیر یک گره از یک درخت را پیاده سازی می کند که دارای دو فرزند است. کلید مقدار گره است. برای این مثال، ما گره هایی را به ریشه اختصاص نداده ایم.

//برنامه زیر یک درخت ساده را تنظیم می کند که ساختار زیر را دارد:

ویژگی های درخت دودویی

  • یک درخت باینری می تواند حداکثر 2 داشته باشد i گره های سطح i. ریشه یک درخت سطح 0 در نظر گرفته می شود. بنابراین 2^0 = 1 یعنی در سطح ریشه درخت فقط می تواند یک گره داشته باشد. در سطح یک: 2^1 = 2 گره و غیره.
  • یک درخت باینری با ارتفاع 'h' حداکثر 2 خواهد داشت h – 1 تعداد گره ها اگر ارتفاع درختی 4 باشد، حداکثر می تواند 2^(4-1) = 8 گره داشته باشد.
  • فرمول بدست آوردن حداقل ارتفاع یا سطوح یک درخت باینری از گره های N به شرح زیر است: Log2 (N + 1).
  • اگر یک درخت دودویی دارای L تعداد برگ باشد (برگ‌ها بچه ندارند)، حداقل تعداد لایه‌هایی که درخت خواهد داشت با فرمول Log به دست می‌آید.2L + 1.
  • اگر در یک درخت دودویی، هر گره 0 یا 2 فرزند داشته باشد، تعداد کل برگ ها (گره هایی با 0 فرزند) همیشه یک بیشتر از گره هایی خواهد بود که دو فرزند دارند.

تراورس

اجازه دهید درخت زیر را همانطور که قبلا ارائه شد در نظر بگیریم تا در مورد پیمایش صحبت کنیم.

درخت باینری

در قسمت قبلی ما به بررسی درخت و اصطلاحات فنی آن پرداختیم و اینکه چگونه یک درخت را پیمایش کنیم. در این قسمت مطلب قبل را با درخت‌های دودویی ادامه می‌دهیم.

همه‌ی موضوعات و اصطلاحاتی را که در مورد درخت‌ها به کار بردیم، در مورد این درخت هم صدق می‌کند؛ تفاوت درخت دودویی با یک درخت معمولی این است که درجه هر گره نهایتا دو خواهد بود یا به عبارتی ضریب انشعاب این درخت 2 است. از آن جایی که هر گره در نهایت دو فرزند دارد، می‌توانیم فرزندانش را به صورت فرزند چپ Left Child و فرزند راست Right Child صدا بزنیم. به گره‌هایی که فرزند ریشه هستند اینگونه می‌گوییم که گره فرزند چپ با همه فرزندانش می‌شوند زیر درخت چپ Left SubTree و گره سمت راست ریشه با تمام فرزندانش زیر درخت راست Right SubTree صدا زده می‌شوند.

نحوه پیمایش درخت دودویی

این درخت پیمایش‌های گوناگونی دارد ولی سه تای آن‌ها اصلی‌تر و مهمتر هستند:

In-order یا LVR (چپ، ریشه، راست): در این حالت ابتدا گره‌های سمت چپ ملاقات (چاپ) می‌شوند و سپس ریشه و بعد گره‌های سمت راست.

Pre-Order یا VLR (ریشه، چپ، راست) : در این حالت ابتدا گره‌های ریشه ملاقات می‌شوند. بعد گره‌های سمت چپ و بعد گره‌های سمت راست.

Post_Order یا LRV (چپ، راست، ریشه ): در این حالت ابتدا گره‌های سمت چپ، بعد راست و نهایتا ریشه، ملاقات می‌شوند.

حتما متوجه شده‌اید که منظور از v در اینجا ریشه است و با تغییر و جابجایی مکان این سه حرف RLV میتوانید به ترکیب‌های مختلفی از پیمایش دست پیدا کنید.

اجازه دهید روی شکل بالا پیمایش LVR را انجام دهیم: همانطور که گفتیم باید اول گره‌های سمت چپ را خواند، پس از 17 به سمت 9 حرکت می‌کنیم و می‌بینیم که 9، خود والد است. پس به سمت 6 حرکت می‌کنیم و می‌بینیم که فرزند چپی ندارد؛ پس خود 6 را ملاقات می‌کنیم، سپس فرزند راست را هم بررسی می‌کنیم که فرزند راستی ندارد پس کار ما اینجا تمام است و به سمت بالا حرکت می‌کنیم. 9 را ملاقات می‌کنیم و بعد عدد 5 را و به 17 بر می‌گردیم. 17 را ملاقات کرده و سپس به سمت 15 می‌رویم و الی آخر .

نحوه پیاده سازی درخت دودویی:

تفاوتی که این کد با کد قبلی که برای یک درخت معمولی داشتیم، در این است که قبلا لیستی از فرزندان را داشتیم که با خاصیت Children شناخته می‌شدند، ولی در اینجا در نهایت دو فرزند چپ و راست برای هر گره وجود دارند. برای جست و جو هم از الگوریتم In_Order استفاده کردیم که از همان الگوریتم DFS آمده‌است. در آنجا هم ابتدا گره‌های سمت چپ به صورت بازگشتی صدا زده می‌شدند. بعد خود گره و سپس گره‌های سمت راست به صورت بازگشتی صدا زده می‌شدند.

برای باقی روش‌های پیمایش تنها نیاز است که این سه خط را جابجا کنید:

درخت دودویی مرتب شده Ordered Binary Search Tree

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

همان طور که می‌دانید برای مقایسه اعداد ما از علامتهای <>= استفاده می‌کنیم و اعداد صحیح بهترین اعداد برای مقایسه هستند. در درخت‌های جست و جوی دو دویی یک خصوصیت اضافه به اسم کلید هویت یکتا Unique identification Key داریم که یک کلید قابل مقایسه است. در تصویر زیر ما دو گره با مقدارهای متفاوتی داریم که با مقایسه‌ی آنان می‌توانیم کوچک و بزرگ بودن یک گره را محاسبه کنیم. ولی به این نکته دقت داشته باشید که این اعداد داخل دایره‌ها، دیگر برای ما حکم مقدار درخت باینری ندارند و کلید‌های یکتا و شاخص هر گره محسوب می‌شوند.

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

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

برای مثال فکر کنید می‌خواهید عدد 13 را در درخت بالا پیدا کنید. ابتدا گره والد 19 را مقایسه کرده و از آنجا که 19 بزرگتر از 13 است می‌دانیم که 13 را در زیر درخت راست پیدا نمی‌کنیم. پس زیر درخت چپ را مقایسه می‌کنیم (بنابراین به راحتی یک زیر درخت از مقایسه و عمل جست و جو کنار گذاشته شد). سپس گره 11 را مقایسه می‌کنیم و از آنجا که 11 کوچکتر از 13 هست، زیر درخت سمت راست را ادامه می‌دهیم و چون 16 بزرگتر درخت باینری از 13 هست، زیر درخت سمت چپ را در ادامه مقایسه می‌کنیم که به 13 رسیدیم.

مقایسه گره‌هایی که برای جست و جو انجام دادیم:

درخت هر چه بزرگتر باشد این روش کارآیی خود را بیشتر نشان می‌دهد.

در قسمت بعدی به پیاده سازی کد این درخت به همراه متدهای افزودن و جست و جو و حذف می‌پردازیم.

درخت باینری

این سوال در تست سراسری 81 ارشد مطرح شده بود و جواب max با پاسخ شما مطابقت داشت اما جواب minنه.برای minگفته بود حداقل در درختان مورب به چپ یا مورب به راست به وجود می آید که می شود 2h+1. به نظر شما این پاسخ صحیح است؟ در کتاب دیگری پاسخ شما مطرح شده بود.

جواب شما درسته،من به صورت سوال دقت نکرده بودم! درصورتی که درخت دودویی کامل نباشد ، مثل درخت دودیی محض شما یک ریشه دارید و نود های دارای دو فرزند هستند و سطح آخر یک برگ داشته باشد فرمول به شکل 2h+1 می باشد.

سلام.
ولی تو درخت مورب حداقل گره ها میشه h+1


که تعداد گره ها 3 و ارتفاع 2 هست (البته اگه ارتفاع ریشه رو صفر بگیریم)

دوست من این تعریفی که شما گفتی تعریف درخت دودویی محض هست!


برای تعریف درخت دودویی میتونی به صفحه 248 کتاب ساختمان داده هوروویتس ترجمه قلزم مراجعه کنی.

اگر در صورت سوال فقط گفته درخت دودویی مسلماً حداقل گره هاش h+1 خواهد بود.
چرا؟ معمولا در تست ها منظور از درخت دودویی درخت دودویی محض است

چرا؟ معمولا در تست ها منظور از درخت دودویی درخت دودویی محض است


ولی فکر نمیکنم اینجوری باشه، البته از روی گزینه ها هم میشه فهمید منظور چی بوده مثلاً اگر در این سوال در گزینه ها h+1 وجود نداشته باشه و 2h+1 وجود داشته باشه میشه فهمید که منظور درخت دودویی محض هست.

در صورت سوال فقط ذکر شده بود یک درخت دودویی درختی است که هر گره آن صفر یا 2 فرزند دارد.و در گزینه ها هم h+1را داده بود و هم 2h+1را.

خوب چون صورت سوال خودش گفته منظرش چه نوع درختی هست 2h+1 صحیح است.
ولی طبق تعریف معمول درخت دودویی، درخت مورب هم دودویی هست.


این همون بهترین و بدترین حالت در جست و جوی دودیی محسوب می شه؟

این همون بهترین و بدترین حالت در جست و جوی دودیی محسوب می شه؟

بدترین حالت جستجوی دودویی ( O( log n درخت باینری و بهترین حالت ( O( 1 هست. بدترین حالت زمانیه که تمام عمق درخت رو برای پیدا کردن عنصر مورد نظر پیمایش کنیم، که log2 درخت باینری n می‌شه. و بهترین حالت اینه که عنصر ریشه درخت همون عنصر مورد نظر باشه که با یه مقایسه به دست می‌یاد و ( O( 1 می‌شه.

البته من در اینجا آرایه مرتب برای استفاده از جستجوی دودویی رو با یه درخت جستجوی دودویی معادل کردم. ابهام پیش نیاد.

پیمایش درخت جستجوی دودویی

تذکر: در این مقاله منظور از درخت دودویی، درخت جستجوی دودویی است!
سه روش استاندارد برای پیمایش درختهای دودویی وجود داره: پیمایش پیشوندی (preorder)، پیمایش میانوندی (inorder) و پیمایش پسوندی (postorder).
تعاریف بازگشتی این پیمایش ها به ترتیب زیره:

پیمایش پیشوندی:
1- پردازش ریشه
۲ - پیمایش زیردرخت چپ ریشه به روش پیشوندی
3- پیمایش زیردرخت راست ریشه به روش پیشوندی

پیمایش میانوندی:
1- پیمایش زیردرخت چپ ریشه به روش میانوندی
2- پردازش ریشه
3- پیمایش زیردرخت راست ریشه به روش میانوندی

پیمایش پسوندی:
1- پیمایش زیردرخت چپ ریشه به روش پسوندی
2- پیمایش زیردرخت راست ریشه به روش پسوندی
3- پردازش ریشه

فرض کنیم برای ذخیره سازی اطلاعاتی از نوع عدد صحیح از درخت دودویی استفاده بشه. از ساختار زیر برای تعریف گره درخت بهره می بریم:

struct node
<
int info ;
node *parent ;
node *Lchild ;
node *Rchild ;
> ;

برای چاپ محتویات گرههای درخت با پیمایشهای سه گانه می شه توابع بازگشتی به صورت زیر پیاده سازی کرد:

void preorder ( node *root )
<
if ( !root )
return;
cout info preorder ( root->Lchild ) ;
preorder ( root->Rchild ) ;
>

void inorder ( node *root )
<
if ( !root )
return;
inorder ( root->Lchild ) ;
cout info inorder ( root->Rchild ) ;
>

void postorder ( node *root )
<
if ( !root )
return;
postorder ( root->Lchild ) ;
postorder ( root->Rchild ) ;
cout info >

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

این مطلب با زحمات کاربرای این سایت جمع آوری شده است
اخلاق حکم می کند در صورت برداشت از سایت منبع را ذکر کنید!

درخت مرکل (درخت درهم سازی)

درخت مرکل (درخت درهم سازی)

سیامک تیموری

سیامک تیموری جمعه 08 فروردین 1399

درخت مرکل (Merkle tree) مانند ساختار درخت، باینری یا دو به دو است که تمام تراکنش‌ها را در یک بلاک درهم سازی می‌کند. این درختان در بسیاری از ارزهای دیجیتال مورد استفاده قرار می‌گیرند تا داده‌های زیادی را در خود ذخیره و آن‌ها را کارآمدتر کنند. این کار باعث می‌شود تا سطح دادهٔ مورد نیاز برای اثبات وجود چیزی کاهش یابد.

همه تراکنش‌هایی که به ماینرها سپرده می‌شوند در یک ردیف قرار می‌گیرند تا به نوبت پردازش شوند. در تراکنش‌های کوین بیس یا تولید نسل (تراکنشی که توسط یک ماینر منجر به تولید بیت کوین می‌شود؛ ماینر این کار را با حل کردن معادلات بلاک درخت باینری قبلی انجام می‌دهد) اگر تعداد تراکنش‌ها فرد باشند، آنگاه آخرین تراکنش با خود جفت می‌شود تا تراکنش را زوج کند. از این رو تعداد سطوح درخت بستگی به تعداد تراکنش‌ها دارد.

اولین تراکنش از طریق الگوریتم SHA-256 درهم سازی می‌شود، سپس دومین تراکنش و بعد از آن سومی و این روند تا تکمیل تمام تراکنش‌ها ادامه می‌یابد. گام بعدی مشخص کردن مقدار هش هر تراکنش است که به ترتیب از اولین تراکنش شروع می‌شود و تا آخرین تراکنش برای به دست آوردن آخرین هش ادامه می‌یابد. آخرین هش در بالاترین نقطهٔ درخت قرار دارد.

​​​​​​​

بیشتر بخوانید: پلتفرم چنجلی (Changelly)

به خاطر داشته باشید الگوریتم هشینگ SHA-256 دسته‌های ۳۲ بیتی تولید می‌کند، از این رو هرگاه یک دستهٔ ۳۲ بیتی را به درخت باینری یک دستهٔ ۳۲ بیتی دیگر متصل کنیم، یک دستهٔ ۶۴ بیتی ایجاد می‌شود. بعد از این که دستهٔ ۳۲ بیتی توسط الگوریتم SHA-256 تولید شد،‌ تراکنش‌ها تا زمانی که همهٔ آن‌ها به هم متصل شوند، توسط الگوریتم درهم سازی می‌شوند.

به بیانی دیگر، این فرایند تا زمانی تکرار می‌شود که آخرین مقدار هش به دست آید. به این مقدار ریشهٔ مرکل (Merkle Root) می‌گویند. برای هر ماینر، ریشهٔ مرکل متفاوت است زیرا درخت باینری مسیری که هر ماینر برای بدست آوردن مقدار هش استفاده می‌کند با سایرین فرق دارد و به همین خاطر هش‌ها متفاوت هستند.

این بدان معناست که ماینرها از سخت افزارهای گوناگون با قدرت محاسباتی متفاوت استفاده می‌کنند و به همین خاطر روش اثبات کار آن‌ها با یکدیگر فرق دارد.

مقالات مرتبط

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

برو به دکمه بالا