Cân bằng một cây nhị phân (AVL)

Question

Ok, đây là một số khác trong lĩnh vực lý thuyết cho những người xung quanh CS.

Vào những năm 90, tôi đã làm khá tốt trong việc triển khai BST. Điều duy nhất tôi không bao giờ có thể có được đầu của tôi xung quanh là sự phức tạp của thuật toán để cân bằng một cây nhị phân (AVL).

Các bạn có thể giúp tôi về điều này không?

Answer 1

Cây vật tế thần có thể có thuật toán xác định số dư đơn giản nhất để hiểu. Nếu bất kỳ chèn nào làm cho nút mới quá sâu, nó sẽ tìm thấy một nút xung quanh đó để cân bằng lại, bằng cách xem cân bằng trọng lượng thay vì cân bằng chiều cao. Quy tắc cho dù để cân bằng lại trên xóa cũng đơn giản. Nó không lưu trữ bất kỳ thông tin phức tạp nào trong các nút. Thật khó để chứng minh rằng đó là chính xác, nhưng bạn không cần điều đó để hiểu thuật toán ...

Tuy nhiên, không giống như AVL, nó không cân bằng độ cao ở mọi thời điểm. Giống như màu đỏ-đen, sự mất cân bằng của nó bị giới hạn, nhưng không giống như màu đỏ-đen, nó có thể điều chỉnh được với một tham số, vì vậy với hầu hết các mục đích thực tế, nó trông cân bằng như bạn cần. Tôi nghi ngờ rằng nếu bạn điều chỉnh nó quá chặt chẽ, mặc dù, nó kết thúc lên như xấu hoặc tồi tệ hơn AVL cho trường hợp xấu nhất chèn.

Trả lời câu hỏi chỉnh sửa

tôi sẽ cung cấp đường dẫn cá nhân của tôi để tìm hiểu cây AVL.

Trước tiên, bạn phải hiểu xoay vòng của cây là gì, vì vậy hãy bỏ qua mọi thứ khác bạn đã từng nghe đến thuật toán AVL và hiểu điều đó. Đi thẳng vào đầu của bạn, đó là một vòng quay đúng và đó là vòng quay trái, và mỗi cái sẽ làm gì với cây, nếu không mô tả của các phương pháp chính xác sẽ chỉ gây nhầm lẫn cho bạn.

Tiếp theo, hiểu rằng mẹo để cân bằng cây AVL là mỗi nút ghi lại trong đó sự khác biệt giữa chiều cao của các subtrees trái và phải của nó. Định nghĩa của 'chiều cao cân bằng' là đây là giữa -1 và 1 bao gồm cho mỗi nút trong cây.

Tiếp theo, hãy hiểu rằng nếu bạn đã thêm hoặc xóa một nút, bạn có thể không cân bằng cây. Nhưng bạn chỉ có thể thay đổi số dư của các nút là tổ tiên của nút bạn đã thêm hoặc xóa. Vì vậy, những gì bạn sẽ làm là làm việc theo cách của bạn sao lưu cây, sử dụng phép quay để cân bằng bất kỳ nút không cân bằng bạn tìm thấy, và cập nhật điểm số dư của họ, cho đến khi cây được cân bằng một lần nữa.

Phần cuối cùng của việc hiểu nó là tra cứu một tham chiếu phong nha các phép quay cụ thể được sử dụng để cân bằng lại mỗi nút bạn thấy: đây là "kỹ thuật" của nó trái ngược với khái niệm cao. Bạn chỉ phải nhớ các chi tiết trong khi sửa đổi mã cây AVL hoặc có thể trong quá trình kiểm tra cấu trúc dữ liệu. Đã nhiều năm kể từ lần cuối tôi có mã cây AVL nhiều như mở trong trình gỡ rối - việc triển khai có xu hướng đến một điểm mà chúng hoạt động và sau đó vẫn hoạt động. Vì vậy, tôi thực sự không nhớ. Bạn có thể sắp xếp công việc trên một bảng bằng cách sử dụng một vài chip poker, nhưng thật khó để chắc chắn bạn đã thực sự có tất cả các trường hợp (không có nhiều). Tốt nhất là tìm nó.

