Tìm hiểu Cấu trúc dữ liệu nâng cao: Cây AVL và Bảng băm (Hash Table)

Tài liệu nghiên cứu 12 các cấu trúc dữ liệu nâng cao chuong 5 cay avl hash table, tổng hợp lý thuyết và thực hành, cung cấp kiến thức chuyên sâu về .

• Đề tài: 12 Các Cấu Trúc Dữ Liệu Nâng Cao Chương 5 Cây AVL Hash Table

Mục lục chi tiết

• 3. Chương 3: Các cấu trúc dữ liệu nâng cao (Advanced Data Structures)
• 3.1. Cây nhị phân tìm kiếm cân bằng
• 3.1.1. Tổng quan về cây BST cân bằng
• 3.1.2. Cây AVL
• 3.1.2.1. Định nghĩa cây AVL
• 3.1.2.2. Cài đặt cấu trúc dữ liệu
• 3.1.2.3. Mất cân bằng khi thêm/xóa node
• 3.1.2.4. Các thuật toán điều chỉnh cây
• 3.1.2.5. Ví dụ tạo cây AVL
• 3.1.2.6. Đánh giá/so sánh
• 3.3. Bảng băm – Hash Table
• 3.3.1. Giới thiệu
• 3.3.2. Direct-address table
• 3.3.3. Bảng băm
• 3.3.4. Khai báo cấu trúc Hash Table
• 3.3.5. Xung đột địa chỉ
• 3.3.6. Hàm băm
• 3.3.7. Các phương pháp xử lý xung đột

Tóm tắt

I. Hướng dẫn toàn tập về cấu trúc dữ liệu nâng cao Cây AVL

Trong lĩnh vực cấu trúc dữ liệu và giải thuật, việc tối ưu hóa thời gian truy xuất, thêm và xóa phần tử là mục tiêu hàng đầu. Các cấu trúc cơ bản như mảng hay danh sách liên kết có thể không hiệu quả khi tập dữ liệu lớn. Cây nhị phân tìm kiếm (Binary Search Tree - BST) ra đời để cải thiện tốc độ tìm kiếm, nhưng lại đối mặt với nguy cơ suy biến thành danh sách liên kết trong trường hợp xấu nhất, khiến độ phức tạp thời gian tăng lên O(n). Để giải quyết vấn đề này, các cấu trúc cây tự cân bằng đã được phát triển. Nổi bật nhất trong số đó là Cây AVL. Được đặt tên theo hai nhà phát minh Adelson-Velskii và Landis, Cây AVL là một cây nhị phân tìm kiếm tự cân bằng đầu tiên, đảm bảo rằng chiều cao của hai cây con tại bất kỳ nút nào cũng không chênh lệch quá một. Điều này giữ cho chiều cao của cây luôn ở mức tối thiểu, xấp xỉ logarit của số nút, từ đó đảm bảo mọi thao tác tìm kiếm, chèn, xóa đều đạt hiệu suất O(log n). Bài viết này sẽ phân tích sâu về định nghĩa, nguyên tắc hoạt động thông qua các phép quay cây (tree rotation), và cách cài đặt cây AVL hiệu quả.

1.1. Định nghĩa Cây AVL và vai trò của hệ số cân bằng

Một cây AVL về cơ bản là một cây nhị phân tìm kiếm (BST) tuân thủ một điều kiện cân bằng nghiêm ngặt. Theo định nghĩa gốc của G. Adelson-Velskii và E. Landis (1962), với mọi nút p trong cây, chiều cao của cây con trái và cây con phải của p chỉ được phép chênh lệch tối đa là 1. Điều kiện này được biểu diễn bằng công thức: ∀p∈TAVL: abs(h(p->left) - h(p->right)) ≤ 1. Để kiểm soát trạng thái này, mỗi nút trong cây AVL cần lưu trữ thêm một thông tin gọi là hệ số cân bằng (balance factor). Hệ số này được tính bằng chiều cao cây con phải - chiều cao cây con trái và có thể nhận một trong ba giá trị: -1 (cây con trái cao hơn 1 đơn vị - lệch trái), 0 (hai cây con cao bằng nhau - cân bằng), hoặc +1 (cây con phải cao hơn 1 đơn vị - lệch phải). Bất cứ khi nào một thao tác thêm hoặc xóa làm cho hệ số cân bằng của một nút nào đó trở thành -2 hoặc +2, cây được xem là mất cân bằng và cần phải thực hiện các thao tác điều chỉnh để tái lập trạng thái AVL.

