cay nhi phan la gi

By Admin 08/11/2023 0

Bách khoa toàn thư cởi Wikipedia

Đừng lầm lẫn với B-tree.

Bạn đang xem: cay nhi phan la gi

Một cây nhị phân được gắn nhãn với độ cao thấp là 9 và độ cao là 3, với nút gốc có mức giá trị là 2. Cây bên trên ko thăng bằng và ko được bố trí.

Trong khoa học tập PC, cây nhị phân (tiếng Anh: binary tree) là 1 cấu tạo tài liệu cây nhưng mà từng nút có không ít nhất nhị nút con cái, được gọi là con trái (left child) và con phải (right child). Một khái niệm đệ quy chỉ dùng những định nghĩa lý thuyết hội tụ là cây nhị phân ko trống rỗng là 1 tuple (L, S, R), với L và R là những cây nhị phân hoặc hội tụ trống rỗng và S là tập luyện đơn (singleton set).[1] Một số người sáng tác được chấp nhận cây nhị phân cũng hoàn toàn có thể là hội tụ trống rỗng.[2]

Xem thêm: adobe prelude là gì

Từ góc nhìn lý thuyết đồ gia dụng thị, cây nhị phân (và K-ary) như khái niệm ở phía trên thực sự là arborescence.[3] Vì vậy cây nhị phân hoàn toàn có thể gọi là arborescence phân nhánh đôi (bifurcating arborescence)[3]—một thuật ngữ xuất hiện tại trong những sách lập trình sẵn vô cùng cũ,[4] trước lúc thuật ngữ khoa học tập PC tân tiến lúc lắc ưu thế. Cũng hoàn toàn có thể hiểu cây nhị phân là 1 đồ gia dụng thị vô phía chứ không hề cần đồ gia dụng thị được bố trí theo hướng, nhập tình huống ê cây nhị phân là 1 cây với gốc và loại tự[5] Một số người sáng tác sử dụng thuật ngữ cây nhị phân với gốc chứ không cây nhị phân nhằm nhấn mạnh vấn đề thực tiễn rằng cây với gốc, tuy nhiên như được khái niệm phía trên thì cây nhị phân luôn luôn với gốc.[6] Cây nhị phân là tình huống quan trọng của cây K-ary, với k vì như thế 2.

Các loại cây nhị phân[sửa | sửa mã nguồn]

Thuật ngữ về cây ko được chuẩn chỉnh hóa chất lượng và vì thế thay cho thay đổi trong những tư liệu.

  • Một cây nhị phân gốc với cùng một nút gốc và từng nút với tối nhiều nhị nút con cái.
Cây nhị phân lênh láng đủ
Một biểu đồ gia dụng tổ tiên hoàn toàn có thể được ánh xạ trở nên một cây nhị phân tuyệt vời nhất với 4 Lever.
  • Một cây nhị phân đầy đủ (đôi khi được gọi là đúng đắn[7] hoặc phẳng hoặc cây nhị phân nghiêm ngặt)[8] [9] là 1 cây với từng nút đều phải sở hữu hoặc không tồn tại hoặc 2 nút con cái. Một cơ hội khái niệm không giống mang đến cây nhị phân khá đầy đủ là 1 cơ hội khái niệm đệ quy. Một cây nhị phân khá đầy đủ gồm:[10]
    • Một đỉnh đơn lẻ (một nút đơn lẻ thực hiện nút gốc).
    • Một cây với nút gốc với nhị nhánh con cái, cả nhị đều là cây nhị phân khá đầy đủ.
  • Một cây nhị phân hoàn hảo là 1 cây nhị phân nhưng mà toàn bộ những nút bên phía trong đều phải sở hữu nhị nút con cái và toàn bộ những nút lá đều phải sở hữu nằm trong độ sâu hoặc nằm trong cấp độ (cấp phỏng của một nút được khái niệm là số đàng nối kể từ nút gốc cho tới nút đó).[11] Một ví dụ về cây nhị phân tuyệt vời nhất là biểu đồ gia dụng tổ tiên của một người cho tới một phỏng sâu sắc chắc chắn nhỏ rộng lớn nút nhưng mà tổ tiên tiếp tục xuất hiện tại nhiều hơn nữa một lượt nhập biểu đồ gia dụng (tại thời đặc điểm này, biểu đồ gia dụng không hề là 1 cây với những nút duy nhất; lưu ý là nằm trong một đội tiên hoàn toàn có thể xuất hiện tại ở những phỏng sâu sắc không giống nhau nhập biểu đồ), vì như thế từng người dân có đích thị nhị phụ vương u sinh học tập (một u và một cha). Miễn là biểu đồ gia dụng tổ tiên luôn luôn hiển thị u và phụ vương ở và một mặt mũi cho 1 nút chắc chắn, nam nữ của mình hoàn toàn có thể được xem là tương tự với nút con cái ngược và cần, con ở phía trên được hiểu là 1 thuật ngữ thuật toán. Một cây nhị phân tuyệt vời nhất là 1 cây nhị phân khá đầy đủ, tuy nhiên hòn đảo ngược của chính nó ko nhất thiết đích thị.
  • Một cây nhị phân hoàn chỉnh là 1 cây nhị phân nhập ê từng Lever, ngoại trừ hoàn toàn có thể là cung cấp cuối cùng, đều được lấp lênh láng trọn vẹn và toàn bộ những nút ở cung cấp sau cùng ở càng phía trái càng chất lượng. Nó hoàn toàn có thể với từ là một cho tới 2h nút ở cung cấp sau cùng h.[12] Một cây tuyệt vời nhất nên là luôn luôn luôn luôn là hoàn hảo tuy nhiên một cây hoàn hảo ko nhất thiết tuyệt vời nhất. Một số người sáng tác dùng thuật ngữ hoàn chỉnh nhằm duy nhất cây nhị phân hoàn hảo như được khái niệm phía trên, nhập tình huống ê bọn họ gọi loại cây này (với một cung cấp cuối ko nhất thiết cần lấp đầy) là cây nhị phân gần như trả chỉnh hoặc hầu như trả chỉnh.[13][14] Một cây nhị phân hoàn hảo hoàn toàn có thể được trình diễn hiệu suất cao vì như thế một mảng.[12]
