Algo Visualizedდაიწყე სწავლა

ხეები: ცნებები, თვისებები, შემოვლები

საქაღალდეები კომპიუტერში, კომპანიის სტრუქტურა, ნებისმიერი ვებგვერდის HTML: ყველა მათგანი ხეა. ერთხელ ისწავლე ტერმინები და წინ მყოფი ალგორითმების ნახევარი მარტივ ენაზე დაწერილივით წაგეკითხება.

★ ლექცია: trees_Intro1 · ზაზა გამეზარდაშვილი▶ ვიდეო დამწყები⏱ 20 წთ

←ეყრდნობა

0რეკურსია და გამოძახებათა სტეკიხის ყოველი შემოვლა ერთი და იგივე ფუნქციაა, რეკურსიულად გამოძახებული ყოველ შვილზე.4ქვესიმრავლეებისა და გადანაცვლებების გენერაციასრული გადარჩევის გადაწყვეტილებების ხე უკვე ხე იყო; ახლა მის ნაწილებს სახელს ვარქმევთ.3ბმული სიებიხის წვერო იგივე ბმული სიის კვანძია, ერთის ნაცვლად რამდენიმე მიმთითებლით.

გზას უხსნის→

5ძებნის ორობითი ხეძებნის ორობითი ხის INORDER შემოვლა გასაღებებს დალაგებულად გვაძლევს.5ორობითი გროვა და პრიორიტეტული რიგიგროვა სრული ორობითი ხეა, სადაც ყოველი მშობელი თავის შვილებზე პატარაა.5ტრაი და ავტოშევსებატრაი არის სათავიანი ხე, რომლის ყოველ წიბოზე ერთი ასოა.6გრაფის წარმოდგენახე ბმული გრაფია ციკლების გარეშე; გრაფი ამ შეზღუდვას უბრალოდ ხსნის.6სიგანეში ძებნა (BFS)ხეზე BFS დონეების მიხედვით შემოვლაა; გრაფზე მას მონახულებულთა მასივი ემატება.6ხის დიამეტრი და ცენტრიდიამეტრი და ცენტრი ხის ძირითადი ცნებებით იგება: სიღრმით, სიმაღლითა და გზით.8გაერთიანება-ძებნა (DSU)DSU-ს ყოველი ჯგუფი ხეა, find კი მის სათავემდე ადის.+სეგმენტების ხესეგმენტების ხე ორობითი ხეა, რომლის ყოველი წვერო ერთ შუალედს ფარავს.
1ისწავლე2უყურე3ითამაშე4შეამოწმე5ივარჯიშე
01

ისწავლე

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

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

ხე არის მონაცემთა სტრუქტურა, რომელიც აღწერს იერარქიული ხასიათის მონაცემებს ან პროცესებს: საქაღალდეები საქაღალდეებში, ხელმძღვანელები თანამშრომლებზე მაღლა, თამაშის სვლები, რომლებსაც ახალი სვლები მოსდევს.

ლექციაში ხე რეკურსიულადაა განსაზღვრული. ხე T ან ცარიელია, ან შეიცავს:

  • განსაკუთრებულ წვეროს r, ხის სათავეს (root),
  • ნულ ან მეტ ქვეხეს T1, T2, …, Tk, რომელთაგან თითოეული თავადაც ხეა.

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

T1T2Tk…rსათავე rქვეხეებიქვეხეც ხეა: თავისი სათავე და ქვეხეებიან ცარიელი ხე: T = ∅
ყოველი ქვეხე თავადაც ხეა: განსაზღვრება საკუთარ თავს იყენებს.

02ხე და გრაფი

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

თუ G = (V, E) არაორიენტირებული გრაფია, შემდეგი თვისებები ტოლფასია, ამიტომ ერთის დამტკიცება დანარჩენებსაც გვაძლევს:

  • G ხეა;
  • ნებისმიერ ორ წვეროს აერთებს ერთადერთი მარტივი გზა;
  • G ბმულია, მაგრამ ნებისმიერი წიბოს გამოკლებით კარგავს ბმულობას;
  • G ბმულია და E = V − 1;
  • G არ შეიცავს ციკლებს, ანუ აციკლურია, და E = V − 1 (სლაიდზე მხოლოდ „არ შეიცავს ციკლებს“ წერია, მაგრამ რამდენიმე ცალკეული ხისგან შემდგარი ტყეც აციკლურია);
  • G აციკლურია, მაგრამ ნებისმიერი წიბოს დამატებით მასში ჩნდება ციკლი.

