Xem mã nguồn của Cây nhị phân

{{distinguish|B-tree}}
[[Hình:binary tree.svg|right|192px|thumb|Một cây nhị phân được gắn nhãn có kích thước là 9 và chiều cao là 3, với nút gốc có giá trị là 2. Cây trên không cân bằng và không được sắp xếp.]]

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ấu trúc cây|cây]] mà mỗi nút có nhiều nhất hai [[nút con]], được gọi là ''{{visible anchor|con trái}}'' (''left child'') và ''{{visible anchor|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).<ref name="GarnierTaylor2009">{{chú thích sách|author1=Rowan Garnier|author2=John Taylor|title=Discrete Mathematics: Proofs, Structures and Applications, Third Edition|url=https://books.google.com/books?id=WnkZSSc4IkoC&pg=PA620|year=2009|publisher=CRC Press|isbn=978-1-4398-1280-8|page=620}}</ref> 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.<ref name="Skiena2009">{{chú thích sách|author=Steven S Skiena|title=The Algorithm Design Manual|url=https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA77|year=2009|publisher=Springer Science & Business Media|isbn=978-1-84800-070-4|page=77}}</ref>

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 (lý thuyết đồ thị)|arborescence]].<ref name="Knuth1997">{{chú thích sách|author=Knuth|title=The Art Of Computer Programming, Volume 1, 3/E|year=1997|publisher=Pearson Education|isbn=0-201-89683-4|page=363}}</ref> Vì vậy cây nhị phân có thể gọi là '''arborescence phân nhánh đôi''' (''bifurcating arborescence'')<ref name="Knuth1997"/>—một thuật ngữ xuất hiện trong các sách lập trình rất cũ,<ref name="Flores1971">{{chú thích sách|author=Iván Flores|title=Computer programming system/360|year=1971|publisher=Prentice-Hall|page=39}}</ref> 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à [[cây có thứ tự|thứ tự]]<ref>{{chú thích sách|author=Kenneth Rosen|title=Discrete Mathematics and Its Applications, 7th edition|year=2011|publisher=McGraw-Hill Science|page=749|isbn=978-0-07-338309-5}}</ref> 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.<ref name="Mazur2010">{{chú thích sách|author=David R. Mazur|title=Combinatorics: A Guided Tour|url=https://books.google.com/books?id=yI4Jx5Obr08C&pg=PA246|year=2010|publisher=Mathematical Association of America|isbn=978-0-88385-762-5|page=246}}</ref> 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.

== Các loại cây nhị phân ==
Thuật ngữ về cây không được chuẩn hóa tốt và do đó thay đổi trong các tài liệu.
* Một cây nhị phân '''{{visible anchor|gốc}}''' có một [[nút gốc]] và mỗi nút có tối đa hai nút con.
[[Tập tin:Full binary.svg|thumbnail|Cây nhị phân đầy đủ]]
[[Tập tin:Waldburg Ahnentafel.jpg|thumb|Một [[biểu đồ tổ tiên]] có thể được ánh xạ thành một cây nhị phân hoàn hảo có 4 cấp độ.]]
* Một cây nhị phân '''{{visible anchor|đầy đủ}}''' (đôi khi được gọi là '''đúng đắn'''<ref>{{chú thích sách|last1=Tamassia|first1=Michael T. Goodrich, Roberto |title=Algorithm design : foundations, analysis, and Internet examples|url=https://archive.org/details/algorithmdesignf0000good| date=2011| publisher=Wiley-India|location=New Delhi| isbn=978-81-265-0986-7| page=[https://archive.org/details/algorithmdesignf0000good/page/n89 76]|edition=2|ref=Goodrich}}</ref> hay '''phẳng''' hay cây nhị phân '''nghiêm ngặt''')<ref>{{chú thích web| url=http://xlinux.nist.gov/dads/HTML/fullBinaryTree.html | title=cây nhị phân đầy đủ | publisher = [[NIST]]}}</ref> <ref>Richard Stanley, Enumerative Combinatorics, volume 2, p.36</ref> là một cây có mỗi nút đều có hoặc không có hoặc 2 nút con. Một cách định nghĩa khác cho cây nhị phân đầy đủ là một [[cách định nghĩa đệ quy]]. Một cây nhị phân đầy đủ gồm:<ref name="Rosen2011">{{chú thích sách|author=Kenneth Rosen| title=Discrete Mathematics and Its Applications 7th edition| year=2011| publisher=McGraw-Hill Science|pages=352–353|isbn=978-0-07-338309-5}}</ref>
** Một đỉnh đơn lẻ (một nút đơn lẻ làm nút gốc).
** Một cây có nút gốc có hai nhánh con, cả hai đều là cây nhị phân đầy đủ.
* Một cây nhị phân '''{{visible anchor|hoàn hảo}}''' là một cây nhị phân mà tất cả các nút bên trong đều có hai nút con ''và'' tất cả các nút lá đều có cùng ''độ sâu'' hoặc cùng ''cấp độ'' (cấp độ của một nút được định nghĩa là số đường nối từ nút gốc đến nút đó).<ref>{{chú thích web| url=https://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html|title=cây nhị phân hoàn hảo | publisher = [[NIST]]}}</ref> Một ví dụ về cây nhị phân hoàn hảo là [[biểu đồ tổ tiên]] của một người đến một độ sâu nhất định nhỏ hơn mức mà tổ tiên sẽ xuất hiện nhiều hơn một lần trong biểu đồ (tại thời điểm này, biểu đồ không còn là một cây có các nút duy nhất; chú ý là cùng một tổ tiên có thể xuất hiện ở các độ sâu khác nhau trong biểu đồ), vì mỗi người có đúng hai cha mẹ sinh học (một mẹ và một cha). Miễn là biểu đồ tổ tiên luôn hiển thị mẹ và cha ở cùng một bên cho một nút nhất định, giới tính của họ có thể được coi là tương đương với nút con trái và phải, ''con'' ở đây được hiểu là một thuật ngữ thuật toán. Một cây nhị phân hoàn hảo là một cây nhị phân đầy đủ, nhưng đảo ngược của nó không nhất thiết đúng.
* Một cây nhị phân '''{{visible anchor|hoàn chỉnh}}''' là một cây nhị phân trong đó mọi cấp độ, ''ngoại trừ có thể là cấp cuối cùng'', đều được lấp đầy hoàn toàn và tất cả các nút ở cấp cuối cùng nằm càng bên trái càng tốt. Nó có thể có từ 1 đến 2<sup>''h''</sup> nút ở cấp cuối cùng ''h''.<ref name="complete binary tree">{{chú thích web| url=https://xlinux.nist.gov/dads/HTML/completeBinaryTree.html|title=cây nhị phân hoàn chỉnh| publisher = NIST}}</ref> Một cây hoàn hảo vì vậy luôn luôn là hoàn chỉnh nhưng một cây hoàn chỉnh không nhất thiết hoàn hảo.  Một số tác giả sử dụng thuật ngữ '''hoàn chỉnh''' để chỉ một cây nhị phân '''hoàn hảo''' như được định nghĩa ở trên, trong trường hợp đó họ gọi loại cây này (với một cấp cuối không nhất thiết phải lấp đầy) là cây nhị phân '''gần như hoàn chỉnh''' hoặc '''hầu như hoàn chỉnh'''.<ref name="almost complete binary tree">{{chú thích web| url=http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html|title=cây nhị phân gần như hoàn chỉnh|access-date=2015-12-11|archive-url=https://web.archive.org/web/20160304081430/http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html|archive-date=2016-03-04|url-status=dead}}</ref><ref name="nearly complete binary tree">{{chú thích web |url=http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/nearly_complete.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/nearly_complete.pdf |archive-date=2022-10-09 |url-status=live| title=cây nhị phân hầu như hoàn chỉnh}}</ref> Một cây nhị phân hoàn chỉnh có thể được biểu diễn hiệu quả bằng một mảng.<ref name="complete binary tree"/>

[[Tập tin:Complete binary2.svg|alt=|thumb|Cây nhị phân hoàn chỉnh (không đầy đủ)]]

* Trong cây nhị phân '''vô hạn hoàn chỉnh''', cây có <math>{\aleph_0}</math> cấp độ, trong đó ở mỗi cấp độ ''d'' số nút hiện có ở cấp độ d bằng 2<sup>''d''</sup>. Số lượng phần tử của tập hợp tất cả các cấp độ là <math>{\aleph_0}</math> (vô hạn đếm được). Số lượng phần tử của tập hợp tất cả các đường đi (các "lá", cứ coi như vậy) là không đếm được, có [[số lượng của liên tục]].
* Một cây nhị phân '''cân bằng''' là một cấu trúc cây nhị phân trong đó nhánh con trái và nhánh con phải của mỗi nút không chênh lệch về chiều cao (số đường nối từ nút trên cùng đến nút xa nhất trong nhánh con) không quá 1.<ref>Aaron M. Tenenbaum, et al. Data Structures Using C, Prentice Hall, 1990 {{ISBN|0-13-199746-7}}</ref> Người ta cũng có thể xem xét các cây nhị phân trong đó không có lá nào xa gốc hơn các lá khác. (Các lược đồ cân bằng khác nhau cho phép các định nghĩa khác nhau về "xa hơn". <ref>Paul E. Black (ed.), mục ''cấu trúc dữ liệu'' trong ''[[Dictionary of Algorithms and Data Structures]]''. Viện [[National Institute of Standards and Technology]] của Mỹ. 15 tháng 12 năm 2004. [http://xw2k.nist.gov/dads//HTML/balancedtree.html Phiên bản trực tuyến] {{webarchive|url=https://web.archive.org/web/20101221085950/http://xw2k.nist.gov/dads/|date=December 21, 2010}} Truy cập ngày 2010-12-19. </ref>)
* Một cây '''tàu lượn''' (hoặc '''bệnh lý''') là một cây mà mỗi nút cha chỉ có một nút con liên quan.<ref>{{chú thích web|url=https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254|title=Các loại cây nhị phân với minh họa đầy màu sắc|last=Parmar|first=Anand K.|ngày=2020-01-22|website=Medium|ngôn ngữ=en|ngày truy cập=2020-01-24}}</ref> Điều này có nghĩa là cây sẽ hoạt động như một cấu trúc dữ liệu [[danh sách liên kết]]. Trong trường hợp này, lợi ích của việc sử dụng cây nhị phân bị giảm đáng kể vì nó về cơ bản là một danh sách liên kết có độ phức tạp [[độ phức tạp thời gian]] là O(''n'') (''n'' là số nút) và nó có nhiều không gian dữ liệu hơn danh sách liên kết do hai con trỏ cho mỗi nút, trong khi độ phức tạp O(log<sub>2</sub>''n'') cho tìm kiếm dữ liệu trong cây nhị phân cân bằng thường được mong đợi.
== Xem thêm ==
* [[Ahnentafel]]
* [[Cây AVL]]
* [[Cây đỏ đen]]
* [[Cây splay]]

== Tham khảo ==

=== Trích dẫn ===
{{tham khảo|33em}}

=== Thư mục ===
* [[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.&nbsp;318–348).

== Liên kết ngoài ==
{{thể loại Commons|Cây nhị phân}}
* [http://www.findstat.org/BinaryTrees binary trees] {{Webarchive|url=https://web.archive.org/web/20200923083018/http://www.findstat.org/BinaryTrees |date=2020-09-23 }} entry in the [http://www.findstat.org/ FindStat] database
* [http://www.gamedev.net/page/resources/_/technical/general-programming/trees-part-2-binary-trees-r1433 Gamedev.net introduction on binary trees]
* [http://www.brpreiss.com/books/opus4/html/page355.html Binary Tree Proof by Induction]
* [http://piergiu.wordpress.com/2010/02/21/balanced-binary-search-tree-on-array/ Balanced binary search tree on array How to create bottom-up an Ahnentafel list, or a balanced binary search tree on array]
* [http://www.cpphub.com/search/label/Binary%20trees Binary trees and Implementation of the same with working code examples]

{{Cây trong khoa học máy tính}}

{{DEFAULTSORT:Cây nhị phân}}
[[Thể loại:Cây nhị phân| ]]