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

არის აქ 16? სია გასაღებებს სათითაოდ ამოწმებს; ძებნის ორობითი ხე რამდენიმე შედარებით გპასუხობს: მილიონ გასაღებზე დაახლოებით 20-ით, თუ ხე დაბალანსებულია.

★ ლექცია: tree_BST · ზაზა გამეზარდაშვილი▶ ვიდეო საშუალო⏱ 20 წთ

←ეყრდნობა

2ორობითი ძებნა და ძებნა პასუხზეძებნის ორობით ხეში ძებნა არის ორობითი ძებნა, ხის ფორმაში გაყინული.5ხეები: ცნებები, თვისებები, შემოვლებიძებნის ორობითი ხის INORDER შემოვლა გასაღებებს დალაგებულად გვაძლევს.

გზას უხსნის→

5დაბალანსებული ხეები და set / mapძებნის ხე O(n)-მდე ეცემა, როცა ჯაჭვად იზრდება; ბალანსი h = O(log n)-ს ინარჩუნებს.

1ისწავლე 2უყურე 3ითამაშე 4შეამოწმე 5ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01ძებნის ორობითი ხის განსაზღვრება

ძებნის ორობითი ხე (BST) ისეთი ორობითი ხეა, რომლის ყოველი წვეროსთვის:

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

გასაღებებს შორის მხოლოდ შედარება უნდა იყოს შესაძლებელი: რიცხვები, სტრიქონები, თარიღები. ლექციის წვეროს აქვს მიმთითებლები left, right და parent და გასაღები value; ამოცანის მიხედვით parent შეიძლება არ დაგვჭირდეს, ან დაგვჭირდეს სხვა ველებიც.

შეხედე 17-ს: 16 მის მარცხნივ კიდია, 19 მარჯვნივ, და 17-ის მთელი ქვეხე მაინც „< 20“ არეშია. ამ წესის წყალობით ამ გაკვეთილის ყოველი ოპერაცია სათავიდან ქვემოთ ერთ გზას გადის და O(h) ღირს, სადაც h ხის სიმაღლეა.

ლექციის 12-გასაღებიანი ხე. წესი ყოველ წვეროზე სრულდება და არა მხოლოდ სათავეზე.

02ელემენტის ძებნა და ჩასმა

ძებნა სათავიდან იწყება. თუ საძებნი გასაღები მიმდინარე წვეროზე მეტია, გადავდივართ მარჯვნივ, თუ ნაკლებია, მარცხნივ; ვჩერდებით, როცა ვიპოვით ან ხიდან „ჩამოვვარდებით“ (NULL მიმთითებელი ნიშნავს „აქ არ არის“). ვეძებთ 16-ს: 16 < 20, მარცხნივ; 16 > 14, მარჯვნივ; 16 < 17, მარცხნივ; ნაპოვნია. ოთხი შედარება, თითო დონეზე ერთი.

ჩასმა იგივე სვლაა. ჩავსვათ 35: 35 > 20, მარჯვნივ; 35 > 32, მარჯვნივ; 35 < 38, მარცხნივ, 38-ს კი მარცხენა შვილი არ ჰყავს, ამიტომ 35 ხდება 38.left. ახალი ელემენტი ჩასმის მომენტში ყოველთვის ფოთოლია და ზუსტად იქ დგება, სადაც მას შემდგომი ძებნა მოძებნის.

ლექციაში ორივე რეკურსიულადაა დაწერილი. insert-ის ლამაზი ხრიკი ისაა, რომ ის ქვეხის სათავეს აბრუნებს, ამიტომ გამოძახება node->left = insert(node->left, key) ხეს თავად აკავშირებს, ცარიელი ადგილი კი უბრალოდ newNode(key) ხდება. უკვე არსებულ გასაღებს მეორედ არ ვსვამთ.

ლექციის search(16) და insert(35): თითო დონეზე ერთი შედარება.

03INORDER, მინიმუმი, მაქსიმუმი, წინა და მომდევნო

გაუშვი INORDER ძებნის ხეზე და გასაღებები დალაგებული გამოვა: 9, 11, 14, 16, 17, 19, 20, 27, 30, 32, 38, 47. ის ჯერ მარცხენა ქვეხეს შემოივლის (ყველა ნაკლები), მერე წვეროს, მერე მარჯვენა ქვეხეს (ყველა მეტი). ჩასვი გასაღებები ნებისმიერი რიგით, ამობეჭდე INORDER-ით და ისინი დალაგებული გაქვს.

დალაგებული ხედი კიდევ ოთხ ოპერაციას ხსნის:

მინიმუმი: სათავიდან ვიაროთ მარცხნივ, ვიდრე მარცხენა შვილი აღარ იქნება (9);
მაქსიმუმი: ვიაროთ მარჯვნივ (47);
გასაღების წინა ელემენტი მისი მარცხენა ქვეხის მაქსიმუმია (20-ისთვის 19);
მომდევნო ელემენტი მარჯვენა ქვეხის მინიმუმია (20-ისთვის 27).

ე.ი. ქვეხეზე findMin() და findMax() ორივე მეზობელს გვაძლევს. თუ ეს ქვეხე ცარიელია, მეზობელი რომელიმე წინაპარია და ამისთვის გვჭირდება parent მიმთითებელი. ოთხივე ოპერაცია ერთ გზას გადის: O(h).

ყოველი წვერო ვერტიკალურად ჩამოუშვი: გასაღებები დალაგებული გამოვა.

04ელემენტის წაშლა: სამი შემთხვევა

წაშლამ ძებნის ხის თვისება უნდა შეინარჩუნოს. ლექცია სამ შემთხვევას განიხილავს:

ა) ფოთოლი: საკმარისია მშობელში გავანულოთ შესაბამისი შვილის მიმთითებელი. 19-ის წაშლა ნიშნავს 17.right = NULL.
ბ) ერთი შვილი: შვილი იკავებს წასაშლელი ელემენტის ადგილს მის მშობელთან. 27-ის წაშლისას მისი შვილი 30 ხდება 32-ის მარცხენა შვილი; მთელი ქვეხე ერთი დონით ადის და დალაგებული რჩება.
გ) ორი შვილი: შვილის ანაცვლებით წესი შეიძლება დაირღვეს, ამიტომ გასაღებს ვანაცვლებთ მისი მომდევნო (ერთი ნაბიჯი მარჯვნივ, მერე ბოლომდე მარცხნივ) ან წინა ელემენტით. 14-ის მომდევნო ელემენტი 16-ია (მარჯვნივ 17-ზე, მერე მარცხნივ 16-ზე), ამიტომ 16 იკავებს 14-ის ადგილს, მისი ძველი ფოთოლი კი ა) შემთხვევის მსგავსად იშლება. იგივე შედეგს მოგვცემდა წინა ელემენტი 11. ზოგადად მომდევნო ელემენტს მარცხენა შვილი არასდროს ჰყავს, ამიტომ მისი ძველი ადგილიდან წაშლა ყოველთვის ა) ან ბ) შემთხვევაა.

ლექციის deleteNode სამივე შემთხვევას ერთ რეკურსიულ ფუნქციაში აკეთებს: ვპოულობთ გასაღებს; თუ მარცხენა შვილი არ ჰყავს, ვაბრუნებთ მარჯვენას (ეს ფოთლებსაც მოიცავს); თუ მარჯვენა არ ჰყავს, მარცხენას; სხვა შემთხვევაში ვაკოპირებთ მომდევნოს გასაღებს და მას მარჯვენა ქვეხიდან ვშლით.

ლექციის სამი მაგალითი: ვშლით 19-ს, 27-ს და 14-ს.

05ღირებულება O(h) და რიგობრივი სტატისტიკა

აქამდე ყოველი ოპერაცია სათავიდან ერთ გზას გადის, ამიტომ O(h) ღირს. რამდენად დიდია h? შემთხვევითი რიგით შემოსული გასაღებებისთვის ის log n-ის მცირე ჯერადი რჩება. თუ გასაღებები დალაგებული მოდის, ყოველი ახალი გასაღები წინას მარჯვნივ ებმება და ხე ჯაჭვად გადაგვარდება, h = n: სიაზე უკეთესი აღარაფერია. ამას დაბალანსებული ხეები ასწორებს (შემდეგი გაკვეთილი).

ლექცია ბონუსით მთავრდება: რიგობრივი სტატისტიკა. თითოეულ კვანძში შევინახოთ მისი ქვეხის ელემენტების რაოდენობა (size) და განვაახლოთ ის ყოველი ჩასმისა და წაშლისას. k-ური უმცირესი გასაღების საპოვნელად ავიღოთ r = left.size + 1, მიმდინარე წვეროს რიგითი ნომერი:

k == r → პასუხი ეს წვეროა;
k < r → ვეძებთ k-ურ ელემენტს მარცხენა ქვეხეში;
k > r → ვეძებთ (k − r)-ურ ელემენტს მარჯვენა ქვეხეში.

მე-8 უმცირესი: 20-ში r = 7 < 8, მარჯვნივ, k = 1; 32-ში r = 3, მარცხნივ; 27-ში r = 1 = k. პასუხია 27, O(h) დროში.

ყოველი წვეროს ქვეშ ქვეხის ზომაა; სვლა 20 → 32 → 27 პოულობს მე-8 უმცირეს გასაღებს.

ლექციის C++ კოდიC++