1.2. Kỹ thuật phép quay cây tree rotation để tái cân bằng

Cơ chế cốt lõi để duy trì tính cân bằng của cây AVL là phép quay cây (tree rotation). Đây là một thao tác cục bộ trên các nút nhằm thay đổi cấu trúc cây mà không phá vỡ thuộc tính của cây nhị phân tìm kiếm. Khi một nút bị mất cân bằng sau khi thêm hoặc xóa, cây sẽ thực hiện một hoặc hai phép quay để khôi phục lại thuộc tính AVL. Có bốn trường hợp mất cân bằng chính, dẫn đến các loại phép quay tương ứng. Trường hợp lệch trái-trái được xử lý bằng một quay phải (right rotation) đơn. Trường hợp lệch phải-phải được xử lý bằng một quay trái (left rotation) đơn. Hai trường hợp phức tạp hơn là lệch trái-phải và phải-trái, đòi hỏi quay kép (double rotation). Ví dụ, trường hợp lệch trái-phải cần một phép quay trái sau đó là một phép quay phải. Các thuật toán thêm xóa sửa trong cây AVL phải tích hợp logic kiểm tra và gọi các phép quay này sau mỗi lần thay đổi cấu trúc cây, đảm bảo cây luôn cân bằng.

1.3. Phân tích độ phức tạp thời gian O log n của Cây AVL

Ưu điểm lớn nhất của cây AVL chính là hiệu suất ổn định và có thể dự đoán được. Do cây luôn được giữ ở trạng thái gần như cân bằng hoàn toàn, chiều cao h của cây AVL với N nút không bao giờ vượt quá 1.44 * log2(N+1). Điều này có nghĩa là chiều cao của cây luôn tỉ lệ với log(N). Do đó, các thao tác cơ bản như tìm kiếm, chèn và xóa đều có độ phức tạp thời gian trong trường hợp xấu nhất là O(log n). Cụ thể, thao tác chèn hoặc xóa bao gồm hai bước: bước đầu tiên là thực hiện chèn/xóa như trên một BST thông thường (chi phí O(log n)), và bước thứ hai là đi ngược từ nút cha về gốc để cập nhật hệ số cân bằng và thực hiện các phép quay cây nếu cần. Quá trình này cũng chỉ tốn O(log n). Hiệu suất này làm cho cây AVL trở thành lựa chọn lý tưởng cho các ứng dụng yêu cầu tốc độ truy vấn nhanh và ổn định, là một chủ đề quan trọng khi ôn thi tin học và giải quyết các bài tập cấu trúc dữ liệu.

II. Thách thức của cây BST Vì sao cần cấu trúc tự cân bằng

Để hiểu rõ giá trị của cây AVL và các cấu trúc dữ liệu và giải thuật tương tự, cần phân tích những hạn chế của cây nhị phân tìm kiếm (BST) tiêu chuẩn. Về lý thuyết, một cây BST cân bằng cung cấp hiệu suất tìm kiếm trung bình là O(log n). Tuy nhiên, cấu trúc của cây BST phụ thuộc hoàn toàn vào thứ tự chèn các phần tử. Khi dữ liệu đầu vào được sắp xếp sẵn (tăng dần hoặc giảm dần), cây BST sẽ bị suy biến. Thay vì phân nhánh, cây sẽ phát triển thành một đường thẳng, giống như một danh sách liên kết. Trong kịch bản tồi tệ này, chiều cao của cây trở thành n, với n là số lượng phần tử. Do đó, chi phí cho các thao tác tìm kiếm, chèn và xóa không còn là O(log n) nữa mà tăng vọt lên O(n). Tình trạng này làm mất đi hoàn toàn lợi thế của cấu trúc cây. Các cây tự cân bằng như Cây AVL hay Cây Đỏ-Đen được sinh ra để khắc phục nhược điểm chí mạng này. Chúng chủ động duy trì cấu trúc cây ở trạng thái gần cân bằng nhất có thể sau mỗi thao tác sửa đổi, đảm bảo hiệu suất O(log n) được duy trì ổn định, bất kể thứ tự dữ liệu đầu vào.

2.1. Hiện tượng cây nhị phân tìm kiếm bị lệch và hệ quả

