Thực đơn
trang chủWindows 10

Đánh giá độ phức tạp của cấu trúc dữ liệu và thuật toán. Cấu trúc dữ liệu: khái niệm chung, cách thực hiện. Cấu trúc dữ liệu đơn giản nhất: hàng đợi, ngăn xếp. Sử dụng ngăn xếp và ký hiệu Ba Lan đảo ngược

  • Dịch
  • Chế độ phục hồi

Ekaterina Malakhova, một biên tập viên tự do, đã phỏng theo một bài viết của Beau Carnes về các loại cấu trúc dữ liệu chính, đặc biệt là cho blog Netology.

“Lập trình viên tồi chỉ nghĩ về mã. Những lập trình viên giỏi nghĩ về cấu trúc dữ liệu và các mối quan hệ của chúng." - Linus Torvalds, người tạo ra Linux.

Cấu trúc dữ liệu đóng vai trò quan trọng trong quá trình phát triển phần mềm và cũng là câu hỏi thường gặp trong các cuộc phỏng vấn của nhà phát triển. Tin tốt là về cơ bản chúng chỉ là những định dạng đặc biệt để tổ chức và lưu trữ dữ liệu.

Trong bài viết này, tôi sẽ chỉ cho bạn 10 cấu trúc dữ liệu phổ biến nhất. Đối với mỗi người trong số họ, các video và ví dụ về cách triển khai chúng trong JavaScript đều được cung cấp. Để giúp bạn thực hành, tôi cũng đưa vào một số bài tập từ phiên bản beta của chương trình giảng dạy freeCodeCamp mới.

Trong bài viết này, tôi cung cấp các ví dụ về cách triển khai các cấu trúc dữ liệu này trong JavaScript, chúng cũng sẽ hữu ích nếu bạn đang sử dụng ngôn ngữ cấp thấp như C. Nhiều ngôn ngữ cấp cao, bao gồm cả JavaScript, đã tích hợp sẵn hầu hết các cấu trúc này. cấu trúc dữ liệu chúng ta sẽ thảo luận. Tuy nhiên, kiến ​​thức như vậy sẽ là một lợi thế lớn trong quá trình tìm kiếm việc làm của bạn và sẽ hữu ích khi viết mã hiệu suất cao.

Danh sách liên kết

Danh sách liên kết là một trong những cấu trúc dữ liệu cơ bản. Nó thường được so sánh với một mảng, vì nhiều cấu trúc khác có thể được triển khai bằng cách sử dụng mảng hoặc danh sách liên kết. Hai loại này đều có ưu điểm và nhược điểm.

Đây là cách hoạt động của danh sách liên kết

Danh sách liên kết bao gồm một nhóm các nút cùng nhau tạo thành một chuỗi. Mỗi nút chứa hai thứ: dữ liệu thực tế mà nó lưu trữ (đây có thể là bất kỳ loại dữ liệu nào) và một con trỏ (hoặc liên kết) tới nút tiếp theo trong chuỗi. Ngoài ra còn có các danh sách liên kết đôi: trong đó, mỗi nút có một con trỏ tới cả phần tử tiếp theo và phần tử trước đó trong danh sách.

Các thao tác cơ bản trong danh sách liên kết bao gồm thêm, xóa và tìm kiếm một phần tử trong danh sách.

Độ phức tạp về thời gian của danh sách liên kết ════════ ╗ ║ Thuật toán ║Giá trị trung bình ║ Trường hợp xấu nhất ║ ╠═══════════╬═══════ ══════ ════ ╬═════════ ══════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(n) ║ O(n) ║ ║ Chèn ║ O(1) ║ O(1) ║ ║ Xóa ║ O (1) ║ O(1) ║ ╚═══════════╩══════════════ ═══╩═════ ═════ ═════╝

Các bài tập từ freeCodeCamp

ngăn xếp

Ngăn xếp là cấu trúc dữ liệu cơ bản cho phép các phần tử chỉ được thêm hoặc xóa ngay từ đầu. Nó giống như một chồng sách: nếu bạn muốn xem cuốn sách ở giữa chồng thì trước tiên bạn phải bỏ những cuốn ở trên xuống.

Ngăn xếp được tổ chức theo nguyên tắc LIFO (Last In First Out). Điều này có nghĩa là phần tử cuối cùng bạn thêm vào ngăn xếp sẽ là phần tử đầu tiên được đưa ra khỏi ngăn xếp.


Đây là cách ngăn xếp hoạt động

Ngăn xếp có thể thực hiện ba thao tác: thêm phần tử (đẩy), xóa phần tử (pop) và hiển thị nội dung của ngăn xếp (pip).

Độ phức tạp của thời gian ngăn xếp ═══════╗ ║ Thuật toán ║Giá trị trung bình ║ Trường hợp xấu nhất ║ ╠═══════════╬═════════ ════════ ╬ ══════════ ═════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(n) ║ O(n) ║ ║ Chèn ║ O(1) ║ O(1) ║ ║ Xóa ║ O( 1) ║ O(1) ║ ╚═══════════╩══════════════════ ══╩ ═════ ══════ ════╝

Các bài tập từ freeCodeCamp

Hàng đợi

Cấu trúc này có thể được coi như một hàng tại một cửa hàng tạp hóa. Ai đến ngay từ đầu sẽ được phục vụ trước - giống như trong cuộc sống.


Đây là cách hàng đợi hoạt động

Hàng đợi được sắp xếp theo nguyên tắc FIFO (First In First Out). Điều này có nghĩa là bạn chỉ có thể xóa một phần tử sau khi tất cả các phần tử được thêm trước đó đã bị xóa.

Hàng đợi cho phép bạn thực hiện hai thao tác cơ bản: thêm phần tử vào cuối hàng đợi ( xếp hàng) và xóa phần tử đầu tiên ( xếp hàng).

Độ phức tạp của thời gian xếp hàng ═══════╗ ║ Thuật toán ║Giá trị trung bình ║ Trường hợp xấu nhất ║ ╠═══════════╬═════════ ════════ ╬ ══════════ ═════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(n) ║ O(n) ║ ║ Chèn ║ O(1) ║ O(1) ║ ║ Xóa ║ O( 1) ║ O(1) ║ ╚═══════════╩══════════════════ ══╩ ═════ ══════ ════╝

Các bài tập từ freeCodeCamp

bộ



Đây là những gì rất nhiều trông giống như

Một tập hợp lưu trữ các giá trị dữ liệu không theo thứ tự cụ thể nào mà không lặp lại chúng. Nó không chỉ cho phép bạn thêm và xóa các phần tử mà còn có một số chức năng quan trọng khác có thể được áp dụng cho hai bộ cùng một lúc.

  • Một hợp kết hợp tất cả các phần tử từ hai bộ khác nhau thành một (không trùng lặp).
  • Phép giao phân tích hai tập hợp và tạo một tập hợp khác từ những phần tử có trong cả hai tập hợp ban đầu.
  • Sự khác biệt hiển thị danh sách các phần tử nằm trong một bộ nhưng không nằm trong bộ khác.
  • Tập hợp con tạo ra một giá trị Boolean cho biết liệu một tập hợp có bao gồm tất cả các phần tử của tập hợp khác hay không.
Ví dụ triển khai bằng JavaScript

Các bài tập từ freeCodeCamp

Bản đồ

Bản đồ là cấu trúc lưu trữ dữ liệu theo cặp khóa/giá trị, trong đó mỗi khóa là duy nhất. Đôi khi nó còn được gọi là mảng kết hợp hoặc từ điển. Bản đồ thường được sử dụng để tìm kiếm dữ liệu nhanh chóng. Nó cho phép bạn làm những việc sau:
  • thêm cặp vào bộ sưu tập;
  • xóa các cặp khỏi bộ sưu tập;
  • thay đổi một cặp hiện có;
  • tìm kiếm một giá trị được liên kết với một khóa cụ thể.

Đây là cách cấu trúc bản đồ hoạt động

Các bài tập từ freeCodeCamp

Bảng băm

Đây là cách bảng băm và hàm băm hoạt động

Bảng băm là một cấu trúc giống như Bản đồ chứa các cặp khóa/giá trị. Nó sử dụng hàm băm để tính chỉ mục thành một mảng các khối dữ liệu nhằm tìm giá trị mong muốn.

Thông thường, hàm băm lấy chuỗi ký tự làm đầu vào và xuất ra một giá trị số. Đối với cùng một đầu vào, hàm băm sẽ trả về cùng một số. Nếu hai đầu vào khác nhau được băm cho cùng một kết quả thì sẽ xảy ra xung đột. Mục tiêu là có càng ít trường hợp như vậy càng tốt.

Vì vậy, khi bạn nhập cặp khóa/giá trị vào bảng băm, khóa sẽ được chuyển qua hàm băm và chuyển thành một số. Số này sau đó được sử dụng làm khóa thực tế tương ứng với một giá trị cụ thể. Khi bạn nhập lại cùng một khóa, hàm băm sẽ xử lý nó và trả về kết quả số tương tự. Kết quả này sau đó sẽ được sử dụng để tìm giá trị liên quan. Cách tiếp cận này làm giảm đáng kể thời gian tìm kiếm trung bình.

Độ phức tạp về thời gian của bảng băm ════════ ═╗ ║ Thuật toán ║Trung bình ║ Trường hợp xấu nhất ║ ╠═══════════╬══════ ═══════ ═══ ═╬════════ ═══════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(1) ║ O(n) ║ ║ Chèn ║ O(1) ║ O(n) ║ ║ Xóa ║ O(1) ║ O(n) ║ ╚═══════════╩══════════════ ═══╩════ ═════ ══════╝

