Khám phá cây qua JavaScript
Cây là cấu trúc dữ liệu phổ biến nhất mà bạn đã tương tác. Từ hệ thống file của bạn đến DOM, nhiều thứ mà máy tính của bạn thực hiện hoàn toàn phụ thuộc vào việc tạo và thao tác cây.
Cây là gì?
Nói tóm lại, cây là một tập hợp các node / giá trị trong đó mỗi nút trỏ đến các node giảm dần và tất cả đều kết nối với một nút cha duy nhất. Hãy xem cái cây mà bạn có thể quen thuộc nhất: DOM.
Tại root của cây, ta có document (thực ra là cửa sổ nhưng shhh) và mỗi thẻ HTML ta thêm vào sẽ tạo ra một nút con mới bên dưới nó. Điểm chính về cây là dù ta có bao nhiêu nút, ta có thể chọn bất kỳ ai một cách ngẫu nhiên và luôn có thể tìm đường trở lại root hoặc bất kỳ phần tử nào khác.
Cây hợp lệ so với cây không hợp lệ
Trước đây, khi ta tạo danh sách liên kết, về mặt kỹ thuật, ta đã tạo ra các cây khả thi vì chúng có root (đầu / đuôi) và mỗi nút được kết nối với một nút con với các con trỏ tiếp theo / trước. Bắt đầu từ bất kỳ nút nào, ta luôn có thể tìm đường trở lại một root duy nhất, nhưng nó hơi tầm thường với chỉ một chuỗi các node .
Tất cả đều là cây hợp lệ. Hầu hết các cấu trúc khác nhau của ta dựa trên cây cối sẽ liên quan nhiều hơn đến cách tổ chức dữ liệu bên trong cây, nhưng tất cả chúng sẽ trông giống như thế này.
Có một số luật ta cần tuân theo để có một cây thích hợp. Một cây không thể tham chiếu đến root của chính nó, chẳng hạn nếu ta chạy một thuật toán duyệt trên một danh sách liên kết vòng tròn thì nó sẽ nhanh chóng trở thành cơn ác mộng đệ quy. Ta cũng không thể có nhiều hơn một root hoặc một nút với nhiều hơn một cha mẹ.
Cuối cùng, một cái cây phải có định hướng cho nó với mọi thứ di chuyển ra khỏi root . Một cụm nút không có hướng thực sự là cấu trúc, biểu đồ phức tạp hơn nhiều của chính nó, mà ta sẽ đề cập trong các bài viết sau 😉.
Ta không thể bắt đầu liên kết các node với nhau và gọi nó là một cây, nếu ta phá vỡ các luật này thì các cấu trúc dữ liệu và thuật toán trong tương lai sẽ không thể thực hiện được.
Giải phẫu cây
Mặc dù khá nhàm chán, nhưng vẫn cần thiết để bao gồm các thuật ngữ quan trọng nhất mà bạn sẽ thấy liên tục khi bạn tìm hiểu thêm về cây cối.
-
Node- Mỗi đối tượng hoặc điểm dữ liệu đơn lẻ. -
Root- Nút đầu tiên và trên cùng trong cây mà từ đó tất cả các node khác có nguồn root . -
Edge- Một kết nối giữa hai nút. -
Parent- Tổ tiên trực tiếp của nút thấp hơn. -
child- Con cháu ngay lập tức của nút cao hơn. -
Siblings- Hai nút trên cùng độ sâu với cùng một nút cha. -
Leafs- Các node dưới cùng không có nút con. -
Depth- Chiều cao của cây được đo bằng cấp với số cạnh tính từ root , do đó cấp 2 chỉ cách root hai cạnh. -
Breadth- Chiều rộng của cây được đo bằng số lá. -
Subtree- Một nút và con cháu của nó có thể được coi như một cây độc lập. Ví dụ: nếu ta tạo từ điển dưới dạng cây và sử dụng thuật toán tìm kiếm xem xét từng mục theo thứ tự bảng chữ cái, ta có thể sử dụng nút cho phần của chữ cái đầu tiên làm root thay vì xem mọi mục trong cây.
Bớt tư tưởng
Ngay bây giờ điều này có vẻ giống như một mớ lông tơ nhưng ma quỷ thực sự nằm trong chi tiết. Khi bạn tiến đến các cấu trúc phức tạp hơn, bạn sẽ ngày càng dễ dàng bỏ qua những chi tiết này và chìm đắm trong những lỗi rất khó sửa.
Các tin liên quan
Giới thiệu về danh sách được liên kết qua JavaScript - Phần 2: Triển khai2020-02-23
Khám phá các và hàng đợi qua JavaScript
2020-02-23
Câu hỏi phỏng vấn JavaScript: Gotchas phổ biến
2020-02-21
Giới thiệu về danh sách được liên kết qua JavaScript - Phần 1: Tổng quan
2020-02-21
Hiểu Radix Sắp xếp Thông qua JavaScript
2020-02-18
Cách xây dựng PWA trong Vanilla JavaScript
2020-02-17
Hiểu về Sắp xếp nhanh qua JavaScript
2020-02-14
Hiểu bản đồ và thiết lập đối tượng trong JavaScript
2020-02-12
Hiểu Hợp nhất Sắp xếp Thông qua JavaScript
2020-02-08
Tạo biểu mẫu tùy chỉnh bằng API dữ liệu biểu mẫu JavaScript
2020-02-06