ლექციის ხეს 10 წვერო და 9 წიბო აქვს. დაამატე კიდევ ერთი, მაგალითად პუნქტირით ნაჩვენები 2–8, და ციკლი მაშინვე გაჩნდება.

+1 წიბო12345678910ხე = გრაფი✓ ბმულია✓ ციკლი არ აქვსE = V − 19 = 10 − 1+1 წიბო→ ჩნდება ციკლი
ლექციის ხე: 10 წვერო, 9 წიბო. პუნქტირი წიბო 2–8 წითელ ციკლს შეკრავდა.

03სათავე და ტერმინოლოგია

ხშირად ერთი წვერო იერარქიულად სხვებზე მაღლა დგას: ეს სათავეა (root, ძირი). ამ როლს ნებისმიერი წვერო შეიძლება ასრულებდეს: ერთი და იგივე ხე შეგვიძლია „ჩამოვკიდოთ“ ნებისმიერ წვეროზე. ნახაზზე ლექციის ხე მე-5 წვეროზეა ჩამოკიდებული. მაშინ:

  • სათავის გარდა ყველა წვეროს ჰყავს მხოლოდ ერთი მშობელი, შვილი კი შეიძლება ჰყავდეს 0, 1 ან რამდენიმე (9 არის 3-ის, 10-ის, 6-ის და 7-ის მშობელი);
  • ფოთოლს შვილები არ ჰყავს; ერთი მშობლის შვილები დედმამიშვილები არიან;
  • გზა წიბოების მიმდევრობაა, მისი სიგრძე კი წიბოების რაოდენობა (8-დან 2-მდე ის 5-ია);
  • წვეროს სიღრმე სათავიდან ამ წვერომდე გზის სიგრძეა;
  • წვეროს სიმაღლე მისგან ფოთლამდე უშორესი გზის სიგრძეა, ამიტომ ყოველი ფოთლის სიმაღლე 0-ია;
  • ხის სიმაღლე = სათავის სიმაღლე = ყველაზე ღრმა ფოთლის სიღრმე, აქ 4;
  • თუ n1 დევს სათავიდან n2-მდე გზაზე, მაშინ n1 არის n2-ის წინაპარი, n2 კი n1-ის შთამომავალი.
სიღრმე 0სიღრმე 1სიღრმე 2სიღრმე 3სიღრმე 412345678910სათავემშობელიშვილები = დედმამიშვილებიხის სიმაღლე = 4= ფოთოლი: 8, 1, 2, 10, 6, 7
იგივე ხე, ჩამოკიდებული მე-5 წვეროზე.

04ორობითი ხეები და ხის წარმოდგენა

ორობით ხეში ყოველ წვეროს აქვს 0, 1 ან 2 შვილი, left(x) და right(x), და ჩვეულებრივ იცის თავისი მშობელიც, parent(x). C++-ში ეს სამმიმთითებლიანი სტრუქტურაა: struct node { int data; node *parent, *left, *right; };. ლექციაში ცხრილური ვარიანტიც არის: მასივები parent[], left[], right[], სადაც 0 ნიშნავს „წვერო არ არის“.

სრულ ორობით ხეში ყოველ წვეროს 0 ან 2 შვილი ჰყავს და ყველა ფოთოლს ერთნაირი სიღრმე აქვს. დათვალე დონეები: 1, 2, 4, 8… ე.ი. d სიმაღლის სრული ორობითი ხე 2^(d+1) − 1 წვეროს შეიცავს. პირიქით თუ წავიკითხავთ: N წვერო ეტევა O(log N) სიმაღლეში. სწორედ ეს ფაქტი ხდის სწრაფს დაბალანსებულ ხეებსა და გროვებს.

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

123456789101112131415დონე 01დონე 12დონე 24დონე 38სულ152⁴ − 1 = 15N წვერო → სიმაღლე O(log N)
ლექციის სრული ორობითი ხე: დონეებზე 1, 2, 4 და 8 წვეროა.

