Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Công Nghệ Thông Tin
Cơ sở dữ liệu
Lecture Data Structures: Lesson 36
tailieunhanh - Lecture Data Structures: Lesson 36
Lecture Data Structures: Lesson 36 provide students with knowledge about union by size; maintain sizes (number of nodes) of all trees, and during union; make smaller tree the subtree of the larger one; implementation: for each root node i, instead of setting parent[i] to -1, set it to -k if tree rooted at i has k nodes; . | Running Time Analysis Union is clearly a constant time operation. Running time of find i is proportional to the height of the tree containing node i. This can be proportional to n in the worst case but not always Goal Modify union to ensure that heights stay small Lecture Data Structures Dr. Sohail Aslam Union by Size Maintain sizes number of nodes of all trees and during union. Make smaller tree the subtree of the larger one. Implementation for each root node i instead of setting parent i to -1 set it to -k if tree rooted at i has k nodes. This also called union-by-weight. Union by Size union i j root1 find i root2 find j if root1 root2 if parent root1 Union by Size 1 2 3 4 5 6 7 8 -1 -1 -1 -1 -1 -1 -1 -1 1 2 3 4 5 6 7 8 Eight elements initially in different sets. Union by Size 1 2 3 4 5 7 8 6 -1 -1 -1 -2 -1 4 -1 -1 1 2 3 4 5 6 7 8 Union 4 6 Union by Size 1 2 4 5 7 8 3 6 -1 -2 2 -2 -1 4 -1 -1 1 2 3 4 5 6 7 8 Union 2 3 Union by Size 2 4 5 7 8 3 1 6 4 -2 2 -3 -1 4 -1 -1 1 2 3 4 5 6 7 8 Union 1 4 Union by Size 4 5 7 8 2 1 6 3 4 4 2 -5 -1 4 -1 -1 1 2 3 4 5 6 7 8 Union 2 4 Union by Size 4 7 8 2 1 6 5 3 4 4 2 -6 4 4 -1 -1 1 2 3 4 5 6 7 8 Union 5 4 Analysis of Union by Size If unions are done by weight size the depth of any element is never greater than log2n. Analysis of Union by Size Intuitive Proof Initially every element is at depth zero. When its depth increases as a result of a union operation it s in the smaller tree it is placed in a tree that becomes at least twice as large as before union of two equal size trees . How often can each union be done - log 2n times because after at most log2n unions the tree will contain all n elements. Union by Height Alternative to union-by-size strategy maintain heights During union make a tree with smaller height a subtree of the other. Details are left as an exercise. Sprucing up Find So far we have tried to optimize union. Can we optimize find Yes using path compression or compaction . Sprucing up Find During find i as
Ngọc Khang
21
24
ppt
Báo lỗi
Trùng lắp nội dung
Văn hóa đồi trụy
Phản động
Bản quyền
File lỗi
Khác
Upload
Tải xuống
đang nạp các trang xem trước
Không thể tạo bản xem trước, hãy bấm tải xuống
Tải xuống
TÀI LIỆU LIÊN QUAN
Lecture ECE 250 - Algorithms and data structures: Data structures and algorithms
35
99
1
Lecture Data Structures: Lesson 1
50
27
1
Lecture ECE 250 - Algorithms and data structures: Containers, relations, and abstract data types
63
80
0
Lecture ECE 250 - Algorithms and data structures: The tree data structure
42
71
0
Lecture Data structures and algorithms: Chapter 1 - Introduction
41
1
1
Lecture Data Structures and Algorithms - Chapter 0: Course Outline
12
29
1
Lecture Data Structures and Algorithms - Chapter 1: Introduction
41
26
1
Lecture Data Structures and Algorithms - Chapter 0: Course Outline (Dr. Nguyen Ho Man Rang)
12
51
3
Lecture Data Structures and Algorithms - Chapter 1: Introduction (Dr. Nguyen Ho Man Rang)
45
54
3
Lecture Data Structures: Lesson 5
24
19
1
TÀI LIỆU XEM NHIỀU
Một Case Về Hematology (1)
8
461872
55
Giới thiệu :Lập trình mã nguồn mở
14
22690
61
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
10902
530
Câu hỏi và đáp án bài tập tình huống Quản trị học
14
10072
446
Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”
3
9536
104
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8295
1125
Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức
16
8244
423
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7866
2220
Đề tài: Dự án kinh doanh thời trang quần áo nữ
17
6697
253
Vật lý hạt cơ bản (1)
29
5779
85
TỪ KHÓA LIÊN QUAN
Cơ sở dữ liệu
Lecture Data Structures
Bài giảng Cấu trúc dữ liệu
Data structures
Union by size
Analysis of union by size
Union by size strategy
Lecture ECE 250
Lecture Algorithms and data structures
Algorithm analysis
Graph algorithms
Memory allocation
Programming assignments
Data structures organize data
Resource constraints
Abstract data types
Tree data structure
Lecture Data structures and algorithms
Data structures and algorithms
Cấu trúc dữ liệu và giải thuật
Abstract data type
Bài giảng Cấu trúc dữ liệu và thuật toán
Fundamental data structures
Computational complexity
Complexity of algorithms
Data structure
Pointers to structures
Pointers to classes
Josephus problem
List data structures
Doubly linked list
Circularly linked list
Code for simulation
Priority queue
Tree data structures
Computer science
Design of data structures
Algorithms in Java
AVL trees
Binary search trees
Red black trees
Splay trees
Dynamic programming
TÀI LIỆU MỚI ĐĂNG
Mass Transfer in Multiphase Systems and its Applications Part 19
40
256
1
29-04-2024
extremetech Hacking BlackBerry phần 9
31
252
0
29-04-2024
MÔN HỌC VẬT LIỆU VÀ CÔNG NGHỆ KIM LOẠI - PHẦN I: KIM LOẠI HỌC
32
177
2
29-04-2024
B2B Content Marketing: 2012 Benchmarks, Budgets & Trends
17
139
0
29-04-2024
HƯỚNG DẪN SỬ DỤNG PHẦN MỀM CAITA part 9
18
130
0
29-04-2024
Giáo trình tổng quan khoa học thông tin và thư viện part 7
22
144
2
29-04-2024
Khóa luận tốt nghiệp: Giải pháp nâng cao chất lượng phương thức thanh toán tín dụng chứng từ phục vụ xuất nhập khẩu tại ngân hàng Thương mại Việt Nam - Trần Thị Tân
12
118
0
29-04-2024
GIÁO TRÌNH VI XỬ LÝ 1 - CHƯƠNG 5. LẬP TRÌNH CHO VI ĐIỀU KHIỂN 80C51
23
107
1
29-04-2024
báo cáo hóa học:" Journal of the International AIDS Society: an important step forward"
2
86
0
29-04-2024
Bài giảng hệ điều hành : HỆ ĐIỀU HÀNH NÂNG CAO part 4
6
114
0
29-04-2024
TÀI LIỆU HOT
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7866
2220
Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152
5765
1383
Ebook Chào con ba mẹ đã sẵn sàng
112
3770
1232
Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1
62
5328
1136
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8295
1125
Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu
561
3504
643
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
10902
530
Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122
3690
525
Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm
274
4062
516
Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe
35
4133
480
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.