რა არის ბინარული ხე?

ორძირიანი ხე — ეს მონაცემთა სტრუქტურა, რომელიც წარმოადგენს ხის სახის სტრუქტურას, სადაც თითოეულ ნიშანს აქვს მაქსიმუმ ორი შვილი: მარცხენა და მარჯვენა.

ძირითადი თვისებები:

• კენჭი (Root): ხის ზედა ნიშანი.
• ნიშანი (Node): ელემენტი ხის, რომელიც შეიცავს მონაცემებს და კავშირებს მის შთამომავლებთან.
• შვილი (Child): ნიშანი, რომელიც მდებარეობს პირდაპირ სხვა ნიშანის (მშობლის) ქვეშ.
• მშობელი (Parent): ნიშანი, რომელიც აქვს პირდაპირ ერთი ან მეტი შვილი.
• საფეხური (Leaf): ნიშანი, რომელსაც არ აქვს შთამომავლები.
• მუხლი (Branch): გზა მშობიდან საფეხურამდე.
• ქვათამძიმარი (Subtree): ხე, რომელიც შედგება ერთ ნიშანიდან და ყველა მის შთამომავლიდან.

სხვადასხვა ტიპის ბინარული ხეები:

• სრული ბინარული ხე (Full Binary Tree): თითოეულ ნიშანს აქვს ან 0 ან 2 შვილი.
• სრულყოფილი ბინარული ხე (Perfect Binary Tree): ყველა დონე, გარდა ბოლო, სრულად არის სავსე, და ბოლო დონეზე ყველა ნიშანი განთავსებულია რაც შეიძლება მარცხნივ.
• ბალანსირებული ბინარული ხე (Balanced Binary Tree): ნებისმიერი ნიშნის მარცხენა და მარჯვენა ქვათამძიმრის სიმაღლე განსხვავდება არა უმეტეს 1-ის. მაგალითი: AVL ხე, წითელი-შავი ხე.
• დეგენერირებული (გაფართოებული) ბინარული ხე (Degenerate Binary Tree): თითოეულ ნიშანს აქვს მაქსიმუმ ერთი შვილი. არსებითად, ეს არის დაკავშირებული სია.

მრავალ ალგორითმში და მონაცემთა სტრუქტურებში გამოიყენება, მაგალითად, ბინარული ძიების ხეები, კოშკები, სინტაქსის ხეები.