TAILIEUCHUNG - Thuật toán Algorithms (Phần 42)

Tham khảo tài liệu 'thuật toán algorithms (phần 42)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | CONNECTIVITY 403 function fastfind x y integer union boolean boolean var i j t integer begin j x while dad i 0 do i dad i j y while dad j 0 do j dad j while dad x 0 do begin t x x dad x dad t i end while dad y do begin end if union and then if dad j dad i then begin dad J dad j dad i 1 dad i j end else begin dad i dad I dad j 1 dad j .i end fastfind i j end The dad array is assumed to be initialized to 0. We ll assume in later chapters that this is done in a separate procedure findinit. For our sample set of edges this program builds the following trees from the first ten edges The trees containing DEF and JKLM are flatter than before because of path compression. Now FE doesn t contribute anything as before then AF combines the first two trees with A at the root since its tree is larger the GC doesn t contribute anything then GH puts the HI tree below A then JG puts the JKLM tree below A resulting in the following tree The following table gives the contents of the dad array as this forest is constructed 404 CHAPTER 30 ABCDEFGH I JKLM A G A B A C 3AAOOOAOOOOO0 LM 3AA00OA00001L JM 3AA0 0 O A 0 O L 0 2L JL 3AAOOOAOOL02L J K E D F D HI 3AAE 2EA 1HLL3 L F E A F 6AAEAEA1HLL3L G E 6AAEAEA1HLL3L G C 6AAEAEA1HLL3L G H JG 12AAEAEAAHL LA L LG 12AAEAEAAHLLAL For clarity in this table each positive entry i is replaced by the ith letter of the alphabet the name of the father and each negative entry is complemented to give a positive integer the weight of the tree . Several other techniques have been developed to avoid degenerate structures. For example path compression has the disadvantage that it requires another pass up through the tree. Another technique called halving is to make each node point to its granddad on the way up the tree. Still another technique splitting is like halving but is applied only to every other node on the search path. Either of these can be used in combination with weight balancing or with height balancing which is similar but uses tree height instead

• Toán học
• Thuật toán sắp xếp
• tìm kiếm
• xử lý chuỗi
• đồ thị
• một số chủ đề nâng cao
• Mathematical algorithms
• Sorting
• Searching
• String processing
• Bài giảng Các thuật toán sắp xếp
• Các thuật toán sắp xếp
• Tìm hiểu các thuật toán sắp xếp
• Cách tiếp cận sắp xếp đơn giản
• Tiếp cận sắp xếp độ phức tạp O
• Một số cách tiếp cận sắp xếp
• Bài giảng Thuật toán sắp xếp
• Tiếp cận sắp xếp đơn giản
• Sắp xếp theo cơ số
• Sắp xếp hòa nhập file lớn
• Cấu trúc dữ liệu và giải thuật
• Bài toán sắp xếp
• Các phương pháp sắp xếp
• Các bước của thuật toán sắp xếp
• Sắp xếp vun đống
• Các tính chất của Heap
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Sắp xếp chọn
• Sắp xếp nhanh
• Sắp xếp trộn
• Bài giảng Sắp xếp
• Sắp xếp nổi bọt
• Sắp xếp hòa nhập
• Thuật toán merge
• Thuật toán sắp xếp hòa nhập
• thuật toán sắp xếp đơn giản
• Sắp xếp lựa chọn
• Phân tích sắp xếp lựa chọn
• sort
• Cấu trúc dữ liệu
• Sắp xếp chèn
• Thuật toán sắp xếp chọn
• Phương pháp phần tử hữu hạn
• Áp dụng các thuật toán sắp xếp
• Giải thuật sắp xếp
• Các thuật toán sắp xếp cơ bản
• Đề tài Công nghệ thông tin
• Selection Sort
• Insertion Sort
• Quick sort
• Bucket sort
• Sắp xếp tại chỗ
• Chiến lược sắp xếp
• Tổng quan về thời gian thực hiện
• Số các nghịch thế
• Các kỹ thuật sắp xếp
• phép hoán vị
• Bài giảng Cấu trúc dữ liệu thuật toán
• Cấu trúc dữ liệu thuật toán
• Ba thuật toán sắp xếp cơ bản
• Bài toán giải thuật
• Tính chất của Heap
• Cấu trúc dữ liệu và thuật toán
• Khoa học máy tính
• Sắp xếp
• Bài giảng Cấu trúc dữ liệu
• Khung làm việc Java Fork Join
• Khung Java Fork Join
• Thuật toán sắp xếp song song
• Thuật toán work stealing
• Sắp xếp trộn song song
• Sắp xếp nhanh song song
• Cơ sở dữ liệu
• Phương pháp sắp xếp
• Phương pháp sắp xếp thông dụng
• Cấu trúc giải thuật
• Thành phần dữ liệu
• Bài giảng Hệ thống thông tin
• Hệ thống thông tin
• Sắp xếp phần tử mảng theo thứ tự
• Bài giảng Giải thuật
• Ba phương pháp sắp xếp
• Sắp xếp kiểu hòa nhập
• Tìm hiểu về thuật toán RadixSort
• Trình bày thuật toán sắp xếp RadixSort
• Tìm hiểu về RadixSort
• Tìm hiểu thuật toán sắp xếp
• Thuật toán RadixSort
• Đánh giá thuật toán
• Thiết kế thuật toán
• Bài giảng đánh giá thuật toán
• Bài giảng thiết kế thuật toán
• Chặn dưới sắp xếp
• Sắp xếp trong thời gian tuyến tính
• Lập trình C
• Bài giảng Lập trình căn bản
• Bài toán tìm kiếm
• Thuật toán tìm kiếm tuần tự
• Thuật toán tìm kiếm nhị phân
• Thuật toán sắp xếp nổi bọt