Các bài tập từ freeCodeCamp

Cây tìm kiếm nhị phân


Cây tìm kiếm nhị phân

Cây là một cấu trúc dữ liệu bao gồm các nút. Nó có các tính chất sau:

  • Mỗi cây đều có một nút gốc (trên cùng).
  • Một nút gốc có 0 hoặc nhiều nút con.
  • Mỗi nút con có 0 hoặc nhiều nút con, v.v.
Cây tìm kiếm nhị phân có hai thuộc tính bổ sung:
  • Mỗi nút có tối đa hai nút con (con cháu).
  • Mỗi nút nhỏ hơn các nút con của nó ở bên phải và các nút con của nó ở bên trái nhỏ hơn chính nó.
Cây tìm kiếm nhị phân cho phép bạn nhanh chóng tìm, thêm và xóa các phần tử. Chúng được thiết kế sao cho thời gian của mỗi thao tác tỷ lệ thuận với logarit của tổng số phần tử trong cây.

Độ phức tạp về thời gian của cây tìm kiếm nhị phân ═══════ ╗ ║ Thuật toán ║Giá trị trung bình ║Trường hợp xấu nhất ║ ╠═══════════╬═══════ ══════ ════ ╬═════════ ═════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(log n) ║ O(n) ║ ║ Chèn ║ O(log n) ║ O(n) ║ ║ Xóa ║ O(log n) ║ O(n) ║ ╚═══════════╩════════════ ═════╩════ ════ ══════╝


Các bài tập từ freeCodeCamp

Cây tiền tố

Cây tiền tố (được tải) là một loại cây tìm kiếm. Nó lưu trữ dữ liệu dưới dạng nhãn, mỗi nhãn đại diện cho một nút trong cây. Các cấu trúc như vậy thường được sử dụng để lưu trữ các từ và thực hiện tìm kiếm nhanh trên chúng - ví dụ: đối với chức năng tự động hoàn thành.

Đây là cách cây tiền tố hoạt động

Mỗi nút trong cây tiền tố ngôn ngữ chứa một chữ cái của từ. Để tạo thành một từ, bạn cần đi theo các cành cây, chuyển từng chữ cái một. Cây bắt đầu phân nhánh khi thứ tự các chữ cái khác với các từ khác trong đó hoặc khi từ kết thúc. Mỗi nút chứa một chữ cái (dữ liệu) và một giá trị Boolean cho biết liệu đó có phải là chữ cái cuối cùng trong từ hay không.

Nhìn vào hình minh họa và cố gắng tạo thành các từ. Luôn bắt đầu với nút gốc ở trên cùng và thực hiện theo cách của bạn. Cây này chứa các từ sau: bóng, dơi, búp bê, do, dork, ký túc xá, gửi, giác quan.

Các bài tập từ freeCodeCamp

Đống nhị phân

Đống nhị phân là một cấu trúc dữ liệu dựa trên cây khác. Mỗi nút trong đó có không quá hai nút con. Nó cũng là một cây hoàn hảo: điều này có nghĩa là tất cả các cấp độ trong đó đều chứa đầy dữ liệu và cấp độ cuối cùng được điền từ trái sang phải.


Đây là cách hoạt động của đống tối thiểu và tối đa

Một đống nhị phân có thể là tối thiểu hoặc tối đa. Trong một đống tối đa, khóa của bất kỳ nút nào luôn lớn hơn hoặc bằng khóa của các nút con của nó. Trong một đống tối thiểu, mọi thứ hoạt động theo cách khác: khóa của bất kỳ nút nào nhỏ hơn hoặc bằng khóa của nút con cháu của nó.

Thứ tự các cấp trong đống nhị phân rất quan trọng, trái ngược với thứ tự của các nút trong cùng một cấp. Hình minh họa cho thấy trong heap tối thiểu ở cấp độ thứ ba, các giá trị không theo thứ tự: 10, 6 và 12.


Độ phức tạp về thời gian của heap nhị phân ════════ ═╗ ║ Thuật toán ║ Trung bình ║ Trường hợp xấu nhất ║ ╠═══════════╬═══════ ═══════ ══ ══╬═══════ ════════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(n) ║ O(n) ║ ║ Chèn ║ O(1) ║ O(log n) ║ ║ Xóa ║ O(log n) ║ O(log n) ║ ║ Peek ║ O(1) ║ O(1) ║ ╚══════════ ═╩══════════ ════════╩═══════════════╝

Các bài tập từ freeCodeCamp

đồ thị

Đồ thị là tập hợp các nút (đỉnh) và các kết nối giữa chúng (các cạnh). Chúng còn được gọi là mạng.

Đồ thị được chia thành hai loại chính: có hướng và vô hướng. Trong đồ thị vô hướng, các cạnh giữa các nút không có hướng, trong khi các cạnh trong đồ thị có hướng thì có.

Thông thường, đồ thị được mô tả theo một trong hai dạng: nó có thể là danh sách kề hoặc ma trận kề.


Đồ thị dưới dạng ma trận kề

Danh sách kề có thể được coi là danh sách các phần tử, với một nút ở bên trái và tất cả các nút khác mà nó kết nối ở bên phải.

Ma trận kề là một lưới các số trong đó mỗi hàng hoặc cột tương ứng với một nút khác nhau trong biểu đồ. Tại giao điểm của hàng và cột có một số cho biết sự hiện diện của kết nối. Số không có nghĩa là nó bị thiếu; đơn vị - rằng có một kết nối. Để biểu thị trọng số của mỗi kết nối, các số lớn hơn một được sử dụng.

Có các thuật toán đặc biệt để xem các cạnh và đỉnh trong đồ thị - được gọi là thuật toán truyền tải. Các loại chính của chúng bao gồm tìm kiếm theo chiều rộng ( tìm kiếm theo chiều rộng) và chuyên sâu ( tìm kiếm theo chiều sâu). Ngoài ra, chúng có thể được sử dụng để xác định mức độ gần của các đỉnh nhất định của đồ thị với nút gốc. Video bên dưới cho biết cách thực hiện tìm kiếm theo chiều rộng trong JavaScript.

Điều kiện cần để xây dựng thuật toán là chính thức hóa dữ liệu, I E. giảm thông tin cho một số mô hình thông tin(cm. " Mô hình thông tin"), đã được mô tả và nghiên cứu. Khi một mô hình như vậy được tìm thấy, nó được cho là đã được xác định cấu trúc dữ liệu trừu tượng.

Cấu trúc dữ liệu trừu tượng mô tả các đặc điểm và tính chất của một đối tượng, mối quan hệ giữa các phần tử đối tượng, tốt nhất có thể hoạt động trên một đối tượng hoặc lớp đối tượng nhất định.

Một trong những nhiệm vụ của khoa học máy tính là tìm ra các dạng biểu diễn thông tin thuận tiện cho việc xử lý của máy tính. Khoa học máy tính với tư cách là một ngành khoa học chính xác hoạt động với các đối tượng hình thức (được mô tả chặt chẽ về mặt toán học). Những đối tượng như vậy - cơ bản cấu trúc dữ liệu trừu tượngđược sử dụng trong khoa học máy tính là:

· số nguyên;

· số thực;

· biểu tượng;

· giá trị logic.

Để máy tính xử lý các đối tượng này bằng ngôn ngữ lập trình, có các phương pháp thích hợp Loại dữ liệu(cm. " Loại dữ liệu"). Các đối tượng cơ bản có thể được kết hợp thành các cấu trúc phức tạp hơn bằng cách thêm các thao tác trên toàn bộ cấu trúc và truy cập các quy tắc vào các thành phần riêng lẻ của cấu trúc dữ liệu trừu tượng này.

Các cấu trúc dữ liệu trừu tượng này bao gồm:

· vectơ (mảng hữu hạn);

· bảng (ma trận) và trong trường hợp chung - mảng đa chiều;

· Cấu trúc động:

Chuỗi ký hiệu, số;

Hàng đợi;

Cây;

Lựa chọn thành công cấu trúc dữ liệu thường là chìa khóa để tạo ra một thuật toán hiệu quả và một chương trình triển khai nó: bằng cách sử dụng sự tương tự giữa cấu trúc dữ liệu và đối tượng thực, bạn có thể tìm ra giải pháp hiệu quả cho các vấn đề.

