Mục lục bài họcĐang ở d05-b2
Binary Trees, Traversals and Choosing a Structure
Terminology. A binary tree consists of nodes, each with at most two children. The root is the single node with no parent; a leaf has no children; the depth of a node is the number of edges from the root; the height of the tree is the depth of its deepest node. Any node together with everything below it forms a subtree, which is why almost every tree algorithm is naturally recursive: a tree is a node plus two smaller trees.
The binary search tree property. In a binary search tree, everything in a node's left subtree is smaller than the node and everything in its right subtree is larger. Inserting a value starts at the root and moves left or right at each node until an empty position is reached. Searching uses the same comparison at each step, and because each comparison eliminates an entire subtree, a balanced tree of n nodes is searched in about log base 2 of n steps.
The crucial caveat. That efficiency depends entirely on balance. If values are inserted in sorted order, every new value goes to the right and the tree degenerates into a straight chain — functionally a linked list — so searching takes n steps. This is why real systems use self-balancing trees, and why an answer claiming that binary search trees are logarithmic without stating the balance condition is incomplete.
Traversals. The three orders are named after the position of the node relative to its subtrees, and the left subtree is always handled before the right. Pre-order is node, left, right; it records a parent before its children, so it is the correct order to copy or serialise a tree. In-order is left, node, right; on a binary search tree it outputs the values in sorted order. Post-order is left, right, node; it processes both children before the node, which is what is required to free memory safely and to evaluate an expression tree, since both operands must be known before the operator is applied.
Choosing a structure. The decision follows from the operations required. Direct access by position points to an array. Frequent insertion and deletion in the middle points to a linked list. A need to reverse or to return to a previous state points to a stack. Fair service in arrival order points to a queue. A need to keep data ordered while still inserting and searching quickly points to a tree. Naming the operation that dominates is what earns the mark, not naming the structure.
Thuật ngữ. Cây nhị phân gồm các nút, mỗi nút có nhiều nhất hai nút con. Gốc là nút duy nhất không có cha; lá là nút không có con; độ sâu của một nút là số cạnh tính từ gốc; chiều cao của cây là độ sâu của nút sâu nhất. Bất kỳ nút nào cùng toàn bộ phần nằm dưới nó tạo thành một cây con, và đó là lý do gần như mọi thuật toán trên cây đều đệ quy một cách tự nhiên: một cây là một nút cộng hai cây nhỏ hơn.
Tính chất của cây tìm kiếm nhị phân. Trong cây tìm kiếm nhị phân, mọi giá trị trong cây con TRÁI của một nút đều nhỏ hơn nút đó, và mọi giá trị trong cây con PHẢI đều lớn hơn. Việc chèn một giá trị bắt đầu từ gốc và rẽ trái hoặc rẽ phải ở mỗi nút cho tới khi gặp một vị trí trống. Việc tìm kiếm dùng cùng phép so sánh ở mỗi bước, và vì mỗi phép so sánh loại bỏ trọn một cây con, một cây cân bằng có n nút được tìm trong khoảng lôgarit cơ số hai của n bước.
Điều kiện then chốt. Hiệu quả đó phụ thuộc hoàn toàn vào tính cân bằng. Nếu các giá trị được chèn theo đúng thứ tự đã sắp, mỗi giá trị mới đều đi sang phải và cây suy biến thành một chuỗi thẳng — về mặt chức năng là một danh sách liên kết — nên tìm kiếm tốn n bước. Đây là lý do các hệ thống thật dùng cây tự cân bằng, và là lý do một câu trả lời khẳng định cây tìm kiếm nhị phân có bậc lôgarit mà không nêu điều kiện cân bằng thì chưa đầy đủ.
Các kiểu duyệt. Ba thứ tự được đặt tên theo vị trí của nút so với hai cây con, và cây con trái luôn được xử lý trước cây con phải. Duyệt trước là nút, trái, phải; nó ghi nút cha trước các con nên là thứ tự đúng để sao chép hoặc tuần tự hoá cây. Duyệt giữa là trái, nút, phải; trên cây tìm kiếm nhị phân nó xuất ra các giá trị theo thứ tự đã sắp xếp. Duyệt sau là trái, phải, nút; nó xử lý cả hai con trước khi xử lý nút, và đó chính là điều kiện cần để giải phóng bộ nhớ an toàn và để tính giá trị một cây biểu thức, vì phải biết kết quả của cả hai toán hạng trước khi áp dụng toán tử.
Chọn cấu trúc. Quyết định suy ra từ các thao tác cần thực hiện. Cần truy cập trực tiếp theo vị trí thì chọn mảng. Cần chèn và xoá thường xuyên ở giữa thì chọn danh sách liên kết. Cần đảo ngược hoặc quay lại trạng thái trước thì chọn ngăn xếp. Cần phục vụ công bằng theo thứ tự tới thì chọn hàng đợi. Cần giữ dữ liệu có thứ tự mà vẫn chèn và tìm nhanh thì chọn cây. Việc gọi tên được THAO TÁC chi phối mới là thứ được cho điểm, chứ không phải việc gọi tên cấu trúc.
Chèn lần lượt các giá trị 45, 25, 60, 15, 35, 55, 70, 30 vào một cây tìm kiếm nhị phân rỗng. Vẽ cây, xuất ba kiểu duyệt, rồi cho biết điều gì xảy ra nếu cùng bộ giá trị đó được chèn theo thứ tự tăng dần.
Dựng cây. Giá trị 45 vào trước nên thành gốc. Giá trị 25 nhỏ hơn 45 nên sang trái. Giá trị 60 lớn hơn 45 nên sang phải. Giá trị 15 nhỏ hơn 45 rồi nhỏ hơn 25 nên thành con trái của 25. Giá trị 35 nhỏ hơn 45 rồi lớn hơn 25 nên thành con phải của 25. Giá trị 55 lớn hơn 45 rồi nhỏ hơn 60 nên thành con trái của 60. Giá trị 70 lớn hơn 45 rồi lớn hơn 60 nên thành con phải của 60. Giá trị 30 nhỏ hơn 45, lớn hơn 25, nhỏ hơn 35 nên thành con TRÁI của 35.
Cấu trúc cây. Gốc là 45. Con trái của 45 là 25, con phải là 60. Nút 25 có con trái 15 và con phải 35. Nút 35 có con trái 30. Nút 60 có con trái 55 và con phải 70.
Duyệt trước — nút, trái, phải: 45, 25, 15, 35, 30, 60, 55, 70.
Duyệt giữa — trái, nút, phải: 15, 25, 30, 35, 45, 55, 60, 70. Chú ý kết quả này đã được sắp xếp tăng dần, và đó không phải trùng hợp: tính chất trái nhỏ hơn nút và phải lớn hơn nút bảo đảm điều đó với mọi cây tìm kiếm nhị phân. Đây cũng là cách kiểm tra nhanh xem bạn dựng cây có đúng không — nếu duyệt giữa không cho dãy tăng dần thì chắc chắn có nút đặt sai chỗ.
Duyệt sau — trái, phải, nút: 15, 30, 35, 25, 55, 70, 60, 45. Chú ý gốc 45 nằm ở cuối cùng, đúng như dự đoán vì nút luôn được xử lý sau hai cây con.
Nếu chèn theo thứ tự tăng dần 15, 25, 30, 35, 45, 55, 60, 70. Giá trị 15 thành gốc. Giá trị 25 lớn hơn nên sang phải. Giá trị 30 lớn hơn cả 15 lẫn 25 nên sang phải tiếp. Mọi giá trị sau đều lớn hơn tất cả các nút đã có nên luôn đi sang phải. Kết quả là một chuỗi thẳng đi xuống bên phải, chiều cao bằng 7 thay vì 3.
Hệ quả. Cây suy biến này về mặt chức năng chính là một danh sách liên kết. Việc tìm giá trị 70 tốn 8 phép so sánh thay vì 3, tức thời gian tìm kiếm chuyển từ bậc lôgarit sang bậc tuyến tính. Điều oái oăm là dữ liệu đã được sắp xếp lại là trường hợp xấu nhất cho cây tìm kiếm nhị phân, dù nó là trường hợp tốt nhất cho tìm kiếm nhị phân trên mảng. Đây là lý do các thư viện thật dùng cây tự cân bằng, vốn xoay lại cấu trúc sau mỗi lần chèn để giữ chiều cao ở bậc lôgarit.
Biểu thức (3 cộng 5) nhân (10 trừ 4) được biểu diễn bằng một cây, trong đó các nút lá là toán hạng và các nút trong là toán tử. Hãy mô tả cây, xuất ba kiểu duyệt, và giải thích vì sao duyệt sau là thứ tự đúng để tính giá trị.
Cấu trúc cây. Gốc là toán tử nhân, vì đó là phép cuối cùng được thực hiện. Cây con trái của gốc có nút là toán tử cộng với hai lá 3 và 5. Cây con phải có nút là toán tử trừ với hai lá 10 và 4. Nguyên tắc chung: toán tử nào được thực hiện sau cùng thì nằm ở gốc, và cấu trúc cây đã mã hoá sẵn thứ tự ưu tiên nên không cần dấu ngoặc nữa.
Duyệt trước — nút, trái, phải: nhân, cộng, 3, 5, trừ, 10, 4. Đây chính là ký pháp tiền tố, còn gọi là ký pháp Ba Lan.
Duyệt giữa — trái, nút, phải: 3, cộng, 5, nhân, 10, trừ, 4. Đây là ký pháp trung tố quen thuộc, nhưng hãy chú ý một điều quan trọng: nó đã MẤT dấu ngoặc, nên đọc lại chuỗi này theo quy tắc ưu tiên thông thường sẽ cho 3 cộng 5 nhân 10 trừ 4, tức một biểu thức khác hẳn. Đây là lý do ký pháp trung tố cần dấu ngoặc còn hai ký pháp kia thì không.
Duyệt sau — trái, phải, nút: 3, 5, cộng, 10, 4, trừ, nhân. Đây là ký pháp hậu tố, còn gọi là ký pháp Ba Lan ngược.
Vì sao duyệt sau là thứ tự tính đúng. Để áp dụng một toán tử, phải biết trước giá trị của cả hai toán hạng. Duyệt sau bảo đảm đúng điều đó, vì nó xử lý xong cả cây con trái lẫn cây con phải rồi mới tới nút. Duyệt trước thì ngược lại: nó gặp toán tử nhân trước khi biết bất kỳ toán hạng nào, nên không thể tính ngay.
Cách máy tính thực sự tính chuỗi hậu tố, và đây là chỗ nối với ngăn xếp. Đọc chuỗi từ trái sang phải. Gặp một toán hạng thì đẩy vào ngăn xếp. Gặp một toán tử thì lấy ra HAI phần tử trên cùng, áp dụng toán tử, rồi đẩy kết quả trở lại. Lần theo chuỗi 3, 5, cộng, 10, 4, trừ, nhân: đẩy 3; đẩy 5; gặp cộng nên lấy ra 5 và 3, tính 8, đẩy 8; đẩy 10; đẩy 4; gặp trừ nên lấy ra 4 và 10, tính 6, đẩy 6; gặp nhân nên lấy ra 6 và 8, tính 48, đẩy 48. Ngăn xếp còn đúng một giá trị và đó là kết quả.
Chú ý về thứ tự toán hạng. Với phép trừ và phép chia, thứ tự quan trọng: phần tử lấy ra ĐẦU TIÊN là toán hạng thứ HAI. Ở ví dụ trên, lấy ra 4 rồi lấy ra 10, và phép tính đúng là 10 trừ 4 chứ không phải 4 trừ 10. Đây là lỗi hay gặp nhất khi lần vết bài toán dạng này.
Bẫy 2 — nhớ ba kiểu duyệt bằng cách học thuộc dãy kết quả. Hãy nhớ theo quy tắc: tên gọi chỉ vị trí của NÚT so với hai cây con, và cây con trái luôn xử lý trước cây con phải. Từ quy tắc đó suy ra được kết quả cho mọi cây.
Bẫy 3 — lấy sai thứ tự toán hạng khi tính biểu thức hậu tố bằng ngăn xếp. Phần tử lấy ra ĐẦU TIÊN là toán hạng THỨ HAI của phép toán. Với phép cộng và phép nhân thì không sao, nhưng với phép trừ và phép chia thì sai hoàn toàn.
Đọc xong rồi — làm thử ngay
Bài tập của chương Abstract Data Structures (HL) gồm 14 câu trắc nghiệm và 5 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.