Jump to content
ToQcHista

ძებნის ორობითი ხეები

Recommended Posts

ძებნის ორობითი ხეები წარმოადგენენ მონაცემთა სტრუქტურას, რომლის საშუალებითაც ხის სიმაღლის პროპორციულ O(h) დროში  სრულდება შემდეგი ოპერაციები:

 

ძებნა;

მინიმუმის პოვნა;
მაქსიმუმის პოვნა;
წინა ელემენტის პოვნა;
მომდევნო ელემენტის პოვნა;
ელემენტის ჩასმა;
ელემენტის წაშლა.
 
              ძებნის ორობითი ხეების წარმოდგენა
წარმოადგენს მიმთითებლებით დაკავშირებულ ხეს.
root(T) კვანძი არის T ხის სათავე.
ყოველი კვანძი შედგება ველებისაგან
      გასაღები
      მარცხენა შვილი: მარცხენა ქვეხის სათავე.
      მარჯვენა შვილი: მარჯვენა ქვეხის სათავე.
      p - მშობლის მიმთითებელი. p[root[T]] = NIL
 
 
ძებნის ორობითი ხის თვისება
 
ძებნის ორობითი ხის გასაღებები უნდა აკმაყოფილებდნენ შემდეგ პირობას:
" y-სათვის x-ის მარცხენა ქვეხიდანkey[y] £ key[x].
" y-სათვის x-ის მარჯვენა ქვეხიდან key[y] ³ key[x].
 
Min & Max-ის პოვნა
wძებნის ორობითი ხის თვისება განაპირობებს:
» მინიმუმი არის სათავიდან ყველაზე მარცხენა კვანძში.
» მაქსიმუმი არის სათავიდან ყველაზე მარჯვენა კვანძში.
 
47e282b06ed7.jpg
 
წინა და მომდევნო ელემენტების პოვნა
x ელემენტის მომდევნო ელემენტი (Successor) არის ისეთი y, რომლის მნიშვნელობაც უმცირესია x-ზე მეტ ელემენტებს შორის.
უდიდესი ელემენტის მომდევნო არის NIL.
ძებნის დროს განიხილება ორი შემთხვევა:
თუ x ელემენტს აქვს არაცარიელი მარჯვენა ქვეხე, მაშინ მისი მომდევნო ელემენტია ამ ქვეხის მინიმუმი.
თუ x ელემენტის მარჯვენა ქვეხე ცარიელია: თუკი მარჯვენა ქვეხე ცარიელია, მაშინ ჩვენ ვმოძრაობთ x-დან ზემოთ, ვიდრე არ ვიპოვით წვეროს, რომელიც თავისი მშობლის მარცხენა შვილია. სწორედ ეს მშობელი (თუკი ის არსებობს) წარმოადგენს საძებნ ელემენტს.
 
ელემენტის წაშლა ძებნის ორობით ხეში
ელემენტის წაშლისას შესაძლებელია სამი შემთხვევა:

     ა) z-ს არ გააჩნია შვილები, ამ დროს z-ის წასაშლელად საკმარისია მისი მშობლის შესაბამის მინდორში მოვათავსოთ nil;

     ბ) z-ს გააჩნია ერთი შვილი, ამ შემთხვევაში z  “ამოიშლება” მისი მშობლისა და შვილის პირდაპირი შეერთებით;

     გ) z-ს გააჩნია ორი შვილი – აქ წვეროს წაშლამდე საჭიროა გარკვეული მოსამზადებელი სამუშაოების ჩატარება: უნდა მოვძებნოთ გასაღების სიდიდის მიხედვით მომდევნო y ელემენტი. მას არ ეყოლება მარცხენა შვილი (ძებნის ორობით ხეში მტკიცდება შემდეგი თვისება: თუ ელემენტს გააჩნია ორი შვილი, მაშინ გასაღების სიდიდის მიხედვით მომდევნო ელემენტს არ გააჩნია მარცხენა შვილი, ხოლო გასაღების სიდიდის მიხედვით წინას – მარჯვენა შვილი). ამის შემდეგ y წვეროს გასაღები და დამატებითი მონაცემები z წვეროს შესაბამის მინდვრებში, ხოლო თავად y წვერო წავშალოთ ზემოთ ნახსენები (ბ) ხერხით.

 

 

  • Upvote 2

Share this post


Link to post
Share on other sites

მაგალითად მე რასაც ვიყენებ C++-ში <Algorithm> ბიბლიოთეკაშია Heap, რომელიც ორობითი ხეა და სურვილის შემთხვევაში შეგიძლია დაასორტირო, ისიც ლოგარითმულ დროში ამატებს და აგდებს ელემენტს მასივიდან...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×