Lưu ý rằng các cấu trúc được liệt kê tồn tại bất kể việc triển khai chúng trong quá trình lập trình như thế nào. Họ đã làm việc với những cấu trúc dữ liệu này vào cả thế kỷ 18 và 19, khi máy tính vẫn chưa được phát minh. Chúng ta có thể phát triển một thuật toán theo cấu trúc dữ liệu trừu tượng, nhưng để triển khai thuật toán bằng một ngôn ngữ lập trình cụ thể, chúng ta cần tìm cách biểu diễn nó theo các thuật ngữ Loại dữ liệu Và toán tửđược hỗ trợ bởi ngôn ngữ lập trình này (xem “ Toán tử ngôn ngữ lập trình"). Để biểu diễn các cấu trúc trừu tượng trên máy tính, chúng ta sử dụng cấu trúc dữ liệu, là một tập hợp các biến, có thể thuộc các kiểu dữ liệu khác nhau, được kết hợp theo một cách nhất định. Để xây dựng các cấu trúc như vector, bảng, chuỗi, dãy, hầu hết các ngôn ngữ lập trình đều có chuẩn Loại dữ liệu: mảng một chiều, mảng hai chiều, chuỗi, tệp (ít thường xuyên hơn là danh sách), tương ứng. Tổ chức các cấu trúc dữ liệu khác, trước hết cấu trúc động, kích thước của nó thay đổi trong quá trình thực hiện chương trình, người lập trình phải thực hiện độc lập, sử dụng các kiểu dữ liệu cơ bản. Chúng ta hãy xem xét các cấu trúc như vậy chi tiết hơn.

Danh sách

Danh sách tuyến tính- một chuỗi các phần tử có liên quan tuyến tính trong đó cho phép thực hiện các thao tác thêm phần tử vào một vị trí tùy ý trong danh sách và xóa bất kỳ phần tử nào. Danh sách tuyến tính được xác định duy nhất bằng con trỏ tới đầu danh sách. Các thao tác điển hình trên danh sách là: duyệt qua danh sách, tìm kiếm phần tử đã cho, chèn phần tử ngay sau hoặc trước phần tử cụ thể, xóa phần tử đã cho, hợp nhất hai danh sách thành một, chia một danh sách thành hai hoặc nhiều danh sách, v.v.

Trong danh sách tuyến tính cho mọi phần tử ngoại trừ Đầu tiên, Có trước yếu tố; cho mọi phần tử ngoại trừ cuối cùng, Có Kế tiếp yếu tố. Vì vậy, tất cả các phần tử của danh sách đều được sắp xếp. Tuy nhiên, việc xử lý danh sách liên kết đơn tuyến tính không phải lúc nào cũng thuận tiện, bởi vì không có khả năng di chuyển theo hướng ngược lại - từ cuối danh sách đến đầu. Trong danh sách tuyến tính, bạn chỉ có thể duyệt qua tất cả các phần tử bằng cách di chuyển tuần tự từ phần tử hiện tại sang phần tử tiếp theo, bắt đầu từ phần tử đầu tiên, truy cập trực tiếp vào Tôi phần tử thứ là không thể.

Ví dụ 1. Thứ tự ghi tên người đọc trong máy tính của thủ thư xác định mối quan hệ “trước-tiếp”. Theo quy định, bản thân các bản ghi có một thuộc tính bổ sung - chúng được sắp xếp theo thứ tự bảng chữ cái. Các thao tác thêm đầu đọc mới và nếu cần, xóa đầu đọc cũ được thực hiện trong danh sách này. Ngoài ra, nếu hồ sơ về các cuốn sách được phát hành cho mỗi người đọc được lưu giữ thì sẽ thuận tiện hơn khi trình bày từng hồ sơ đó bằng cách sử dụng danh sách các cuốn sách được phát hành.

Danh sách đổ chuông- cấu trúc giống như danh sách tuyến tính, nhưng có thêm kết nối giữa phần tử cuối cùng và phần tử đầu tiên, nghĩa là phần tử tiếp theo sau phần tử cuối cùng là phần tử đầu tiên.

Trong danh sách vòng trái ngược với danh sách tuyến tính tất cả các phần tử đều bằng nhau(vì đối với mỗi phần tử, cả phần tử trước và phần tử tiếp theo đều được xác định). Việc lựa chọn các phần tử “đầu tiên” và “cuối cùng” trong danh sách vòng là rất tùy tiện, vì trên thực tế cấu trúc danh sách không có phần tử được phân bổ rõ ràng!

Ví dụ 2. Trong nhiều trò chơi, trẻ sử dụng quầy để chọn người lãnh đạo, chia thành các đội, v.v. Theo quy định, các quầy đếm dài và trẻ em (không tự biết) sắp xếp một danh sách vòng tròn. Mối quan hệ “trước-sau” được xác định theo hướng mà người lãnh đạo đang tính đến. Một hoạt động điển hình trong cấu trúc như vậy là loại bỏ một phần tử khỏi danh sách trong khi vẫn duy trì cấu trúc vòng tròn của nó.

Danh sách tuyến tính, trong đó các thao tác chèn, xóa và truy cập vào các giá trị phần tử chỉ được thực hiện trên các phần tử ngoài cùng (đầu tiên hoặc cuối cùng), đã nhận được các tên đặc biệt.

Cây rơm- trường hợp đặc biệt của danh sách liên kết đơn tuyến tính trong đó hai thao tác được xác định: thêm một phần tử vào đầu ngăn xếp (trước phần tử đầu tiên) và xóa một phần tử khỏi đầu ngăn xếp (loại bỏ phần tử đầu tiên).

Ví dụ 3. Chúng ta hãy xem xét vấn đề xác định sự cân bằng của các loại dấu ngoặc đơn khác nhau trong một biểu thức số học. Ví dụ: bạn muốn phân tích xem dấu ngoặc đơn trong biểu thức chứa dấu ngoặc đơn và dấu ngoặc vuông có cân bằng hay không: ? Để giải quyết vấn đề này chúng ta sẽ sử dụng cấu trúc động dữ liệu cây rơm. Hãy để chúng tôi trình bày một thuật toán để giải quyết vấn đề này từng bước. Chúng ta sẽ sử dụng ký hiệu sau:

Tôi- số ký hiệu được phân tích;

N- số ký tự trong biểu thức.

1. Tôi = 0.

2. Tôi = Tôi + 1.

3. Nếu TôiN, sau đó chuyển sang bước (4), ngược lại nếu ngăn xếp trống thì hiển thị thông báo “ngoặc được cân bằng”, ngược lại hiển thị thông báo “ dấu ngoặc không cân bằng" Kết thúc thuật toán.

4. Nếu Tôi Ký hiệu thứ khác với ký hiệu ngoặc, sau đó chuyển sang bước (2).

5. Nếu Tôi Ký hiệu thứ bằng “(” hoặc “[”, thì ta bỏ vào ngăn xếp, chuyển sang bước (2).

6. Nếu Tôi Ký hiệu thứ là “)”, thì ta kiểm tra phần trên cùng của ngăn xếp: nếu có dấu “(” ở đầu ngăn xếp thì ta loại bỏ khỏi ngăn xếp; chuyển sang bước (2), nếu không thì hiển thị thông báo “ dấu ngoặc không cân bằng" Kết thúc thuật toán.

7. Nếu Tôi Ký tự thứ là “]”, thì ta kiểm tra phần trên cùng của ngăn xếp: nếu có “[” ở đầu ngăn xếp thì ta xóa nó ra khỏi ngăn xếp; chuyển sang bước (2), nếu không hiển thị thông báo “ dấu ngoặc không cân bằng" Kết thúc thuật toán.

Xếp hàng- trường hợp đặc biệt của danh sách liên kết đơn tuyến tính mà chỉ được phép thực hiện hai thao tác: thêm một phần tử vào cuối (đuôi) của hàng đợi và xóa một phần tử khỏi đầu (đầu) của hàng đợi.

Khái niệm hàng đợi thực sự rất gần với thuật ngữ “hàng đợi” hàng ngày. Hàng đợi khách hàng trong cửa hàng được mô tả rõ ràng dưới dạng cấu trúc dữ liệu này.

Cây

Cây là tập hợp các phần tử được gọi là điểm giao, trong đó một phần tử được chọn ( nguồn gốc), và các phần tử còn lại được chia thành các tập rời nhau (cây con), mỗi tập là một cây và gốc của mỗi cây con là hậu duệ gốc của cây, tức là tất cả các phần tử được kết nối với nhau bằng một mối quan hệ (tổ tiên-hậu duệ). Kết quả là một cấu trúc phân cấp của các nút được hình thành. Các nút không có con nào được gọi là lá. Các thao tác sau được xác định trên cây: thêm một phần tử vào cây, xóa một phần tử khỏi cây, duyệt cây, tìm kiếm một phần tử trong cây.

Ví dụ 4. Cây là cấu trúc dữ liệu thuận tiện nhất để biểu diễn cây gia phả, có thể được sử dụng để giải quyết các vấn đề xác định mức độ quan hệ giữa hai người.

Cây còn được dùng để xác định chiến lược giành chiến thắng trong trò chơi (xem bài “ Trò chơi. Chiến lược chiến thắng") và để xây dựng các mô hình thông tin khác nhau (xem " Mô hình thông tin”).

Một vai trò đặc biệt quan trọng trong khoa học máy tính được thực hiện bởi cái gọi là cây nhị phân.

Cây nhị phân- một trường hợp đặc biệt của cây trong đó mỗi nút không thể có nhiều hơn hai con cháu, đó là các gốc của cây con trái và cây con phải.

Ngoài ra, nếu điều kiện đối với các nút cây được thỏa mãn là tất cả các giá trị của các phần tử của cây con bên trái nhỏ hơn giá trị của gốc của cây và tất cả các giá trị của các phần tử của cây con bên phải đều bằng lớn hơn giá trị của gốc thì cây đó được gọi là cây tìm kiếm nhị phân và được thiết kế để nhanh chóng tìm kiếm các phần tử. Thuật toán tìm kiếm trong cây như vậy hoạt động như sau: giá trị tìm kiếm được so sánh với giá trị gốc của cây và tùy thuộc vào kết quả so sánh, việc tìm kiếm sẽ kết thúc hoặc chỉ tiếp tục ở bên trái hoặc chỉ ở bên phải. cây con tương ứng. Tổng số thao tác so sánh sẽ không vượt quá cái gọi là chiều cao cây- số phần tử tối đa trên đường đi từ gốc đến một trong các lá. Vậy chiều cao của cây trong hình là 4.

Đồ thị

đồ thị là một tập hợp các phần tử được gọi là đỉnh caođồ thị cùng với một tập hợp các mối quan hệ giữa các đỉnh này, được gọi là xương sườnđồ thị. Giải thích đồ họa của cấu trúc dữ liệu này là một tập hợp các điểm tương ứng với các đỉnh, một số cặp được kết nối bằng các đường hoặc mũi tên tương ứng với các cạnh. Trong trường hợp sau, đồ thị được gọi là định hướng(xem thêm bài viết “ Mô hình đồ họa" Và " Mô hình dạng bảng”).

Do các đối tượng có cấu trúc tùy ý có thể được mô tả bằng đồ thị nên đồ thị là phương tiện chính để mô tả cấu trúc của các đối tượng phức tạp và hoạt động của hệ thống. Ví dụ: để mô tả mạng máy tính, hệ thống giao thông, cấu trúc phân cấp (cây là một trong các loại biểu đồ). Lưu đồ thuật toán (xem “ Cách viết thuật toán”) cũng là đồ thị.

Nếu mỗi cạnh cũng được gán một số nhất định ( cân nặng), thì đồ thị như vậy được gọi là có trọng lượng. Ví dụ: khi mô tả hệ thống đường bộ của Nga bằng biểu đồ, độ dài của con đường (trọng lượng của cạnh biểu đồ) kết nối các khu dân cư nhất định (đỉnh của biểu đồ) là quan trọng. Hơn nữa, trong hình, độ dài của các cạnh tương ứng không nhất thiết phải tương ứng với trọng số được gán cho chúng, không giống như bản đồ đường đi.

Ví dụ 5. Thật thuận tiện khi giải quyết vấn đề sau đây bằng đồ thị có trọng số. Chính phủ Nga đang lên kế hoạch xây dựng những tuyến đường cao tốc hiện đại nối các thành phố có dân số hơn một triệu người. Nên xây dựng loại đường nào để từ bất kỳ thành phố nào như vậy người ta có thể đến bất kỳ thành phố nào khác bằng đường cao tốc mới và tổng chiều dài của các con đường sẽ là tối thiểu?

Bài toán này trong lý thuyết đồ thị có lời giải đơn giản và chính xác. Chúng ta có thể bắt đầu quy hoạch mạng lưới đường bộ, bắt đầu từ bất kỳ thành phố nào, chẳng hạn như St. Petersburg. Hãy kết nối nó với thành phố hơn một triệu người gần nhất. Sau đó, ở mỗi bước, con đường ngắn nhất sẽ được thêm vào mạng hiện có, con đường này có thể kết nối một thành phố chưa được kết nối với mạng với một trong những thành phố đã có trong mạng. Do đó, số đường sẽ ít hơn số thành phố một đường.

Cấu trúc dữ liệu trừu tượng - biểu đồ - có thể được biểu diễn trong chương trình theo nhiều cách, tức là. sử dụng các kiểu dữ liệu khác nhau. Ví dụ: một đồ thị có thể được mô tả bằng cách sử dụng danh sách các cạnh, xác định mỗi cạnh bằng một cặp đỉnh và, tùy chọn, một trọng số. Việc lưu trữ biểu đồ dạng bảng đã trở nên phổ biến nhất (xem “ Mô hình dạng bảng"), còn được gọi là ma trận kề, I E. một mảng hai chiều, nói MỘT, trong đó đối với đồ thị không có trọng số (hoặc 1), nếu cạnh giữa các đỉnh Tôi Và j tồn tại và (hoặc 0) nếu ngược lại. Đối với đồ thị có trọng số MỘT[Tôi][j] bằng trọng số của cạnh tương ứng, và sự vắng mặt của cạnh trong một số bài toán được biểu thị thuận tiện bằng vô cực. Đối với đồ thị vô hướng, ma trận kề luôn đối xứng qua đường chéo chính ( Tôi = j). Sử dụng ma trận kề, dễ dàng kiểm tra xem có cạnh nào trong đồ thị nối một đỉnh hay không Tôi với đầu j. Nhược điểm chính của nó là ma trận kề đòi hỏi lượng bộ nhớ đủ để lưu trữ N 2 giá trị cho đồ thị chứa N các đỉnh, ngay cả khi có ít cạnh hơn đáng kể trong đồ thị so với N 2 .

Khi giải thích khái niệm cấu trúc dữ liệu Bạn có thể sử dụng hình minh họa sau.

Khi giải quyết bất kỳ vấn đề nào cũng cần có sự hợp tác dữ liệu và thực hiện các thao tác trên chúng. Nói chung, tập hợp các thao tác này cho từng nhiệm vụ là khác nhau. Tuy nhiên, nếu một tập hợp các thao tác nhất định thường được sử dụng để giải quyết các vấn đề khác nhau thì sẽ rất hữu ích nếu bạn tìm ra cách tổ chức dữ liệu cho phép bạn thực hiện các thao tác cụ thể này một cách hiệu quả nhất có thể. Sau khi một phương pháp như vậy được phát minh, khi giải quyết một vấn đề cụ thể, chúng ta có thể giả sử rằng chúng ta có một “hộp đen” (chúng ta sẽ gọi nó là cấu trúc dữ liệu), mà người ta biết rằng một loại dữ liệu nào đó được lưu trữ trong đó, và có thể thực hiện một số thao tác trên dữ liệu này. Điều này cho phép bạn thoát khỏi các chi tiết và tập trung vào các tính năng cụ thể của nhiệm vụ. Bên trong (tức là trong máy tính) “hộp đen” này có thể được triển khai theo nhiều cách khác nhau, nhưng người ta nên cố gắng triển khai hiệu quả nhất (nhanh và tiết kiệm bộ nhớ) nhất có thể.

Tiêu chuẩn giáo dục của tiểu bang quy định việc nghiên cứu các cấu trúc dữ liệu khác nhau cả trong khóa học cơ bản của trường tiểu học và trung học. Trong khóa học lập trình cơ bản ở trường, Chương trình mẫu đề cập đến chuỗi ký tự (chuỗi), số, danh sách, cây và đồ thị dưới dạng đối tượng được xử lý. Tuy nhiên, trong các công trình thực tế chỉ đề cập đến mảng từ dữ liệu có cấu trúc phức tạp (xem bài “ Hoạt động mảng"). Ở trường cơ bản, rõ ràng việc nghiên cứu các cấu trúc còn lại trước hết là hợp lý khi xây dựng các mô hình đồ họa và các mô hình khác (xem phần IV của bộ bách khoa toàn thư).

Một chương trình gần đúng dành cho một trường chuyên biệt bao gồm việc làm việc với các con số, ma trận, chuỗi, danh sách và cây. Như một minh họa đơn giản khi làm việc với danh sách, bạn có thể chọn sắp xếp ngăn xếp bằng cách sử dụng mảng một chiều và một biến số nguyên trỏ đến đỉnh ngăn xếp (“phần dưới cùng” của ngăn xếp luôn nằm ở phần tử đầu tiên của mảng ). Ngoài bài toán kiểm tra dấu ngoặc đơn để cân bằng được đưa ra trong bài, các bạn có thể nghiên cứu hoạt động của máy tính ngăn xếp bằng ví dụ về thuật toán chuyển biểu thức số học sang ký hiệu Ba Lan ngược ( hậu tố ghi âm) từ cái mà chúng ta đã quen thêm vào ghi và tính toán thêm giá trị của một biểu thức số học.

Cây nhị phân cũng có thể được biểu diễn dễ dàng trong bộ nhớ máy tính bằng mảng một chiều, với phần tử đầu tiên của mảng lưu trữ gốc của cây và con cháu của nút cây được lưu trữ trong Tôi-phần tử thứ của mảng sẽ nằm ở vị trí thứ 2 Tôi-m và (2 Tôi+1) phần tử thứ tương ứng. Nếu một nút không có phần tử con thì phần tử tương ứng sẽ bằng, ví dụ: 0. Thủ tục duyệt cây đệ quy t và in các phần tử của nó trong trường hợp này sẽ trông như thế này:

thứ tự thủ tục(i:số nguyên);

nếu như t[i]<> 0 sau đó

Bạn có thể đọc về cách triển khai danh sách và mảng bằng cách sử dụng các biến động, chẳng hạn như trong cuốn sách cổ điển của N. Wirth “Thuật toán và cấu trúc dữ liệu”.

Chương trình dành cho trường chuyên cũng bao gồm các thuật toán đồ thị. Đặc biệt, việc tìm kiếm đường đi ngắn nhất trong đồ thị được đề cập. Đối với đồ thị không có trọng số, vấn đề này có thể được giải quyết, ví dụ: bằng cách sử dụng thuật toán "tìm kiếm theo chiều rộng", khi đầu tiên các đỉnh của đồ thị được kết nối bởi một cạnh với đỉnh ban đầu được đánh dấu, sau đó tất cả các đỉnh được kết nối với các đỉnh được đánh dấu, v.v. . Đối với biểu đồ có trọng số, thuật toán Dijkstra thường được sử dụng nhiều nhất (ví dụ: xem bài viết của E.V. Andreeva “Olympiads in Informatics. Paths to the Top”, “Informatics” số 8/2002). Kiến thức về các thuật toán như vậy là cần thiết để giải thành công các bài toán Olympic về khoa học máy tính. Vì vậy, ở giai đoạn cấp quận liên bang IV của Olympic Tin học toàn Nga năm 2007, bài toán “Rãnh và rãnh” đã được đề xuất, giải pháp của bài toán này là tìm đường đi ngắn nhất trong biểu đồ có trọng số.

Khái niệm về mô hình dữ liệu

Mô hình dữ liệu

Mô hình dữ liệu là một công cụ để lập mô hình một lĩnh vực chủ đề tùy ý.

Mô hình dữ liệu là một bộ quy tắc để tạo cấu trúc dữ liệu trong cơ sở dữ liệu, các thao tác trên chúng, cũng như các ràng buộc toàn vẹn xác định các kết nối và giá trị dữ liệu được phép cũng như trình tự thay đổi của chúng. Vì vậy, mô hình dữ liệu bao gồm ba phần:

  1. Một tập hợp các kiểu cấu trúc dữ liệu.

Ở đây chúng ta có thể rút ra sự tương tự với các ngôn ngữ lập trình, cũng có các kiểu cấu trúc dữ liệu được xác định trước, chẳng hạn như dữ liệu vô hướng, vectơ, mảng, cấu trúc (ví dụ: kiểu cấu trúc bằng ngôn ngữ C), v.v.

  1. Một tập hợp các toán tử hoặc quy tắc suy luận có thể được áp dụng cho bất kỳ ví dụ hợp lệ nào về các loại dữ liệu được liệt kê trong (1) để tìm, suy ra hoặc chuyển đổi thông tin chứa trong bất kỳ phần nào của các cấu trúc này theo bất kỳ kết hợp nào.

Các hoạt động đó là: tạo và sửa đổi cấu trúc dữ liệu, nhập dữ liệu mới, xóa và sửa đổi dữ liệu hiện có, tìm kiếm dữ liệu trong các điều kiện khác nhau.

  1. Một tập hợp các quy tắc toàn vẹn chung trực tiếp hoặc gián tiếp xác định tập hợp các trạng thái nhất quán của cơ sở dữ liệu và/hoặc tập hợp các thay đổi đối với trạng thái của nó.

Quy tắc toàn vẹn được xác định bởi loại dữ liệu và vùng chủ đề. Ví dụ: giá trị thuộc tính Quầy tính tiền là một số nguyên, tức là chỉ có thể bao gồm các số. Và giới hạn của lĩnh vực môn học là con số này không thể nhỏ hơn 0.

Bây giờ chúng ta hãy xem xét kỹ hơn các bộ tạo nên mô hình dữ liệu.

Cấu trúc dữ liệu dựa trên việc sử dụng các khái niệm “tổng hợp” và “tổng quát hóa”. Một trong những lựa chọn đầu tiên về cấu trúc dữ liệu đã được Hiệp hội Ngôn ngữ xử lý dữ liệu (Hội thảo về ngôn ngữ hệ thống dữ liệu, CODASYL) đề xuất (Hình 2.1).

Hình 2.1 Thành phần cấu trúc dữ liệu theo phiên bản CODASYL

Phần tử dữ liệu– đơn vị dữ liệu được đặt tên nhỏ nhất mà DBMS có thể truy cập trực tiếp và với sự trợ giúp của nó, tất cả các cấu trúc khác được xây dựng. Đối với mỗi phần tử dữ liệu, loại của nó phải được xác định.

Tổng hợp- tập hợp các phần tử dữ liệu được đặt tên trong một bản ghi có thể được coi là một tổng thể duy nhất. Một tập hợp có thể đơn giản (chỉ bao gồm các phần tử dữ liệu, Hình 2.2, a) và hỗn hợp (bao gồm, cùng với các phần tử dữ liệu, các tập hợp khác, Hình 2.2, b).

Hình 2.2 Ví dụ về đơn vị: a) đơn vị đơn giản và b) đơn vị phức hợp

Ghi– một tập hợp được đặt tên của các phần tử dữ liệu hoặc các phần tử dữ liệu và tập hợp. Bản ghi là một tập hợp không phải là một phần của bất kỳ tập hợp nào khác; nó có thể có cấu trúc phân cấp phức tạp vì việc tổng hợp có thể được áp dụng nhiều lần. Sự khác biệt được tạo ra giữa loại bản ghi (cấu trúc của nó) và phiên bản bản ghi, tức là một bản ghi với các giá trị phần tử dữ liệu cụ thể. Một bản ghi mô tả các thuộc tính của một thực thể phần mềm (ví dụ). Đôi khi thuật ngữ "bản ghi" được thay thế bằng thuật ngữ "nhóm".


Một ví dụ về bản ghi chứa thông tin về một nhân viên được hiển thị trong Hình 2. 2.3.

Hình 2.3 Ví dụ về một mục nhập kiểu NGƯỜI LAO ĐỘNG

Bản ghi này có một số thành phần dữ liệu ( Mã số, Chức vụ, Giới tính v.v.) và ba đơn vị: đơn vị đơn giản Họ và tên Và Địa chỉ và tổng hợp lặp lại Những cái điện thoại . (Một tổng hợp lặp lại có thể được đưa vào bản ghi với số lần bất kỳ.)

Trong số các thành phần dữ liệu (trường bản ghi), một hoặc nhiều khóa lĩnh vực. Các giá trị trường chính cho phép bạn phân loại thực thể chứa một bản ghi cụ thể. Các khóa có giá trị duy nhất được gọi tiềm năng. Mỗi khóa có thể đại diện cho một tập hợp dữ liệu. Một trong các khóa được chỉ định là khóa chính, các khóa còn lại là khóa phụ. Khóa chính xác định một phiên bản của bản ghi, giá trị của nó phải là duy nhất và bắt buộc đối với các bản ghi cùng loại. Ví dụ trong hình. 2.3 khóa tiềm năng là các trường số vượt qua Và Hộ chiếu , và sẽ thích hợp hơn nếu chọn trường làm khóa chính số vượt qua , bởi vì rõ ràng nó chiếm ít bộ nhớ hơn dữ liệu hộ chiếu.

Bộ dụng cụ(hoặc thái độ nhóm) – một tập hợp các bản ghi được đặt tên tạo thành cấu trúc phân cấp hai cấp. Mỗi loại tập hợp thể hiện mối quan hệ giữa hai hoặc nhiều loại bản ghi. Đối với mỗi loại tập hợp, một loại bản ghi được khai báo là chủ sở hữu của tập hợp và các loại bản ghi còn lại được khai báo là thành viên của tập hợp. Mỗi phiên bản của một tập hợp chỉ được chứa một phiên bản của bản ghi loại chủ sở hữu và nhiều phiên bản của bản ghi loại thành viên tập hợp được liên kết với chủ sở hữu. Đối với mối quan hệ nhóm, sự phân biệt cũng được thực hiện giữa loại và thể hiện.

Thật thuận tiện khi mô tả các mối quan hệ nhóm bằng sơ đồ Bachman, được đặt theo tên của một trong những nhà phát triển mô hình dữ liệu mạng. Sơ đồ Bachmann là một đồ thị có hướng, các đỉnh tương ứng với các nhóm (loại bản ghi) và các cung tương ứng với các mối quan hệ nhóm (Hình 2.4).

Cơm. 2.4 Ví dụ về sơ đồ Bachmann cho một đoạn cơ sở dữ liệu Thành phố

Đây là một mục như PHÒNG KHÁM ĐA KHOA là chủ sở hữu của các bản ghi thuộc loại DÂN CƯ khám lâm sàng . Loại bản ghi TỔ CHỨC cũng là chủ sở hữu của hồ sơ như DÂN CƯ và chúng được kết nối bởi mối quan hệ nhóm công việc . Bản ghi thuộc loại REU và gõ DÂN CƯ là chủ sở hữu của các hồ sơ thuộc loại CĂN HỘ với các mối quan hệ tương ứng phục vụ Và cư trú tại . Do đó, một bản ghi cùng loại có thể là thành viên của một mối quan hệ và là chủ sở hữu của một mối quan hệ khác.

Cơ sở dữ liệu– một tập hợp được đặt tên của các thể hiện của nhóm và các mối quan hệ nhóm. Đây là cấp độ cao nhất của cấu trúc dữ liệu.

Ghi chú: cấu trúc dữ liệu theo CODASYL được sử dụng trong các mô hình dữ liệu mạng và phân cấp. Mô hình quan hệ áp dụng cấu trúc dữ liệu khác dựa trên lý thuyết tập hợp.

  • Dịch

Tất nhiên, bạn có thể là một lập trình viên thành công mà không cần có kiến ​​thức thiêng liêng về cấu trúc dữ liệu, nhưng chúng hoàn toàn không thể thiếu trong một số ứng dụng. Ví dụ: khi bạn cần tính toán đường đi ngắn nhất giữa hai điểm trên bản đồ hoặc tìm tên trong danh bạ điện thoại có chứa một triệu mục nhập. Chưa kể, cấu trúc dữ liệu luôn được sử dụng trong lập trình thể thao. Chúng ta hãy xem xét một số trong số họ chi tiết hơn.

Xếp hàng

Vì vậy hãy gửi lời chào tới Loopy!

Loopy thích chơi khúc côn cầu với gia đình. Và khi nói đến “trò chơi”, ý tôi là:

Khi rùa bay vào cổng, chúng sẽ bị ném lên trên cùng của chồng. Lưu ý rằng con rùa đầu tiên được thêm vào đống là người đầu tiên rời khỏi đống đó. Nó được gọi là Xếp hàng. Cũng giống như hàng đợi mà chúng ta thấy trong cuộc sống hàng ngày, phần tử đầu tiên được thêm vào danh sách là phần tử đầu tiên rời khỏi nó. Cấu trúc này còn được gọi là FIFO(Vào trước ra trước).

Còn các thao tác chèn và xóa thì sao?

Q = def Insert(elem): q.append(elem) #thêm một phần tử vào cuối hàng đợi print q def delete(): q.pop(0) #xóa phần tử 0 khỏi hàng đợi print q

Cây rơm

Sau một trận khúc côn cầu vui nhộn, Loopy làm bánh kếp cho mọi người. Cô ấy xếp chúng thành một đống.

Khi tất cả các chiếc bánh đã sẵn sàng, Loopy sẽ phục vụ từng chiếc một cho cả gia đình.

Lưu ý rằng chiếc bánh đầu tiên cô ấy làm sẽ được phục vụ sau cùng. Nó được gọi là Cây rơm. Phần tử cuối cùng được thêm vào danh sách sẽ là phần tử đầu tiên rời khỏi danh sách. Cấu trúc dữ liệu này còn được gọi là LIFO(Vào sau ra trước).

Thêm và xóa các phần tử?

S = def Push(elem): #Thêm một phần tử vào ngăn xếp - Push s.append(elem) print s def customPop(): #Xóa một phần tử khỏi ngăn xếp - Pop s.pop(len(s)-1) in s

Đống

Bạn đã bao giờ nhìn thấy một tháp mật độ chưa?

Tất cả các phần tử từ trên xuống dưới đều được đặt ở vị trí của chúng, theo mật độ của chúng. Điều gì xảy ra nếu bạn ném một vật mới vào bên trong?

Nó sẽ chiếm không gian tùy thuộc vào mật độ của nó.

Đại khái đây là cách nó hoạt động Đống.

Đống là một cây nhị phân. Điều này có nghĩa là mỗi phần tử cha có hai phần tử con. Và mặc dù chúng ta gọi cấu trúc dữ liệu này là heap nhưng nó được thể hiện thông qua một mảng thông thường.
Ngoài ra, heap luôn có chiều cao logn, trong đó n là số phần tử

Hình vẽ hiển thị vùng heap tối đa dựa trên quy tắc sau: trẻ em ít hơn cha mẹ. Ngoài ra còn có các đống min-heap, nơi trẻ em luôn có hơn cha mẹ.

Một số hàm đơn giản để làm việc với đống:

Global heap toàn cầu currSize def parent(i): #Lấy chỉ mục của phần tử cha cho phần tử thứ i return i/2 def left(i): #Lấy phần tử con bên trái của phần tử thứ i return 2*i def right (i): #Nhận đúng con của trả về thứ i (2*i + 1)

Thêm một phần tử vào vùng heap hiện có
Để bắt đầu, chúng ta thêm một phần tử vào cuối heap, tức là đến cuối mảng. Sau đó, chúng tôi hoán đổi nó với phần tử gốc cho đến khi nó khớp vào vị trí.

Thuật toán:

  1. Thêm một phần tử vào cuối heap.
  2. So sánh phần tử được thêm vào với phần tử gốc; Nếu đúng thứ tự, chúng tôi dừng lại.
  3. Nếu không, chúng ta hoán đổi các phần tử và quay lại điểm trước đó.
Mã số:

Def swap(a, b): #swap phần tử có chỉ mục a cho phần tử có chỉ mục b temp = heap[a] heap[a] = heap[b] heap[b] = temp def Insert(elem): Global currSize chỉ mục = len(heap) heap.append(elem) currSize += 1 par = parent(index) flag = 0 while flag != 1: if index == 1: #We đã đạt đến phần tử gốc flag = 1 elif heap > elem : #Nếu chỉ mục của phần tử gốc lớn hơn chỉ mục của phần tử của chúng tôi - phần tử của chúng tôi ở đúng vị trí của nó flag = 1 else: #Hoán đổi phần tử cha bằng swap(par, index) index = par par = parent(index) ) đống in
Số lần vượt qua tối đa của vòng lặp while bằng chiều cao của cây hoặc logn, do đó độ phức tạp của thuật toán là O(logn).

Truy xuất phần tử heap tối đa
Phần tử đầu tiên trong heap luôn là phần tử tối đa, vì vậy chúng ta sẽ chỉ cần xóa nó (sau khi ghi nhớ nó trước) và thay thế bằng phần tử thấp nhất. Sau đó chúng ta sẽ sắp xếp heap theo đúng thứ tự bằng cách sử dụng hàm:

MaxHeapify().

Thuật toán:

  1. Thay thế phần tử gốc bằng phần tử dưới cùng.
  2. So sánh phần tử gốc mới với phần tử con của nó. Nếu chúng theo đúng thứ tự thì dừng lại.
  3. Nếu không, hãy thay thế phần tử gốc bằng một trong các phần tử con (nhỏ hơn cho vùng heap tối thiểu, lớn hơn cho vùng heap tối đa) và lặp lại bước 2.

Def extractMax(): toàn cầu currSize if currSize != 0: maxElem = heap heap = heap #Thay thế phần tử gốc bằng phần tử cuối cùng heap.pop(currSize) #Xóa phần tử cuối cùng currSize -= 1 #Giảm kích thước heap maxHeapify( 1) return maxElem def maxHeapify(index): toàn cầu currSize lar = index l = left(index) r = right(index) #Tính toán phần tử con nào lớn hơn; nếu nó lớn hơn cái gốc, đổi chỗ nếu l<= currSize and heap[l] >đống: lar = l nếu r<= currSize and heap[r] >heap: lar = r if lar != index: swap(index, lar) maxHeapify(lar)
Một lần nữa, số lượng lệnh gọi tối đa đến hàm maxHeapify bằng với chiều cao của cây hoặc logn, có nghĩa là độ phức tạp của thuật toán là O(logn).

Chúng tôi tạo một đống từ bất kỳ mảng ngẫu nhiên nào
Được rồi, có hai cách để làm điều này. Đầu tiên là chèn từng phần tử vào heap một. Nó đơn giản, nhưng hoàn toàn không hiệu quả. Độ phức tạp của thuật toán trong trường hợp này sẽ là O(nlogn), vì hàm O(logn) sẽ được thực thi n lần.

Một cách hiệu quả hơn là sử dụng hàm maxHeapify cho ‘ đống phụ', từ (currSize/2) đến phần tử đầu tiên.

Độ phức tạp sẽ là O(n), và thật không may, bằng chứng của tuyên bố này nằm ngoài phạm vi của bài viết này. Chỉ cần hiểu rằng các phần tử trong phần currSize/2 đến currSize của vùng heap không có phần tử con và hầu hết các 'đống con' được tạo theo cách này sẽ có chiều cao nhỏ hơn chiều cao đăng nhập.

Def buildHeap(): toàn cầu currSize for i in range(currSize/2, 0, -1): #the đối số thứ ba trong range() là bước tìm kiếm, trong trường hợp này nó xác định hướng. print heap maxHeapify(i) currSize = len(heap)-1

Thực sự, tại sao tất cả điều này là?

Cần có các đống để thực hiện một kiểu sắp xếp đặc biệt được gọi là, thật kỳ lạ, “ sắp xếp đống" Không giống như “sắp xếp chèn” và “sắp xếp bong bóng” kém hiệu quả hơn với độ phức tạp O(n2) khủng khiếp, “sắp xếp đống” có độ phức tạp O(nlogn).

Việc thực hiện rất đơn giản. Chỉ cần tiếp tục lấy phần tử (gốc) tối đa từ vùng heap một cách tuần tự và ghi nó vào mảng cho đến khi vùng heap trống.

Def heapSort(): for i in range(1, len(heap)): print heap heap.insert(len(heap)-i, extractMax()) #insert phần tử lớn nhất vào cuối mảng currSize = len( đống)-1
Để tóm tắt tất cả những điều trên, tôi đã viết một vài dòng mã chứa các hàm để làm việc với heap và đối với những người hâm mộ OOP, tôi đã định dạng mọi thứ dưới dạng một lớp.

Dễ dàng phải không? Đây là lễ kỷ niệm Loopy!

Băm

Loopy muốn dạy các con mình nhận biết hình dạng và màu sắc. Để làm điều này, cô đã mang về nhà một số lượng lớn các hình vẽ đầy màu sắc.

Sau một thời gian, lũ rùa trở nên hoàn toàn bối rối

Vì vậy, cô ấy đã lấy ra một món đồ chơi khác để giúp quá trình này dễ dàng hơn một chút.

Mọi việc trở nên dễ dàng hơn nhiều vì rùa đã biết rằng các hình được sắp xếp theo hình dạng. Điều gì sẽ xảy ra nếu chúng ta dán nhãn cho mọi trụ cột?

Bây giờ rùa cần kiểm tra một cây cột có một số nhất định và chọn cây cột phù hợp từ số lượng hình nhỏ hơn nhiều. Điều gì sẽ xảy ra nếu chúng ta cũng có một trụ cột riêng cho từng sự kết hợp giữa hình dạng và màu sắc?

Giả sử số cột được tính như sau:

Họ và tên mùa hè tre quảng trường
f+i+o+t+r+e = 22+10+16+20+18+6 = Cột 92

Kra buồn ngủ thẳng Tam giác
k+p+a+p+p+i = 12+18+1+17+18+33 = Cột 99

Chúng ta biết rằng 6*33 = 198 kết hợp có thể có, nghĩa là chúng ta cần 198 cột.

Hãy gọi công thức này để tính số cột - Hàm băm.

Mã số:
def hashFunc(mảnh): Words = Piece.split(" ") #chia chuỗi thành các từ color = Words Shape = Words poleNum = 0 for i in range(0, 3): poleNum += ord(colour[i]) - 96 cựcNum += ord(shape[i]) - 96 cực trả vềNum
(với chữ Cyrillic thì phức tạp hơn một chút, nhưng tôi để nó như vậy cho đơn giản. - khoảng)

Bây giờ, nếu chúng ta tìm ra nơi lưu trữ hình vuông màu hồng, chúng ta có thể tính:
hashFunc("hình vuông màu hồng")

Đây là ví dụ về bảng băm trong đó vị trí của các phần tử được xác định bởi hàm băm.
Với cách tiếp cận này, thời gian tìm kiếm bất kỳ phần tử nào không phụ thuộc vào số lượng phần tử, tức là. O(1). Nói cách khác, thời gian tìm kiếm trong bảng băm là một giá trị không đổi.

Được rồi, nhưng giả sử chúng ta đang tìm kiếm “ xe hơi amel thẳng tam giác” (tất nhiên nếu có màu “caramel”).

HashFunc("hình chữ nhật caramel")
sẽ trả về cho chúng ta 99, đó là con số tương tự cho hình chữ nhật màu đỏ. Nó được gọi là " Va chạm" Để giải quyết xung đột chúng ta sử dụng “ Phương pháp chuỗi”, ngụ ý rằng mỗi cột lưu trữ một danh sách mà chúng tôi tìm kiếm bản ghi mà chúng tôi cần.

Vì vậy, chúng ta chỉ cần đặt hình chữ nhật kẹo lên hình màu đỏ và chọn một hình khi hàm băm trỏ đến cột đó.

Chìa khóa cho một bảng băm tốt là chọn một hàm băm thích hợp. Đây rõ ràng là điều quan trọng nhất trong việc tạo bảng băm và mọi người dành rất nhiều thời gian để phát triển các hàm băm chất lượng.
Trong các bảng tốt, không có vị trí nào chứa nhiều hơn 2-3 phần tử, nếu không, hàm băm không hoạt động tốt và bạn cần thay đổi hàm băm.

Một lần nữa, tìm kiếm không phụ thuộc vào số phần tử! Chúng ta có thể sử dụng bảng băm cho bất kỳ thứ gì có kích thước khổng lồ.

Bảng băm cũng được sử dụng để tìm chuỗi và chuỗi con trong đoạn văn bản lớn bằng thuật toán Rabin Karp hoặc thuật toán Knuth-Morris-Pratt, ví dụ, rất hữu ích trong việc xác định đạo văn trong các bài báo khoa học.

Tôi nghĩ chúng ta có thể kết thúc ở đây. Trong tương lai tôi dự định xem xét các cấu trúc dữ liệu phức tạp hơn, ví dụ: cọc Fibonacci Và Cây phân đoạn. Tôi hy vọng bạn thấy hướng dẫn không chính thức này thú vị và hữu ích.

Đã dịch cho Habr bị khóa

Điều kiện cần để lưu trữ thông tin trong bộ nhớ máy tính là khả năng chuyển đổi thông tin này sang dạng phù hợp với máy tính. Nếu điều kiện này được đáp ứng, cần phải xác định một cấu trúc phù hợp cụ thể với thông tin hiện có, một cấu trúc sẽ cung cấp tập hợp các khả năng cần thiết để làm việc với nó.

Danh sách đổ chuông

Ở đây, cấu trúc được hiểu là cách trình bày thông tin mà qua đó một tập hợp các phần tử riêng lẻ tạo thành một cái gì đó thống nhất, được xác định bởi mối quan hệ giữa chúng với nhau. Khi được sắp xếp theo các quy tắc nhất định và kết nối hợp lý với nhau, dữ liệu có thể được xử lý rất hiệu quả, vì cấu trúc chung của chúng cung cấp một tập hợp các khả năng để quản lý chúng - một trong những lý do giúp đạt được kết quả cao trong việc giải quyết một số vấn đề nhất định.

Nhưng không phải mọi đối tượng đều được biểu diễn dưới dạng tùy ý và có lẽ chỉ có một phương pháp diễn giải duy nhất cho nó, do đó, kiến ​​thức về tất cả các cấu trúc dữ liệu hiện có sẽ là một lợi thế chắc chắn cho người lập trình. Vì vậy, bạn thường phải đưa ra lựa chọn giữa các phương pháp lưu trữ thông tin khác nhau và hiệu suất của sản phẩm phụ thuộc vào sự lựa chọn này.

Nói về công nghệ phi máy tính, có thể không chỉ ra một trường hợp nào mà thông tin có cấu trúc rõ ràng. Một ví dụ điển hình là sách có nhiều nội dung khác nhau. Chúng được chia thành các trang, đoạn văn và chương và thường có mục lục, tức là giao diện để sử dụng chúng. Theo nghĩa rộng, mọi sinh vật sống đều có cấu trúc, nếu không có nó thì chất hữu cơ khó có thể tồn tại.

Có thể người đọc đã gặp trực tiếp các cấu trúc dữ liệu trong khoa học máy tính, chẳng hạn như những cấu trúc được xây dựng trong ngôn ngữ lập trình. Chúng thường được gọi là các kiểu dữ liệu. Chúng bao gồm: mảng, số, chuỗi, tệp, v.v.

Các phương pháp lưu trữ thông tin, được gọi là “đơn giản”, tức là không thể chia thành các bộ phận cấu thành, nên được nghiên cứu cùng với một ngôn ngữ lập trình cụ thể hoặc đi sâu vào bản chất công việc của chúng. Do đó, chỉ những cấu trúc “tích hợp” mới được xem xét ở đây, những cấu trúc bao gồm những cấu trúc đơn giản, cụ thể là: mảng, danh sách, cây và đồ thị.

Mảng.

Mảng là một cấu trúc dữ liệu với một tập hợp cố định và có thứ tự các phần tử (thành phần) tương tự. Việc truy cập vào bất kỳ phần tử nào của mảng được thực hiện bằng tên và số (chỉ mục) của phần tử này. Số lượng chỉ mục xác định kích thước của mảng. Ví dụ: mảng một chiều (vectơ) và hai chiều (ma trận) thường được tìm thấy nhiều nhất.

Cái trước có một chỉ mục, cái sau - hai. Đặt tên mảng một chiều là A, sau đó để truy cập vào phần tử thứ i của nó, bạn cần chỉ định tên của mảng và số phần tử được yêu cầu: A[i]. Khi A là một ma trận, nó được biểu diễn dưới dạng một bảng, các phần tử của bảng này được truy cập bằng tên của mảng, cũng như số hàng và số cột tại giao điểm của phần tử đó: A, trong đó i là số hàng, j là số cột.

Làm việc với mảng có thể khác nhau theo một số cách trong các ngôn ngữ lập trình khác nhau, nhưng các nguyên tắc cơ bản thường giống nhau ở mọi nơi. Trong ngôn ngữ Pascal, việc truy cập vào mảng một chiều và hai chiều diễn ra chính xác như được hiển thị ở trên và, ví dụ, trong C++, mảng hai chiều phải được chỉ định như sau: A[i][j]. Các phần tử mảng được đánh số thứ tự. Ngôn ngữ lập trình ảnh hưởng đến giá trị bắt đầu đánh số. Thông thường giá trị này là 0 hoặc 1.

Mảng thuộc loại được mô tả được gọi là tĩnh, nhưng cũng có những mảng khác với chúng theo một số cách nhất định: động và không đồng nhất. Tính năng động của mảng trước được đặc trưng bởi kích thước thay đổi, tức là khi chương trình thực thi, kích thước của mảng động có thể thay đổi. Chức năng này giúp làm việc với dữ liệu linh hoạt hơn, nhưng đồng thời bạn phải hy sinh hiệu suất và bản thân quá trình này trở nên phức tạp hơn.

Một tiêu chí bắt buộc đối với một mảng tĩnh, như đã nói, là tính đồng nhất của dữ liệu được lưu trữ đồng thời trong đó. Khi điều kiện này không được đáp ứng, mảng sẽ không đồng nhất. Việc sử dụng nó là do những nhược điểm tồn tại ở dạng trước, nhưng nó hợp lý trong nhiều trường hợp.

Vì vậy, ngay cả khi bạn đã quyết định cấu trúc và chọn mảng làm nó, điều này vẫn chưa đủ. Xét cho cùng, mảng chỉ là một tên gọi chung, một loại dành cho một số cách triển khai nhất định có thể có. Vì vậy, cần phải quyết định phương pháp biểu diễn cụ thể, với mảng phù hợp nhất.

Danh sách.

Danh sách là một kiểu dữ liệu trừu tượng triển khai một tập hợp các giá trị có thứ tự. Danh sách khác với mảng ở chỗ các phần tử của chúng được truy cập tuần tự, trong khi mảng là cấu trúc dữ liệu truy cập ngẫu nhiên. Kiểu trừu tượng này có một số cách triển khai dưới dạng cấu trúc dữ liệu. Một số trong số họ sẽ được thảo luận ở đây.

Danh sách (danh sách liên kết) là một cấu trúc dữ liệu là tập hợp hữu hạn các phần tử có thứ tự được kết nối với nhau thông qua con trỏ. Mỗi phần tử của cấu trúc chứa một trường có một số thông tin cũng như một con trỏ tới phần tử tiếp theo. Không giống như mảng, không có quyền truy cập ngẫu nhiên vào các phần tử của danh sách.

Danh sách liên kết đơn

Trong danh sách liên kết đơn ở trên, phần tử ban đầu là danh sách Head (tên tùy ý) và mọi thứ khác được gọi là tail. Phần đuôi của danh sách bao gồm các phần tử được chia thành hai phần: thông tin (trường thông tin) và chỉ mục (trường tiếp theo). Phần tử cuối cùng, thay vì con trỏ, chứa dấu kết thúc danh sách - nil.

Danh sách liên kết đơn không thuận tiện lắm vì từ một điểm chỉ có thể đi đến điểm tiếp theo, từ đó di chuyển về cuối. Khi, ngoài con trỏ tới phần tử tiếp theo, còn có một con trỏ tới phần tử trước đó, thì danh sách như vậy được gọi là liên kết đôi.

Danh sách liên kết đôi

Khả năng di chuyển cả tiến và lùi rất hữu ích cho một số thao tác, nhưng các con trỏ bổ sung yêu cầu nhiều bộ nhớ hơn mức cần thiết trong một danh sách liên kết đơn tương đương.

Đối với hai loại danh sách được mô tả ở trên, có một loại con được gọi là danh sách vòng. Bạn có thể tạo danh sách vòng từ danh sách liên kết đơn bằng cách chỉ thêm một con trỏ vào phần tử cuối cùng để nó tham chiếu đến phần tử đầu tiên. Và đối với một kết nối kép, cần có hai con trỏ: tới phần tử đầu tiên và phần tử cuối cùng.

Danh sách đổ chuông

Ngoài các loại cấu trúc danh sách được xem xét, còn có các cách khác để tổ chức dữ liệu bằng cách sử dụng loại “danh sách”, nhưng theo quy tắc, chúng phần lớn giống với những cách đã thảo luận, vì vậy chúng sẽ bị bỏ qua ở đây.

Ngoài sự khác biệt về kết nối, danh sách còn được chia theo phương pháp làm việc với dữ liệu. Một số phương pháp này sẽ được thảo luận dưới đây.

Cây rơm.

Cây rơm

Một ngăn xếp có đặc điểm là các phần tử của nó chỉ có thể được truy cập từ một đầu, gọi là đỉnh của ngăn xếp, hay nói cách khác: ngăn xếp là một cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO (vào sau - ra trước). Tốt hơn là mô tả cấu trúc dữ liệu này dưới dạng một danh sách dọc, ví dụ: một chồng một số thứ, để sử dụng một trong số chúng, bạn cần nâng tất cả những thứ nằm phía trên nó và bạn chỉ có thể đặt một mục ở trên cùng của ngăn xếp.

Trong danh sách liên kết đơn được hiển thị, các thao tác trên các phần tử diễn ra nghiêm ngặt ở một đầu: để đưa phần tử mong muốn vào ô thứ năm, cần phải loại trừ phần tử chiếm vị trí này. Ví dụ: nếu có 6 phần tử và một phần tử cụ thể cũng cần được chèn vào ô thứ năm thì sẽ phải loại trừ hai phần tử.

Xếp hàng.

Cấu trúc dữ liệu Hàng đợi sử dụng nguyên tắc tổ chức FIFO (First In First Out). Theo một nghĩa nào đó, phương pháp này công bằng hơn phương pháp mà ngăn xếp vận hành, bởi vì quy tắc đơn giản làm cơ sở cho việc xếp hàng thông thường ở các cửa hàng và bệnh viện khác nhau được coi là khá công bằng và chính xác đây là cơ sở của cấu trúc này. Hãy để quan sát này là một ví dụ. Nói một cách chính xác, hàng đợi là một danh sách trong đó các phần tử chỉ có thể được thêm vào cuối và chúng có thể bị xóa khỏi phía bên kia, được gọi là phần đầu của danh sách.


Xếp hàng

Tháng mười hai

Deque (hàng đợi hai đầu) là một ngăn xếp có hai đầu. Thật vậy, bất chấp cách dịch cụ thể, một bộ bài có thể được định nghĩa không chỉ là một hàng đợi hai chiều mà còn là một chồng có hai đầu. Điều này có nghĩa là loại danh sách này cho phép các phần tử được thêm vào đầu và cuối, và điều này cũng đúng đối với thao tác truy xuất.


Tháng mười hai

Cấu trúc này hoạt động đồng thời theo hai cách tổ chức dữ liệu: FIFO và LIFO. Do đó, nó có thể được quy cho một đơn vị chương trình riêng biệt thu được bằng cách tính tổng hai loại danh sách trước đó.

Đồ thị.

Nhánh toán học rời rạc liên quan đến việc nghiên cứu đồ thị được gọi là lý thuyết đồ thị. Lý thuyết đồ thị xem xét chi tiết các khái niệm, tính chất, phương pháp biểu diễn và lĩnh vực ứng dụng đã biết của các đối tượng toán học này. Chúng tôi chỉ quan tâm đến những khía cạnh quan trọng trong lập trình.

Đồ thị là tập hợp các điểm được nối với nhau bằng các đường thẳng. Các điểm được gọi là đỉnh (nút) và các đường thẳng được gọi là cạnh (cung).

Như thể hiện trong hình, có hai loại đồ thị chính: có hướng và vô hướng. Trong trường hợp đầu tiên, các cạnh được định hướng, tức là chỉ có một hướng khả dụng giữa hai đỉnh được kết nối, ví dụ: bạn có thể đi từ đỉnh 1 đến đỉnh 2, nhưng không được ngược lại. Trong đồ thị liên thông vô hướng, bạn có thể đi từ mỗi đỉnh đến từng đỉnh và ngược lại. Trường hợp đặc biệt của hai loại này là đồ thị hỗn hợp. Nó được đặc trưng bởi sự hiện diện của cả hai cạnh định hướng và không định hướng.

Bậc trong của một đỉnh là số cạnh đi vào nó, bậc ngoài là số cạnh đi ra.

Các cạnh của đồ thị không nhất thiết phải thẳng và các đỉnh được chỉ định chính xác bằng số, như trong hình. Ngoài ra, có những đồ thị mà các cạnh được gán một giá trị cụ thể, chúng được gọi là đồ thị có trọng số và giá trị này là trọng số của cạnh. Khi cả hai đầu của một cạnh trùng nhau, tức là cạnh đó rời khỏi và đi vào đỉnh F thì cạnh đó được gọi là vòng lặp.

Đồ thị được sử dụng rộng rãi trong các cấu trúc do con người tạo ra, ví dụ như trong máy tính và mạng truyền tải cũng như công nghệ web. Các phương pháp biểu diễn đặc biệt cho phép sử dụng biểu đồ trong khoa học máy tính (trong máy tính). Nổi tiếng nhất trong số đó: “Ma trận kề”, “Ma trận sự cố”, “Danh sách kề”, “Danh sách cạnh”. Hai cái đầu tiên, như tên của nó, sử dụng ma trận để biểu diễn biểu đồ và hai cái cuối cùng sử dụng danh sách.

Cây.

Cây không có thứ tự

Cây với tư cách là một đối tượng toán học là một sự trừu tượng từ các đơn vị đồng âm được tìm thấy trong tự nhiên. Sự giống nhau về cấu trúc của cây tự nhiên với các đồ thị thuộc một loại nhất định cho thấy giả định thiết lập sự tương đồng giữa chúng. Cụ thể, với các đồ thị được kết nối và đồng thời theo chu kỳ (không có chu kỳ). Cái sau về cấu trúc của chúng thực sự giống với những cái cây, nhưng có một số điểm khác biệt, chẳng hạn, người ta thường mô tả những cây toán học có gốc nằm ở trên cùng, tức là tất cả các nhánh đều “mọc” từ trên xuống dưới. Được biết, trong tự nhiên điều này hoàn toàn không xảy ra.

Vì cây về cơ bản là một biểu đồ nên nhiều định nghĩa của nó trùng khớp với biểu đồ sau hoặc tương tự về mặt trực quan. Vì vậy, nút gốc (đỉnh 6) trong cấu trúc cây là đỉnh (nút) duy nhất được đặc trưng bởi sự vắng mặt của tổ tiên, tức là không có đỉnh nào khác đề cập đến nó và từ chính nút gốc, bạn có thể tiếp cận bất kỳ nút nào hiện có. cây đỉnh, xuất phát từ tính chất kết nối của cấu trúc này. Các nút không tham chiếu đến bất kỳ nút nào khác, nói cách khác, không có nút con, được gọi là nút lá (2, 3, 9) hoặc nút cuối. Các phần tử nằm giữa nút gốc và các lá là các nút trung gian (1, 1, 7, 8). Mỗi nút cây chỉ có một nút tổ tiên hoặc nếu là nút gốc thì không có nút nào.

Cây con là một phần của cây bao gồm nút gốc và tất cả các nút con của nó. Vì vậy, ví dụ, trong hình, một trong các cây con bao gồm gốc 8 và các phần tử 2, 1, 9.

Bạn có thể thực hiện nhiều thao tác trên cây, chẳng hạn như tìm phần tử, xóa phần tử và cây con, chèn cây con, tìm nút gốc cho một số đỉnh, v.v. Một trong những thao tác quan trọng nhất là duyệt cây. Có một số phương pháp giải quyết. Phổ biến nhất trong số đó là: đường vòng đối xứng, đường vòng trực tiếp và đường vòng ngược. Trong quá trình truyền tải xuôi, các nút tổ tiên được truy cập trước các nút con cháu của chúng và trong quá trình truyền tải ngược, tình huống cũng bị đảo ngược tương ứng. Trong phép duyệt đối xứng, các cây con của cây chính được xem lần lượt.

Việc trình bày dữ liệu theo cấu trúc được xem xét sẽ có lợi nếu thông tin có hệ thống phân cấp rõ ràng. Ví dụ: làm việc với dữ liệu về giống và loài sinh học, chức danh công việc, đối tượng địa lý, v.v. đòi hỏi một cấu trúc được thể hiện theo thứ bậc, chẳng hạn như cây toán học.