05ორობითი ხის შემოვლის ალგორითმები

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

  • PREORDER: მშობელი, მარცხენა შვილი, მარჯვენა შვილი → 4, 7, 6, 1, 2, 8, 3, 9, 5
  • INORDER: მარცხენა შვილი, მშობელი, მარჯვენა შვილი → 6, 7, 2, 1, 4, 3, 9, 8, 5
  • POSTORDER: მარცხენა შვილი, მარჯვენა შვილი, მშობელი → 6, 2, 1, 7, 9, 3, 5, 8, 4

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

ყოველ რიგს თავისი საქმე აქვს. PREORDER ხეს აკოპირებს ან საქაღალდეებივით ბეჭდავს. INORDER ძებნის ორობით ხეს დალაგებულად ჩამოთვლის (შემდეგი გაკვეთილი). POSTORDER შვილებს მშობელზე ადრე ამუშავებს: მეხსიერების გასათავისუფლებლად ან არითმეტიკული გამოსახულების ხის გამოსათვლელად, მაგალითად 16 + (7 + 5·4) / 9 − 2·3, სადაც ოპერაციები შიდა წვეროებშია, რიცხვები კი ფოთლებში.

123456789PREORDER476128395INORDER672143985POSTORDER621793584
ლექციის შემოვლის სლაიდის ხე. სათავე 4 პირველია, შუაშია ან ბოლოა.
ლექციის C++ კოდიC++

მე-9 სლაიდი: მეხსიერებაში ყოველი წვერო ინახავს მონაცემს და სამ მიმთითებელს: მშობელზე, მარცხენა შვილზე და მარჯვენა შვილზე.

struct node {
    int data;
    struct node *parent;
    struct node *leftchild;
    struct node *rightchild;
};

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

ნებისმიერი შემოვლაO(n)
წიბოები ხეშიV − 1
სრული ორობითი ხის სიმაღლეO(log N)
d სიმაღლის სრული ხის წვეროები2^(d+1) − 1

დაიმახსოვრე

  1. ხე ბმული გრაფია ციკლების გარეშე, ამიტომ მას ზუსტად V − 1 წიბო აქვს და ნებისმიერ ორ წვეროს შორის ერთადერთი გზა.
  2. სიღრმე სათავიდან ქვემოთ ითვლება, სიმაღლე წვეროდან მის უღრმეს ფოთლამდე; ხის სიმაღლე მისი სათავის სიმაღლეა.
  3. PREORDER, INORDER და POSTORDER ერთი რეკურსიული ფუნქციაა; იცვლება მხოლოდ ის მომენტი, როცა მშობელს ვსტუმრობთ.
02

უყურე

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

▶

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

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

▶ ვიდეოს გვერდი▣ პრეზენტაციად გახსნა
ლექციებიდან ასევე▶ ხეები, ნაწილი 2
03

ითამაშე

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

👀 რას უყურო: უყურე გამომავალ ზოლს: ერთი და იგივე ცხრა წვერო სამი სხვადასხვა რიგით გამოდის. დააკვირდი, სად ხვდება ყოველ ჯერზე სათავე 4.

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

ორობითი ხე: PREORDER

123456789

გამომავალი მიმდევრობა

(ჯერ ცარიელია)
PREORDER (მშობელი → მარცხენა → მარჯვენა): მშობელი შვილებზე ადრე ცხადდება. გამოიყენება ხის კოპირებისა და პრეფიქსული ჩანაწერისთვის.

ფსევდოკოდი

 1 preorder(v):  visit v; preorder(v.left); preorder(v.right) 2 inorder(v):   inorder(v.left); visit v; inorder(v.right) 3 postorder(v): postorder(v.left); postorder(v.right); visit v 4 // each node is visited exactly once → O(n)
1 / 1
04

შეამოწმე

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

№1

ბმულ არაორიენტირებულ გრაფს 12 წვერო და 12 წიბო აქვს. რაში შეგვიძლია ვიყოთ დარწმუნებული?

№2

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

№3

სრული ორობითი ხის სიმაღლე 4-ია. რამდენი წვერო აქვს მას?

05

ივარჯიშე

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

LeetCodeBinary Tree Inorder Traversal დამწყები↗LeetCodeMaximum Depth of Binary Tree დამწყები↗CSESSubordinates საშუალო↗LeetCodeConstruct Binary Tree from Preorder and Inorder Traversal საშუალო↗