Cấu trúc dữ liệu Python: Cây cho

Cây Python rất giống danh sách liên kết, nhưng có thứ tự phân cấp. Cây bao gồm các nút liên kết với các nút khác. Nút dưới cùng không có liên kết được gọi là lá . Nút được liên kết với một nút khác được gọi là nút cha và nút được liên kết đến là nút con.

Một cây thường được xây dựng với nhiều nút hoặc cấu trúc sâu xếp tầng. Vì vậy, bạn có thể nói một cái cây rộng hoặc sâu .

Một phiên bản hiệu quả của cấu trúc cây được gọi là cây tìm kiếm nhị phân. Đó là nơi bạn chỉ cho phép một nút cha có hai nút con. Nút bên trái có giá trị nhỏ hơn nút bên phải. Việc xây dựng một cái cây như thế này làm cho việc đi qua và tìm một giá trị cụ thể rất hiệu quả.

Trong ví dụ trên, nếu tôi muốn tìm giá trị 98 từ 39, tôi sẽ di chuyển sang phải 98> 39 - từ 70 di chuyển sang phải một lần nữa - từ 97 di chuyển sang phải và trong ba lần di chuyển, tôi đã tìm thấy nút mong muốn của mình.

Vì vậy, hãy xây dựng một nút cây trong python và xem một nút đang hoạt động. Tất cả những gì chúng ta cần để bắt đầu một nút cây là một cái tên. Chúng tôi sẽ tự động gán cho nó một danh sách trống để chứa tất cả các nút con sắp tới.

Nếu bạn đã đọc các bài viết trước đây của tôi về cấu trúc dữ liệu python, điều này sẽ trông quen thuộc.

Bây giờ, như với bất kỳ cấu trúc dữ liệu nào, chúng ta phải ghi nhớ các chức năng thực tế mà chúng ta muốn cây của chúng ta có. Thêm một nút và xóa một nút là những lựa chọn hiển nhiên và cũng dễ thực hiện.

Để thêm, tôi sẽ sử dụng phương thức append () và để xóa, tôi chỉ cần lặp lại danh sách self.children và thêm lại tất cả các nút, ngoại trừ nút tôi muốn xóa.

Tiếp theo, chúng ta sẽ đi ngang qua cây để tìm thông tin chúng ta muốn. Để xây dựng phương pháp này, chúng tôi sẽ bắt đầu với một danh sách trống để điền vào mỗi nút để truy cập. Mặc dù nút đó có các nút con, chúng tôi sẽ bật nó ra và thêm nó vào danh sách các nút để truy cập.

Bạn nghĩ cấu trúc dữ liệu như thế này sẽ được sử dụng ở đâu tốt nhất? Có lẽ nếu chúng tôi thêm một số logic để truy cập các nút, chúng tôi có thể phân chia rất nhiều đặc quyền mà người dùng có thể có.

Cây dữ liệu là một công cụ tuyệt vời và được sử dụng rộng rãi trong thế giới mã hóa. Tôi hy vọng phần giới thiệu ngắn gọn này ít nhất cũng mang lại một cái nhìn đáng giá về lý do tại sao bạn muốn biết về những cấu trúc này.