მე-9 სლაიდის სრული პროგრამა, რომელსაც მე-5 სლაიდის ძებნის ფუნქცია დავამატეთ: insert და search ხეში ერთნაირად ეშვება, გასაღებს ადარებს და მარცხნივ ან მარჯვნივ უხვევს, inorder კი გასაღებებს დალაგებულად ბეჭდავს.

#include <bits/stdc++.h>
using namespace std;
struct node { int key; struct node *left, *right; };
struct node* newNode(int item){
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
void inorder(struct node* root){
    if (root != NULL) {
        inorder(root->left);
        cout<<root->key<<" ";
        inorder(root->right);
    }
}
struct node* insert(struct node* node, int key){
    if (node == NULL) return newNode(key);
    if (key < node->key) node->left = insert(node->left, key);
    else if (key > node->key) node->right = insert(node->right, key);
    return node;
}
//ძებნა BST-ში მოცემული ხისა და მოცემული რიცხვისათვის
struct node* search(struct node* root, int key) {
    // საბაზო შემთხვევა: სათავე null-ია ან საძებნი რიცხვი სათავეშია
    if (root == NULL || root->key == key) return root;
    // საძებნი რიცხვი სათავის მნიშვნელობაზე მეტია
    if (root->key < key) return search(root->right, key);
    // საძებნი რიცხვი სათავის მნიშვნელობაზე ნაკლებია
    return search(root->left, key);
}
int main() {
    struct node* root = NULL;
    root = insert(root, 100); insert(root, 50); insert(root, 150);
    insert(root, 25); insert(root, 75); insert(root, 125); insert(root, 175);
    inorder(root);
}

ფასი ერთი შეხედვით

ძებნა / ჩასმა / წაშლაO(h)

მინ. / მაქს. / წინა / მომდევნოO(h)

დალაგებული გამოტანა (INORDER)O(n)

სიმაღლე h: დაბალანსებული … ჯაჭვიlog n … n

დაიმახსოვრე

ყოველ წვეროზე მარცხნივ < წვერო < მარჯვნივ, ამიტომ ძებნა, ჩასმა, მინიმუმი და მაქსიმუმი ერთ გზას გადის: O(h).
INORDER ძებნის ხეს დალაგებულად ჩამოთვლის; წინა და მომდევნო ელემენტები ამ სიაში გასაღების მეზობლები არიან.
წაშლას სამი შემთხვევა აქვს (ფოთოლი, ერთი შვილი, ორი შვილი), ორი შვილის შემთხვევაში კი მომდევნო ელემენტს ვიყენებთ.

უყურე

ლექცია ვიდეოს სახით.

▶

ლექცია, ანიმაციით

ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.

▶ ვიდეოს გვერდი ▣ პრეზენტაციად გახსნა

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: მიჰყევი შედარებების გზას: ყოველი ნაბიჯი მთელ ქვეხეს გამორიცხავს. შემდეგ შეიყვანე შენი გასაღებები და წაშალე სათავე, რომ ნახო, როგორ ადის მომდევნო ელემენტი.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

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

შედარებების გზანაპოვნი / ჩასმულიმიმდინარე

ძებნა 16: ვიწყებთ სათავიდან. ყოველი შედარება მთელ ქვეხეს გამორიცხავს. ეს ორობითი ძებნაა, მიმთითებლებში „გაყინული“.

ფსევდოკოდი

 1 search(x): start at root 2   if x == node.key: found 3   if x <  node.key: go left 4   if x >  node.key: go right 5 insert(x): search for x … 6   … attach x at the first null link 7 findMin(): keep going left 8 findMax(): keep going right 9 delete(x), x is a leaf:10   null the pointer in x’s parent11 delete(x), x has one child:12   the child takes x’s place under x’s parent13 delete(x), x has two children:14   successor s = min of right subtree; s replaces x

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

ცარიელ ძებნის ხეში ჩავსვით 50, 30, 70, 20, 40, შემდეგ 35. სად აღმოჩნდება 35?

№2

ორშვილიან წვეროს ვშლით და მის ადგილს მომდევნო ელემენტით ვავსებთ. რატომ არის მომდევნოს ძველი ადგილიდან ამოღება მარტივი?

№3

ჩვეულებრივ ძებნის ხეში გასაღებები 1, 2, 3, …, 1000 ამ რიგით ჩავსვით. რა ღირს ახლა ძებნა?

ივარჯიშე

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

LeetCodeSearch in a Binary Search Tree დამწყები↗LeetCodeInsert into a Binary Search Tree საშუალო↗LeetCodeValidate Binary Search Tree საშუალო↗LeetCodeKth Smallest Element in a BST საშუალო↗LeetCodeDelete Node in a BST საშუალო↗