Kích thước
Số lần so sánh

Thao tác Trung bình Trường hợp xấu nhất

Thêm thông tin về cấu trúc dữ liệu

Trực quan hóa cấu trúc dữ liệu

Cấu trúc dữ liệu là cách cất giữ dữ liệu sao cho những câu hỏi hay gặp nhất được trả lời nhanh. Hãy chọn một trong mười một cấu trúc kinh điển, từ ngăn xếp đến cây đỏ-đen, nhập một giá trị rồi nhấn một thao tác. Mỗi bước diễn ra trên màn hình: nút nào được so sánh, liên kết nào thay đổi, vì sao cây quay hay một giá trị nổi lên, kèm một câu nói rõ điều đang xảy ra. Các ô đếm khối lượng việc của mỗi thao tác, và một bảng cho biết thời gian chạy của nó. Chọn một cấu trúc, nhập một giá trị rồi nhấn một thao tác. Mỗi thao tác được phát từng bước: các nút được tô sáng cho thấy cái gì đang được so sánh, di chuyển hay thay đổi, và dòng dưới hình nói điều gì xảy ra và vì sao. Lùi, Bước, Phát và Cuối cho phép xem lại các bước. Điền ngẫu nhiên và Xóa hết bắt đầu lại từ đầu, còn Hoàn tác rút lại một thao tác. Các ô hiển thị kích thước, chiều cao của cây, khối lượng việc của thao tác vừa rồi (số lần so sánh, dò hoặc liên kết cha đã đi theo) và một con số quan trọng với cấu trúc đó; bảng cho biết thời gian chạy của từng thao tác.

Cách nó hoạt động

  1. Chọn một cấu trúc, chẳng hạn cây tìm kiếm nhị phân, bảng băm hay trie. Nó bắt đầu với nội dung ngẫu nhiên; Điền ngẫu nhiên và Xóa hết bắt đầu lại.
  2. Nhập một giá trị rồi nhấn một thao tác: push, đưa vào hàng, chèn, xóa, tìm, duyệt, union hoặc find. Các bước tự phát; Lùi, Bước, Phát và Cuối cho phép xem lại.
  3. Đọc ở dòng dưới hình xem mỗi bước làm gì, theo dõi kích thước, chiều cao và khối lượng việc của thao tác vừa rồi ở các ô, và so sánh thời gian chạy trong bảng.

Danh sách, ngăn xếp và hàng đợi

Những cấu trúc đơn giản nhất xếp các phần tử thành một hàng. Ngăn xếp chỉ làm việc ở một đầu, nên phần tử vào sau cùng ra đầu tiên, như một chồng đĩa; hàng đợi thêm vào cuối và lấy ra ở đầu, như hàng người trước quầy. Hàng đợi ở đây nằm trong một bộ đệm vòng: đầu và cuối chạy vòng quanh một mảng cố định và quay lại đầu mảng khi vượt quá cuối, và khi đầy, các phần tử được sao chép sang một bộ đệm lớn gấp đôi. Danh sách liên kết nối các nút bằng con trỏ, nên chèn vào đầu gần như không tốn gì, nhưng muốn tìm đuôi hay một chỉ số thì phải đi theo từng liên kết một.

Cây, đống, bảng băm và tập hợp

Cây tìm kiếm nhị phân đặt giá trị nhỏ hơn bên trái và lớn hơn bên phải, nên mỗi bước tìm kiếm loại được một nửa số ứng viên, miễn là cây còn sum suê. Cây AVL và cây đỏ-đen bảo đảm điều đó bằng các phép quay mà bạn có thể quan sát và được đặt tên theo trường hợp của chúng. Đống chỉ giữ giá trị nhỏ nhất hoặc lớn nhất ở trên cùng, và hàng đợi ưu tiên chỉ cần có vậy. Bảng băm nhảy thẳng tới một thùng tính từ khóa và phải xử lý va chạm; trie dùng chung tiền tố của các từ; union-find trả lời trong thời gian gần như hằng số liệu hai phần tử có cùng một tập hay không.

Câu hỏi thường gặp

Tôi nên dùng cấu trúc dữ liệu nào?

Điều đó tùy vào những câu hỏi bạn hay đặt ra nhất. Ngăn xếp hoặc hàng đợi khi các phần tử được xử lý theo thứ tự đến hoặc ngược lại; bảng băm để tra một khóa; cây tìm kiếm cân bằng như cây AVL hay cây đỏ-đen khi bạn còn cần các khóa theo thứ tự hoặc khóa gần nhất; đống khi bạn chỉ luôn cần phần tử nhỏ nhất hoặc lớn nhất; trie cho từ và tiền tố; union-find để theo dõi các nhóm nhập lại với nhau.

Cây AVL và cây đỏ-đen khác nhau thế nào?

Cả hai đều giữ cây tìm kiếm nhị phân nông, nên mỗi lần tìm, chèn hay xóa chỉ mất thời gian tỉ lệ với log n. Cây AVL cân bằng chặt chẽ hơn, chiều cao hai bên của mỗi nút chênh nhau không quá một, nên tìm kiếm nhanh hơn đôi chút. Cây đỏ-đen cho phép xê dịch nhiều hơn và cần ít phép quay hơn khi thay đổi, vì vậy nhiều thư viện chuẩn dùng nó cho các map và set có thứ tự.

Vì sao bảng băm có thể chậm trong trường hợp xấu nhất?

Nếu nhiều khóa rơi vào cùng một thùng, việc tìm kiếm phải kiểm tra từng khóa một, y như với danh sách. Một hàm băm tốt rải khóa đều ra và bảng được nới rộng trước khi quá đầy, nên trung bình mỗi lần tìm chỉ mất thời gian hằng số. Hãy thử bảng kích thước 10 với các số tận cùng bằng cùng một chữ số, hoặc những từ là đảo chữ của nhau, để thấy va chạm chồng chất.

Các con số bên cạnh nút AVL có nghĩa là gì?

Đó là hệ số cân bằng: chiều cao cây con trái của một nút trừ đi chiều cao cây con phải. Trong cây AVL, mọi hệ số cân bằng phải là −1, 0 hoặc +1. Khi một lần chèn hay xóa làm một hệ số thành +2 hoặc −2, cây quay tại nút đó; trường hợp (LL, RR, LR hoặc RL) cho biết phần chiều cao dư nghiêng về phía nào và quyết định cần một hay hai phép quay.

Có gì được gửi lên máy chủ không?

Không. Mọi thao tác đều chạy trong trình duyệt của bạn, và nội dung của mỗi cấu trúc được lưu trong bộ nhớ cục bộ của trình duyệt này.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Tới trình chỉnh sửa