Sau đó, doanh nghiệp dịch tất cả thành mã.

Tôi không nghĩ rằng việc xem danh sách mã sẽ giúp rất nhiều với bất kỳ giai đoạn nào ngoại trừ giai đoạn cuối cùng, vì vậy hãy bỏ qua chúng. Ngay cả trong trường hợp tốt nhất, nơi mã được viết rõ ràng, nó sẽ trông giống như một mô tả sách giáo khoa của quá trình, nhưng không có sơ đồ. Trong một trường hợp điển hình hơn đó là một mớ hỗn độn của thao tác cấu trúc C. Vì vậy, chỉ cần dính vào các cuốn sách.

Answer 2

Tôi không nghĩ rằng nên đăng các mã hoàn chỉnh cho các thuật toán cân bằng nút ở đây vì chúng nhận được khá lớn. Tuy nhiên, bài viết trên Wikipedia số red-black trees chứa một triển khai C hoàn chỉnh của thuật toán và bài viết trên AVL trees cũng có một số liên kết đến triển khai chất lượng cao.

Hai triển khai này là đủ cho hầu hết các trường hợp có mục đích chung.

Answer 3

Tôi đồng ý, một chương trình hoàn chỉnh sẽ không phù hợp. Trong khi cây AVL và RB cổ điển sử dụng phương pháp xác định, tôi khuyên bạn nên xem xét "Randomized binary search trees" ít tốn kém hơn để giữ cân bằng và đảm bảo cân bằng tốt bất kể phân phối thống kê các khóa.

Answer 4

Cây AVL không hiệu quả vì bạn phải thực hiện nhiều phép quay cho mỗi lần chèn/xóa.

Cây đỏ-đen có lẽ là một lựa chọn tốt hơn vì chèn/xóa hiệu quả hơn nhiều. Cấu trúc này đảm bảo đường đi dài nhất đến một chiếc lá không quá hai lần con đường ngắn nhất. Vì vậy, trong khi ít cân bằng hơn một cây AVL, các trường hợp không cân bằng tồi tệ nhất là tránh.

Nếu cây của bạn sẽ được đọc nhiều lần và sẽ không bị thay đổi sau khi được tạo, nó có thể đáng giá thêm chi phí cho cây AVL cân bằng hoàn toàn. Ngoài ra, cây Đỏ-Đen yêu cầu thêm một chút dung lượng lưu trữ cho mỗi nút, cho nút "màu" của nút.

Answer 5

Gần đây tôi đã làm việc với cây AVL.

Trợ giúp tốt nhất tôi có thể tìm thấy cách cân bằng chúng thông qua tìm kiếm trên google.

Tôi vừa mã hóa xung quanh mã giả này (nếu bạn hiểu cách xoay vòng dễ thực hiện).

IF tree is right heavy 
{ 
    IF tree's right subtree is left heavy 
    { 
    Perform Double Left rotation 
    } 
    ELSE 
    { 
    Perform Single Left rotation 
    } 
} 
ELSE IF tree is left heavy 
{ 
    IF tree's left subtree is right heavy 
    { 
    Perform Double Right rotation 
    } 
    ELSE 
    { 
    Perform Single Right rotation 
    } 
} 

Answer 6

Để cân bằng cây AVL, tôi vừa viết một loạt các chức năng mà tôi đã chia sẻ với mọi người ở đây. Tôi đoán việc triển khai này hoàn hảo. Các câu hỏi/câu hỏi/chỉ trích là đương nhiên hoan nghênh:

http://uploading.com/files/5883f1c7/AVL_Balance.cpp/

Là một người mới để Stackoverflow, tôi đã cố gắng đăng mã của tôi ở đây nhưng đã bị mắc kẹt với vấn đề định dạng xấu. Vì vậy, tải lên các tập tin trên liên kết ở trên.

Chúc mừng.

Answer 7

có triển khai hoàn chỉnh cây avl tự cân bằng @http://code.google.com/p/self-balancing-avl-tree/. nó cũng thực hiện các hoạt động ghép nối và chia nhỏ thời gian logarit cũng như một bộ sưu tập bản đồ/đa chiều