Một cây nhị phân tìm kiếm (BST) bị lệch xảy ra khi các nút mới liên tục được thêm vào một phía của cây. Ví dụ, nếu chèn các khóa theo thứ tự 10, 20, 30, 40, 50, mỗi khóa mới sẽ luôn lớn hơn khóa trước đó và được chèn vào cây con phải. Kết quả là một cây chỉ có các nút con phải, trông giống hệt một danh sách liên kết. Hệ quả trực tiếp là chi phí tìm kiếm một phần tử trở thành một cuộc duyệt tuần tự. Để tìm khóa 50, thuật toán phải đi qua các nút 10, 20, 30, 40. Chi phí tìm kiếm, vốn được kỳ vọng là O(log n), giờ đây trở thành O(n). Vấn đề này không chỉ ảnh hưởng đến hiệu suất tìm kiếm mà còn tác động tiêu cực đến các thao tác thêm và xóa, khiến BST trở nên không hiệu quả cho các ứng dụng trong thế giới thực nơi dữ liệu không thể được đảm bảo là ngẫu nhiên. Đây là thách thức cơ bản mà các cây tự cân bằng phải giải quyết.

2.2. So sánh chi phí tìm kiếm Cây cân bằng và cây lệch

Sự khác biệt về hiệu suất giữa một cây BST cân bằng và một cây bị lệch là rất lớn, đặc biệt với tập dữ liệu lớn. Giả sử có một triệu (1,000,000) phần tử. Trong một cây cân bằng lý tưởng, chiều cao của cây sẽ xấp xỉ log2(1,000,000), tức là khoảng 20. Điều này có nghĩa là để tìm bất kỳ phần tử nào, thuật toán chỉ cần tối đa khoảng 20 phép so sánh. Chi phí này là cực kỳ nhỏ và hiệu quả. Ngược lại, trong một cây bị lệch hoàn toàn, chiều cao của cây sẽ là 1,000,000. Trong trường hợp xấu nhất, việc tìm kiếm một phần tử có thể đòi hỏi tới 1,000,000 phép so sánh. Sự chênh lệch này cho thấy tầm quan trọng của việc duy trì tính cân bằng. Các cấu trúc như cây AVL đảm bảo rằng, dù trong trường hợp nào, số phép so sánh vẫn ở mức O(log n), mang lại hiệu suất ổn định và đáng tin cậy cho các hệ thống phần mềm, đặc biệt trong các bài toán yêu cầu lập trình C++/Java/Python hiệu năng cao.

III. Phương pháp Bảng Băm Tối ưu truy xuất dữ liệu nhanh O 1

Bên cạnh các cấu trúc dữ liệu dựa trên cây, Bảng Băm (Hash Table) là một giải pháp cực kỳ mạnh mẽ khác để quản lý và truy xuất dữ liệu. Không giống như cây AVL dựa vào việc so sánh các khóa để điều hướng, Bảng Băm hoạt động dựa trên một nguyên lý hoàn toàn khác: tính toán trực tiếp vị trí lưu trữ của một phần tử từ chính khóa (key) của nó. Ý tưởng cốt lõi là sử dụng một hàm băm (hash function) để ánh xạ một không gian khóa lớn (ví dụ: chuỗi ký tự, số nguyên lớn) vào một không gian chỉ số nhỏ hơn của một mảng. Về mặt lý tưởng, thao tác này cho phép truy cập, chèn và xóa dữ liệu với độ phức tạp thời gian trung bình là O(1), tức là gần như ngay lập tức, bất kể số lượng phần tử trong bảng. Tuy nhiên, thực tế không hoàn hảo. Vấn đề lớn nhất của Bảng Băm là đụng độ băm (hash collision), xảy ra khi hai hoặc nhiều khóa khác nhau được hàm băm ánh xạ vào cùng một vị trí. Do đó, hiệu quả của một Bảng Băm không chỉ phụ thuộc vào chất lượng của hàm băm mà còn vào chiến lược giải quyết đụng độ được áp dụng.

3.1. Nguyên lý hoạt động của Bảng Băm và vai trò hàm băm