Cây nhị phân hoàn hảo (không lênh láng đủ)

Xem thêm[sửa | sửa mã nguồn]

  • Ahnentafel
  • Cây AVL
  • Cây đỏ tía đen
  • Cây splay

Tham khảo[sửa | sửa mã nguồn]

Trích dẫn[sửa | sửa mã nguồn]

  1. ^ Rowan Garnier; John Taylor (2009). Discrete Mathematics: Proofs, Structures and Applications, Third Edition. CRC Press. tr. 620. ISBN 978-1-4398-1280-8.
  2. ^ Steven S Skiena (2009). The Algorithm Design Manual. Springer Science & Business Media. tr. 77. ISBN 978-1-84800-070-4.
  3. ^ a b Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. tr. 363. ISBN 0-201-89683-4.
  4. ^ Iván Flores (1971). Computer programming system/360. Prentice-Hall. tr. 39.
  5. ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. tr. 749. ISBN 978-0-07-338309-5.
  6. ^ David R. Mazur (2010). Combinatorics: A Guided Tour. Mathematical Association of America. tr. 246. ISBN 978-0-88385-762-5.
  7. ^ Tamassia, Michael T. Goodrich, Roberto (2011). Algorithm design : foundations, analysis, and Internet examples (ấn phiên bản 2). New Delhi: Wiley-India. tr. 76. ISBN 978-81-265-0986-7.
  8. ^ “cây nhị phân lênh láng đủ”. NIST.
  9. ^ Richard Stanley, Enumerative Combinatorics, volume 2, p.36
  10. ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications 7th edition. McGraw-Hill Science. tr. 352–353. ISBN 978-0-07-338309-5.
  11. ^ “cây nhị phân trả hảo”. NIST.
  12. ^ a b “cây nhị phân trả chỉnh”. NIST.
  13. ^ “cây nhị phân gần như là trả chỉnh”. Bản gốc tàng trữ ngày 4 mon 3 năm 2016. Truy cập ngày 11 mon 12 năm 2015.
  14. ^ “cây nhị phân đa số trả chỉnh” (PDF). Lưu trữ (PDF) phiên bản gốc ngày 9 mon 10 năm 2022.
  15. ^ Aaron M. Tenenbaum, et al. Data Structures Using C, Prentice Hall, 1990 ISBN 0-13-199746-7
  16. ^ Paul E. Black (ed.), mục cấu trúc dữ liệu nhập Dictionary of Algorithms and Data Structures. Viện National Institute of Standards and Technology của Mỹ. 15 mon 12 năm 2004. Phiên phiên bản trực tuyến Lưu trữ mon 12 21, 2010 bên trên Wayback Machine Truy cập ngày 2010-12-19.
  17. ^ Parmar, Anand K. (22 mon một năm 2020). “Các loại cây nhị phân với minh họa lênh láng color sắc”. Medium (bằng giờ đồng hồ Anh). Truy cập ngày 24 mon một năm 2020.

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 nhận thêm hình hình ảnh và phương tiện đi lại truyền đạt về Cây nhị phân.
  • binary trees Lưu trữ 2020-09-23 bên trên Wayback Machine entry in the FindStat database
  • Gamedev.net introduction on binary trees
  • Binary Tree Proof by Induction
  • Balanced binary tìm kiếm tree on array How to tát create bottom-up an Ahnentafel list, or a balanced binary tìm kiếm tree on array
  • Binary trees and Implementation of the same with working code examples