Cây nhị phân
Trong khoa học máy tính, cây nhị phân (tiếng Anh: binary tree) là một cấu trúc dữ liệu cây mà mỗi nút có nhiều nhất hai nút con, được gọi là con trái (left child) và con phải (right child). Một định nghĩa đệ quy chỉ sử dụng các khái niệm lý thuyết tập hợp là cây nhị phân không trống là một tuple (L, S, R), với L và R là các cây nhị phân hay tập hợp rỗng và S là tập đơn (singleton set).[1] Một số tác giả cho phép cây nhị phân cũng có thể là tập hợp trống.[2]
Từ góc độ lý thuyết đồ thị, cây nhị phân (và K-ary) như định nghĩa ở đây thực sự là arborescence.[3] Vì vậy cây nhị phân có thể gọi là arborescence phân nhánh đôi (bifurcating arborescence)[3]—một thuật ngữ xuất hiện trong các sách lập trình rất cũ,[4] trước khi thuật ngữ khoa học máy tính hiện đại chiếm ưu thế. Cũng có thể hiểu cây nhị phân là một đồ thị vô hướng chứ không phải đồ thị có hướng, trong trường hợp đó cây nhị phân là một cây có gốc và thứ tự[5] Một số tác giả dùng thuật ngữ cây nhị phân có gốc thay vì cây nhị phân để nhấn mạnh thực tế rằng cây có gốc, nhưng như được định nghĩa ở trên thì cây nhị phân luôn có gốc.[6] Cây nhị phân là trường hợp đặc biệt của cây K-ary, với k bằng 2.
Xem thêm[sửa | sửa mã nguồn]
Tham khảo[sửa | sửa mã nguồn]
Trích dẫn[sửa | sửa mã nguồn]
- ^ Rowan Garnier; John Taylor (2009). Discrete Mathematics: Proofs, Structures and Applications, Third Edition. CRC Press. tr. 620. ISBN 978-1-4398-1280-8.
- ^ Steven S Skiena (2009). The Algorithm Design Manual. Springer Science & Business Media. tr. 77. ISBN 978-1-84800-070-4.
- ^ a b Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. tr. 363. ISBN 0-201-89683-4.
- ^ Iván Flores (1971). Computer programming system/360. Prentice-Hall. tr. 39.
- ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. tr. 749. ISBN 978-0-07-338309-5.
- ^ David R. Mazur (2010). Combinatorics: A Guided Tour. Mathematical Association of America. tr. 246. ISBN 978-0-88385-762-5.
Thư mục[sửa | sửa mã nguồn]
- Donald Knuth. The Art of Computer Programming vol 1. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3, especially subsections 2.3.1–2.3.2 (pp. 318–348).
Liên kết ngoài[sửa | sửa mã nguồn]
 |
Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Cây nhị phân. |
- binary trees Lưu trữ 2020-09-23 tại Wayback Machine entry in the FindStat database
- Gamedev.net introduction on binary trees
- Binary Tree Proof by Induction
- Balanced binary search tree on array How to create bottom-up an Ahnentafel list, or a balanced binary search tree on array
- Binary trees and Implementation of the same with working code examples