Bảng băm (Hash Table) là một cấu trúc dữ liệu lưu trữ các cặp khóa (key) và giá trị (value). Nó sử dụng một mảng và một hàm băm (hash function). Khi cần lưu một phần tử, hàm băm sẽ lấy khóa của phần tử đó làm đầu vào và tạo ra một chỉ số (index) trong mảng. Giá trị của phần tử sau đó sẽ được lưu tại chỉ số này. Tương tự, khi cần tìm một phần tử, hàm băm sẽ được áp dụng cho khóa cần tìm để tính ra chỉ số, và sau đó truy cập trực tiếp vào vị trí đó trong mảng để lấy giá trị. Một hàm băm tốt phải đáp ứng các yêu cầu sau: tính toán nhanh, phân bố các khóa một cách đồng đều trên toàn bộ bảng để giảm thiểu đụng độ, và có tính xác định (cùng một khóa luôn cho ra cùng một chỉ số). Các phương pháp phổ biến để xây dựng hàm băm bao gồm phương pháp chia (sử dụng phép toán modulo) và phương pháp nhân.

3.2. Đụng độ băm hash collision Nguyên nhân và tác động

Đụng độ băm (hash collision) là hiện tượng không thể tránh khỏi khi sử dụng Bảng Băm. Nó xảy ra khi hàm băm tạo ra cùng một chỉ số cho hai hoặc nhiều khóa khác nhau. Nguyên nhân chính là do số lượng khóa có thể có (tập U) thường lớn hơn rất nhiều so với kích thước của bảng băm (m). Theo nguyên lý chuồng bồ câu, khi số lượng khóa cần lưu trữ vượt quá kích thước bảng, đụng độ chắc chắn sẽ xảy ra. Đụng độ làm giảm hiệu suất của Bảng Băm. Nếu không được xử lý đúng cách, việc tìm kiếm một phần tử có thể không còn là O(1) nữa. Thay vào đó, nó có thể suy biến thành việc tìm kiếm tuần tự trong một danh sách các phần tử bị đụng độ, làm tăng độ phức tạp thời gian lên O(n) trong trường hợp xấu nhất. Do đó, việc lựa chọn một phương pháp giải quyết đụng độ hiệu quả là cực kỳ quan trọng để duy trì hiệu năng của cấu trúc này.

3.3. Các phương pháp giải quyết đụng độ hiệu quả hiện nay

Có hai chiến lược chính để giải quyết đụng độ trong Bảng Băm. Phương pháp thứ nhất là Separate Chaining (nối kết riêng). Với phương pháp này, mỗi ô trong mảng băm không chỉ chứa một phần tử duy nhất mà là một con trỏ tới một cấu trúc dữ liệu khác, thường là một danh sách liên kết. Khi xảy ra đụng độ, phần tử mới sẽ được thêm vào cuối danh sách liên kết tại ô đó. Phương pháp thứ hai là Open Addressing (địa chỉ mở). Thay vì sử dụng cấu trúc dữ liệu phụ, phương pháp này sẽ tìm một ô trống khác trong chính bảng băm để lưu phần tử bị đụng độ. Có nhiều kỹ thuật để tìm ô trống, bao gồm Linear Probing (dò tuyến tính) (tìm tuần tự các ô tiếp theo), Quadratic Probing, và Double Hashing. Mỗi phương pháp có ưu và nhược điểm riêng về hiệu suất và độ phức tạp trong việc cài đặt bảng băm, và việc lựa chọn phụ thuộc vào yêu cầu cụ thể của ứng dụng.

IV. Ứng dụng thực tiễn của Cây AVL và Bảng Băm trong lập trình

Cả Cây AVL và Bảng Băm đều là những cấu trúc dữ liệu nâng cao có ứng dụng rộng rãi trong khoa học máy tính và phát triển phần mềm. Sự lựa chọn giữa chúng phụ thuộc vào yêu cầu cụ thể của bài toán, đặc biệt là sự cân bằng giữa hiệu suất truy vấn, yêu cầu về bộ nhớ và tính thứ tự của dữ liệu. Cây AVL, với khả năng duy trì dữ liệu được sắp xếp, thường được ưu tiên trong các ứng dụng cần duyệt các phần tử theo thứ tự hoặc tìm kiếm theo khoảng (range queries). Ví dụ, các hệ quản trị cơ sở dữ liệu thường sử dụng các biến thể của cây tự cân bằng như B-Tree (tương tự AVL) để đánh chỉ mục (indexing), giúp tăng tốc độ truy vấn trên các bảng dữ liệu khổng lồ. Ngược lại, Bảng Băm (Hash Table) lại tỏa sáng trong các ứng dụng yêu cầu tốc độ chèn, xóa và tìm kiếm gần như tức thời, và không quan tâm đến thứ tự của các phần tử. Nó là nền tảng cho nhiều cấu trúc dữ liệu khác như Dictionary trong Python, HashMap trong Java, hay std::unordered_map trong C++. Đây là những kiến thức không thể thiếu khi chuẩn bị cho các kỳ ôn thi tin học hoặc phỏng vấn kỹ thuật.

4.1. Khi nào nên sử dụng Cây AVL trong các dự án thực tế

Cây AVL là lựa chọn tối ưu khi ứng dụng đòi hỏi cả hiệu suất tìm kiếm nhanh O(log n) và khả năng truy xuất dữ liệu theo một thứ tự nhất định. Do Cây AVL về bản chất là một cây nhị phân tìm kiếm, nó cho phép thực hiện các thao tác như tìm phần tử nhỏ nhất/lớn nhất, tìm phần tử kế tiếp/trước đó, hoặc duyệt toàn bộ các phần tử theo thứ tự tăng dần/giảm dần một cách hiệu quả. Các ứng dụng điển hình bao gồm: hệ thống chỉ mục trong cơ sở dữ liệu (database indexing), nơi các truy vấn tìm kiếm theo khoảng (ví dụ: tìm tất cả nhân viên có tuổi từ 25 đến 30) là phổ biến. Ngoài ra, trong các lĩnh vực liên quan đến lý thuyết đồ thị và thuật toán, Cây AVL cũng được dùng để triển khai các cấu trúc như tập hợp có thứ tự (ordered sets) hoặc bản đồ có thứ tự (ordered maps) trong các thư viện lập trình.

4.2. Sức mạnh của Bảng Băm trong việc xây dựng bộ đệm cache

Một trong những ứng dụng phổ biến và mạnh mẽ nhất của Bảng Băm là xây dựng hệ thống bộ đệm (cache). Cache được sử dụng để lưu trữ các kết quả tính toán hoặc dữ liệu thường xuyên được truy cập nhằm giảm thời gian phản hồi. Ví dụ, một máy chủ web có thể cache các trang HTML đã được tạo ra. Khi một yêu cầu mới đến, thay vì tạo lại trang, máy chủ sẽ dùng URL làm khóa (key) để tra cứu trong Bảng Băm. Nếu trang đã có trong cache (cache hit), nó sẽ được trả về ngay lập tức, với tốc độ O(1). Nếu không có (cache miss), trang sẽ được tạo, trả về cho người dùng và lưu vào cache cho các lần sau. Tốc độ truy cập trung bình O(1) của Bảng Băm làm cho nó trở thành cấu trúc dữ liệu lý tưởng cho mục đích này. Các trình duyệt web, hệ điều hành, và các hệ thống phân tán đều sử dụng rộng rãi Bảng Băm cho cơ chế caching.

4.3. So sánh hiệu năng Lựa chọn giữa Cây AVL và Bảng Băm

Việc lựa chọn giữa Cây AVL và Bảng Băm phụ thuộc vào một số yếu tố. Về độ phức tạp thời gian: Bảng Băm có hiệu suất trung bình O(1) cho các thao tác cơ bản, nhanh hơn O(log n) của Cây AVL. Tuy nhiên, trường hợp xấu nhất của Bảng Băm là O(n), trong khi Cây AVL đảm bảo O(log n) trong mọi trường hợp. Về bộ nhớ: Cây AVL thường tốn ít bộ nhớ hơn vì nó chỉ lưu trữ những gì cần thiết, trong khi Bảng Băm thường phải cấp phát một mảng lớn hơn số phần tử để giảm đụng độ băm. Về thứ tự: Cây AVL duy trì thứ tự của các khóa, còn Bảng Băm thì không. Tóm lại: nếu ứng dụng của bạn cần tốc độ truy cập nhanh nhất có thể và không yêu cầu duyệt theo thứ tự, hãy chọn Bảng Băm. Nếu ứng dụng yêu cầu hiệu suất ổn định và có thể dự đoán được, cùng với khả năng truy vấn theo thứ tự, Cây AVL là lựa chọn phù hợp hơn.

Trích đoạn nội dung tài liệu

Các cấu trúc dữ liệu nâng cao (Advanced Data Structures) 3.1 Cây nhị phân tìm kiếm cân bằng 3.3 Bảng băm – Hash Table Winter 2014 123 (C) Nguyen Tri Tuan - DH.HCM Cây nhị phân tìm kiếm cân bằng (1) Cây BST có thể bị lệch Vì sao cây BST trở nên bị lệch ? Chi phí tìm kiếm trên cây bị lệch ? Một cây BST không cân bằng Winter 2014 124 (C) Nguyen Tri Tuan - DH.HCM Cây nhị phân tìm kiếm cân bằng (2) Cây cân bằng chiều cao và chi phí tìm kiếm tối ưu O(log2N) Winter 2014 125 (C) Nguyen Tri Tuan - DH.HCM Cây nhị phân tìm kiếm cân bằng (3) Cần có phương pháp để duy trì tính cân bằng cho cây BST Winter 2014 126 (C) Nguyen Tri Tuan - DH.HCM Cây nhị phân tìm kiếm cân bằng (4) Các loại cây BST cân bằng Cây AVL Cây Đỏ - Đen (Red – Black tree) Cây AA Winter 2014 127 (C) Nguyen Tri Tuan - DH.HCM Cây AVL (1) Định nghĩa Cài đặt cấu trúc dữ liệu Mất cân bằng khi thêm/xóa node Các thuật toán điều chỉnh cây Đánh giá/so sánh E. Adelson-Velskii Winter 2014 128 (C) Nguyen Tri Tuan - DH.HCM Cây AVL (2) Cấu trúc cây AVL do 2 tác giả người Liên xô: G. Adelson-Velskii và E. Landis công bố năm 1962 Đây là mô hình cây tự cân bằng đầu tiên được đề xuất (self-adjusting, height- balanced binary search tree) Winter 2014 129 (C) Nguyen Tri Tuan - DH.HCM Định nghĩa cây AVL (1) Cây AVL: Là một cây nhị phân tìm kiếm (BST) Mỗi nút p của cây đều thỏa: chiều cao của cây con bên trái (p->left) và chiều cao của cây con bên phải (p->right) chênh lệch nhau không quá 1 ∀p∈TAVL: abs(hp->left - hp->right)≤ 1 Winter 2014 130 (C) Nguyen Tri Tuan - DH.HCM Định nghĩa cây AVL (2) Chiều cao 2 cây con left, right chênh lệch không quá 1 Winter 2014 131 (C) Nguyen Tri Tuan - DH.HCM Định nghĩa cây AVL (3) Cây AVL ? Winter 2014 132 (C) Nguyen Tri Tuan - DH.HCM Cài đặt cấu trúc dữ liệu (1) Cấu trúc node, tree tương tự như BST Thêm vào mỗi node một field balance, diễn tả trạng thái cân bằng của node đó: balance = -1: node lệch trái (cây con trái cao hơn cây con phải) balance = 0: node cân bằng (cây con trái cao bằng cây con phải) balance = +1: node lệch phải (cây con phải cao hơn cây con trái) Winter 2014 133 (C) Nguyen Tri Tuan - DH.HCM Cài đặt cấu trúc dữ liệu (2) +1 20 [phone] 0 0 25 27 Hệ số cân bằng của các node trong cây AVL Winter 2014 134 (C) Nguyen Tri Tuan - DH.HCM Cài đặt cấu trúc dữ liệu (3) template <class T> class AVLNode { public: T key; // key of node char balance; // balance status of node BSTNode *left; // pointer to left child BSTNode *right; // pointer to right child BSTNode() { } BSTNode(T aKey) { key = aKey; balance = 0; left = right = NULL; } }; // end class Winter 2014 135 (C) Nguyen Tri Tuan - DH.HCM Mất cân bằng khi thêm/xóa node (1) [Insert – Thêm 1 phần tử vào cây]: có thể làm cây mất cân bằng.

Duyệt từ node vừa thêm ngược về node gốc Nếu tìm thấy node P bị mất cân bằng thì tiến hành xoay cây tại nút P (chỉ cần điều chỉnh 1 lần duy nhất) Winter 2014 136 (C) Nguyen Tri Tuan - DH.HCM Mất cân bằng khi thêm/xóa node (2) 44 P 17 78 Thêm phần tử 54 32 50 88 làm cây mất cân bằng tại node P 48 62 54 Winter 2014 137 (C) Nguyen Tri Tuan - DH.HCM Mất cân bằng khi thêm/xóa node (3) [Delete – Xóa 1 phần tử]: có thể làm cây mất cân bằng. Duyệt từ node vừa xóa ngược về node gốc Nếu tìm thấy node P bị mất cân bằng thì tiến hành xoay cây tại node P Lưu ý: Thao tác điều chỉnh có thể làm cho những node phía trên của node P bị mất cân bằng cần điều chỉnh cho đến khi không còn node nào bị mất cân bằng nữa (lùi dần về node gốc) Winter 2014 138 (C) Nguyen Tri Tuan - DH.HCM Mất cân bằng khi thêm/xóa node (4) P 44 17 78 Xóa phần tử 32 làm 32 50 88 cây mất cân bằng tại node P 48 62 Winter 2014 139 (C) Nguyen Tri Tuan - DH.HCM Các thuật toán điều chỉnh cây (1) P -1 P -1 -1 +1 P1 P1 h h h C h+1 h h+1 C B A A B (a1) (b1) Hai trường hợp cây bị mất cân bằng ở nhánh trái Winter 2014 140/203 (C) Nguyen Tri Tuan - DH.HCM Các thuật toán điều chỉnh cây (2) P +1 P +1 +1 -1 P1 P1 h h A h A h+1 h h+1 B C C B (a2) (b2) Hai trường hợp cây bị mất cân bằng ở nhánh phải Winter 2014 141 (C) Nguyen Tri Tuan - DH.HCM Các thuật toán điều chỉnh cây (3) P -1 P1 0 -1 P1 P 0 SLR h h C h+1 h+1 h h B A A B C Trường hợp (a1): áp dụng phép xoay đơn Trái - Phải (SLR – Single Left-to-Right) Winter 2014 142 (C) Nguyen Tri Tuan - DH.HCM Các thuật toán điều chỉnh cây (4) 44 44 -1 0 P P1 78 17 50 17 P1 0 P 32 50 -1 88 32 48 78 48 62 46 62 88 SLR 46 Ví dụ: điều chỉnh cây bằng thao tác xoay đơn SLR Winter 2014 143 (C) Nguyen Tri Tuan - DH.HCM Các thuật toán điều chỉnh cây (5) P -1 P2 0 +1 P1 P1 P DLR P2 h h C h B1 B2 h A A C B1 B2 Trường hợp (b1): áp dụng phép xoay kép Trái - Phải (DLR – Double Left–to-Right) Winter 2014 144 (C) Nguyen Tri Tuan - DH.HCM Các thuật toán điều chỉnh cây (6) 44 44 P P2 -1 17 78 0 17 62 P1 P1 P [phone] +1 P2 48 62 48 88 54 -1 DLR 54 Ví dụ: thao tác xoay kép DLR Winter 2014 145 (C) Nguyen Tri Tuan - DH.HCM Các thuật toán điều chỉnh cây (7) Đối với trường hợp (a2) và (b2) Xử lý tương tự như (a1) và (b1), đối xứng qua trục đứng Trường hợp (a2) Áp dụng phép xoay SRL – Single Right-to-Left Trường hợp (b2) Áp dụng phép xoay DRL – Double Right-to-Left Winter 2014 146 (C) Nguyen Tri Tuan - DH.HCM Ví dụ tạo cây AVL (1) Tạo cây AVL với các khóa lần lượt là: 30, 20, 10,… 30 20 20 SLR 10 30 10 Winter 2014 147 (C) Nguyen Tri Tuan - DH.HCM Ví dụ tạo cây AVL (2) 20 20 10 30 10 30 15 25 40 15 26 40 27 DRL 25 27 26 …thêm 15, 40, 25, 27, 26 Winter 2014 148 (C) Nguyen Tri Tuan - DH.HCM Ví dụ tạo cây AVL (3) 20 20 DLR 10 30 30 10 5 15 26 40 26 40 5 14 13 25 27 15 25 27 13 14 … thêm 5, 13, 14 Winter 2014 149 (C) Nguyen Tri Tuan - DH.HCM Đánh giá/so sánh Độ cao của cây: hAVL < 1.44*log2(N+1) Cây AVL có độ cao nhiều hơn không quá 44% so với độ cao của 1 cây nhị phân tối ưu. Chi phí tìm kiếm O(log2N) Chi phí thêm phần tử O(log2N) Tìm kiếm: O(log2N) Điều chỉnh cây: O(log2N) Chi phí xóa phần tử O(log2N) Tìm kiếm: O(log2N) Điều chỉnh cây: O(log2N) Winter 2014 150 (C) Nguyen Tri Tuan - DH.HCM Các cấu trúc dữ liệu nâng cao (Advanced Data Structures) 3.1 Cây nhị phân tìm kiếm cân bằng 3.3 Bảng băm – Hash Table Winter 2014 168 (C) Nguyen Tri Tuan - DH.HCM Bảng băm – Hash Table Giới thiệu Direct-address table Bảng băm Khai báo cấu trúc Hash Table Xung đột địa chỉ Hàm băm Các phương pháp xử lý xung đột Winter 2014 169 (C) Nguyen Tri Tuan - DH.HCM Giới thiệu (1) Bài toán: Cho một tập các khóa (key). Nhu cầu chủ yếu là tìm kiếm (thêm, xóa ít khi xảy ra) Cách tổ chức lưu trữ và tìm kiếm với chi phí thấp ? Winter 2014 170 (C) Nguyen Tri Tuan - DH.HCM Giới thiệu (3) Các cấu trúc dữ liệu đã biết: Mảng, Danh sách liên kết, BST,… tìm kiếm bằng cách so sánh lần lượt các phần tử thời gian tìm kiếm không nhanh và phụ thuộc N (số phần tử) Cây bậc 3 chi phí tìm kiếm O(log3N) Winter 2014 172 (C) Nguyen Tri Tuan - DH.HCM Direct-address table (1) Giả sử có một tập khoá U: Kích thước không quá lớn Các giá trị khoá phân biệt VD.

U = {0, 1, 2, …, 9} Mô hình minh họa dùng direct-address table T[m] để lưu trữ các khoá trong tập U Winter 2014 173 (C) Nguyen Tri Tuan - DH.HCM Direct-address table (2) Direct-address table: Một mảng T[m] (T[0],…,T[m-1]) để chứa các khoá trong tập U |T| = |U| Mỗi vị trí T[k] (slot) sẽ chứa: • Khóa k, hay • NULL nếu khoá k không có trong tập hợp Lưu ý: U (Universe of keys): tập các giá trị khóa K (Actual keys): tập các khoá thực sự được dùng Chi phí thao tác: O(1) Winter 2014 174 (C) Nguyen Tri Tuan - DH.HCM Direct-address table (3) Các giới hạn của direct-address table: Kích thước tập U quá lớn không thể tạo bảng T với số slot tương ứng với |U| Kích thước của tập K quá nhỏ so với U rất nhiều slot bị bỏ trống Winter 2014 175 (C) Nguyen Tri Tuan - DH.HCM Bảng băm (1) Khi tập khóa K nhỏ hơn nhiều (VD) so với tập U ta chỉ dùng mảng T[m] với kích thước vừa đủ cho tập K m = Θ(|K|) Do đó, không thể áp dụng ánh xạ trực tiếp T[k]  k được nữa Thay vì ánh xạ trực tiếp T[k]  k, ta dùng hàm băm h để ánh xạ T[h(k)]  k Winter 2014 176 (C) Nguyen Tri Tuan - DH.HCM Bảng băm (2) Hàm băm h: dùng để ánh xạ các khoá của tập U vào những slot của bảng băm T[0.m-1] h(k): giá trị băm (hash value) của khoá k Winter 2014 177 (C) Nguyen Tri Tuan - DH.HCM Bảng băm (3) Định nghĩa bảng băm: Bảng băm là một cấu trúc dữ liệu, lưu trữ các khóa trong bảng T (danh sách đặc); sử dụng một hàm băm (hash function) để ánh xạ khoá (key) với một địa chỉ lưu trữ Hàm băm có tác dụng biến đổi khoá thành chỉ số địa chỉ (index) – tương ứng với khoá Bảng băm là cấu trúc rất phù hợp để cài đặt cho bài toán “từ điển (dictionary)” Dictionary: dạng bài toán chỉ chủ yếu sử dụng thao tác chèn thêm (Insert) và tìm kiếm (Search) Winter 2014 178 (C) Nguyen Tri Tuan - DH.HCM Bảng băm (4) Hàm băm – biến đổi khoá thành địa chỉ index Winter 2014 179 (C) Nguyen Tri Tuan - DH.