Thuật Toán Cân Bằng Cây AVL | VN-Zoom
Có thể bạn quan tâm
Ủng hộ Speedtest VNZ-News Telegram VNZoom Beta 
Moderator
Thành viên BQT Tại sao phải cân bằng cây? Cân bằng cây là gì? Cách cân bằng cây AVL như thế nào? Trong bài viết này mình sẽ trình bày lý thuyết, bài viết sau mình sẽ trình bày code và giải thích. Ngoài ra các bạn nên tìm hiểu thêm các cách cân bằng cây khác nữa. Tại sao phải cân bằng cây? Bạn hãy nhìn vào cây sau đây, bạn thấy cây này giống gì? 
Bạn nhìn thấy giống gì nào? Bạn có thấy giống Linked List không? Mà Binary Tree được tạo ra để phục vụ việc tìm kiếm nhanh hơn, thêm, xoá phần tử dễ dàng hơn với O(log2(n)) nhưng khi các bạn thêm các phần tử và không may nó thành Linked List, việc tìm kiếm là O(n). Vậy chúng ta nên cân bằng để cây trở thành Binary Tree và việc tìm kiếm phần tử sẽ dễ dàng hơn. Cân bằng cây là gì? Thay vì cây của bạn biến thành Linked List thì bạn sẽ biến nó thành Binary Tree thực sự, cũng là hình trên nhưng khi bạn thêm sẽ tự động cân bằng lại cây? 
Theo cây AVL cây được gọi là cân bằng khi chiều cao của cây con bên phải không cao hơn cây con bên trái quá một đơn vị và ngược lại. Tức là chiều cao chỉ được chênh lệch nhau từ tối đa 1 đơn vị. Ví dụ: 
Cây AVL, chênh 1 bậc. 
Không phải cây AVL, lệch 2 bậc. Cân bằng cây AVL như thế nào? Bạn cần làm quen với việc xoay cây, để làm quen với việc này, mình sẽ đưa ra các ví dụ từ dễ đến phức tạp. Nói nôm na là các bạn sẽ cầm cây và quay theo một hướng xác định. Đầu tiên, đến với hình dễ nào: 
Xoay cây từ phải sang trái Bạn hãy tưởng tượng bạn đang cầm Node A và bạn hất Node A từ phải sang trái, thì theo quán tính Node P sẽ bay xuống làm con Node A, vậy là cây cân bằng. Hình trên là cây lệch bên phải nên bạn phải xoay bên trái và tương tự với cây lệch bên trái thì các bạn phải xoay sang phải. Nâng độ khó game lên chút xíu bây giờ các bạn thử xoay cây này xem vẫn áp dụng cách xoay như trên. Hình dưới, cây bị mất cân bằng tại Node 18 vì Node 20 và Node 12 cách nhau 2 đơn vị. Còn tại cây con Node 15 thì cây vẫn cân bằng vì Node 16 và Node 12 chỉ cách nhau 1 đơn vị và cây AVL cho phép điều đó. 
Cây lệch trái bên trái Khác một tý với ví dụ bên trên là bạn chỉ cần cầm Node A và hất sang bên phải là xong. Đối với cây lệch trái bên trái bạn cũng hất tương tự nhưng bạn phải thực hiện hành động bán "con". Cụ thể: 
Tương tự với cây lệch phải bên phải: 
Cây lệch phải bên phải Chắc tới đây, các bạn sẽ hỏi cây lệch trái bên trái là gì? Cây lệch phải bên phải là gì? Thực ra do mình hiểu nhưng không biết giải thích thế nào cho dễ hiểu nên mình sẽ lấy ví dụ tường minh để các bạn tự nhận ra. Và đây là cây lệch trái bên phải: 
Mình đoán là nhìn hình các bạn cũng hiểu được lệch trái bên trái là gì rồi. Với cây lệch trái bên phải thì hơi phức tạp xíu, các bạn nên lấy giấy bút ra để vẽ và đọc kỹ để tránh nhầm lẫn. Đầu tiên, các bạn cần lấy cây con bên trái xoay bên trái để biến cây trở thành cây bên trái lệch trái. 
Tới đây, cân bằng cây quá dễ dàng chỉ cần dùng thuật toán cân bằng cây bên trái lệch trái là xong. 
Và tương tự như vậy với cây lệch phải bên phải. Tổng kết Mình đã giới thiệu xong phần lý thuyết về cây AVL và thuật toán để cân bằng cây AVL và mình có một số gợi ý sau đây: Giả lập cây AVL 
- DIỄN ĐÀN Tin Tức Công Nghệ và Đời Sống Reviews Công Nghệ Tin Học Căn Bản Phần Cứng Phần Mềm Kiến thức điện tử - Tiêu Dùng Khoa Học & Công Nghệ Anti Virus Bảo Mật Lập Trình Thiết Kế WEB - VPS HOST- MẠNG Digital Marketing Kho Tài Nguyên - Học Tập Hệ điều hành Windows Windows 12 Windows 11 Windows 10 Windows 8 Hệ Điều Hành Linux Hệ Điều Hành Mac (Apple) Ghost/ WinPE - Hirent's Boot Điện Ảnh Âm Nhạc Tranh Ảnh Đọc Truyện Thể Thao Chuyện Trò Linh Tinh Điện Thoại Di Động - Thiết Bị Cầm Tay Hệ Điều Hành Android iOS (Apple) Thế Giới Thiết Bị Số Máy Ảnh Số Thiết bị hình ảnh - Truyền Hình Tin Tức Ô Tô Xe Máy Xe điện Hỏi Đáp Ô TÔ - Xe Máy Game PC & Console Thông tin Game Game Mobile 2048 Trung Tâm Thương Mại Điện Tử Telegram VN-Zoom Chăn Nuôi Trồng trọt
- ĐÁNH GIÁ
- BÀI MỚI
- Asus Apple Sony Bphone SamSung Corsair LG Nokia Xiaomi HTC Canon Nikon Oppo OnePlus ViVo Google Microsoft NVIDIA Lenovo Huawei
- DONATE
Tìm kiếm
Everywhere Chủ đề This forum This thread Tìm kiếm dựa vào tiêu đề (tích để chọn) Tìm kiếm Tìm kiếm nâng cao…- Tin Tức Công Nghệ và Đời Sống
- Reviews Công Nghệ
- Tin Học Căn Bản
- Phần Cứng
- Phần Mềm
- Kiến thức điện tử - Tiêu Dùng
- Khoa Học & Công Nghệ
- Anti Virus
- Bảo Mật
- Lập Trình
- Thiết Kế WEB - VPS HOST- MẠNG
- Digital Marketing
- Kho Tài Nguyên - Học Tập
- Hệ điều hành Windows Windows 12 Windows 11 Windows 10 Windows 8
- Hệ Điều Hành Linux
- Hệ Điều Hành Mac (Apple)
- Ghost/ WinPE - Hirent's Boot
- Điện Ảnh
- Âm Nhạc
- Tranh Ảnh
- Đọc Truyện
- Thể Thao
- Chuyện Trò Linh Tinh
- Điện Thoại Di Động - Thiết Bị Cầm Tay Hệ Điều Hành Android iOS (Apple)
- Thế Giới Thiết Bị Số Máy Ảnh Số Thiết bị hình ảnh - Truyền Hình
- Tin Tức Ô Tô Xe Máy
- Xe điện
- Hỏi Đáp Ô TÔ - Xe Máy
- Game PC & Console
- Thông tin Game
- Game Mobile
- 2048
- Trung Tâm Thương Mại Điện Tử
- Telegram VN-Zoom
- Chăn Nuôi
- Trồng trọt
- Thanh lý đồ công nghệ
- WinXDVD Giveaway 30 phần mềm cao cấp, tổng gía trị hơn 1000 USD
- Lễ Hội Phần Mềm Miễn Phí Từ AOMEI: Nhận Ngay 22 Phần Mềm Miễn Phí tổng giá trị $1,456!
- WonderFox Giveaway Giáng Sinh 2024: Nhận Ngay 12 Phần Mềm Miễn Phí Trị Giá Hơn $380!.
We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.
We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!
We need money to operate the site, and almost all of it comes from our online advertising.
Please add https://vn-z.vn to your ad blocking whitelist or disable your adblocking software.
×- DIỄN ĐÀN
- Thư viện Tin Học
- Lập Trình
- Thread starter statistics
- Ngày gửi 9/12/20
statistics
Moderator
Thành viên BQT Tại sao phải cân bằng cây? Cân bằng cây là gì? Cách cân bằng cây AVL như thế nào? Trong bài viết này mình sẽ trình bày lý thuyết, bài viết sau mình sẽ trình bày code và giải thích. Ngoài ra các bạn nên tìm hiểu thêm các cách cân bằng cây khác nữa. Tại sao phải cân bằng cây? Bạn hãy nhìn vào cây sau đây, bạn thấy cây này giống gì? Bạn nhìn thấy giống gì nào? Bạn có thấy giống Linked List không? Mà Binary Tree được tạo ra để phục vụ việc tìm kiếm nhanh hơn, thêm, xoá phần tử dễ dàng hơn với O(log2(n)) nhưng khi các bạn thêm các phần tử và không may nó thành Linked List, việc tìm kiếm là O(n). Vậy chúng ta nên cân bằng để cây trở thành Binary Tree và việc tìm kiếm phần tử sẽ dễ dàng hơn. Cân bằng cây là gì? Thay vì cây của bạn biến thành Linked List thì bạn sẽ biến nó thành Binary Tree thực sự, cũng là hình trên nhưng khi bạn thêm sẽ tự động cân bằng lại cây? Theo cây AVL cây được gọi là cân bằng khi chiều cao của cây con bên phải không cao hơn cây con bên trái quá một đơn vị và ngược lại. Tức là chiều cao chỉ được chênh lệch nhau từ tối đa 1 đơn vị. Ví dụ: Cây AVL, chênh 1 bậc. Không phải cây AVL, lệch 2 bậc. Cân bằng cây AVL như thế nào? Bạn cần làm quen với việc xoay cây, để làm quen với việc này, mình sẽ đưa ra các ví dụ từ dễ đến phức tạp. Nói nôm na là các bạn sẽ cầm cây và quay theo một hướng xác định. Đầu tiên, đến với hình dễ nào: Xoay cây từ phải sang trái Bạn hãy tưởng tượng bạn đang cầm Node A và bạn hất Node A từ phải sang trái, thì theo quán tính Node P sẽ bay xuống làm con Node A, vậy là cây cân bằng. Hình trên là cây lệch bên phải nên bạn phải xoay bên trái và tương tự với cây lệch bên trái thì các bạn phải xoay sang phải. Nâng độ khó game lên chút xíu bây giờ các bạn thử xoay cây này xem vẫn áp dụng cách xoay như trên. Hình dưới, cây bị mất cân bằng tại Node 18 vì Node 20 và Node 12 cách nhau 2 đơn vị. Còn tại cây con Node 15 thì cây vẫn cân bằng vì Node 16 và Node 12 chỉ cách nhau 1 đơn vị và cây AVL cho phép điều đó. Cây lệch trái bên trái Khác một tý với ví dụ bên trên là bạn chỉ cần cầm Node A và hất sang bên phải là xong. Đối với cây lệch trái bên trái bạn cũng hất tương tự nhưng bạn phải thực hiện hành động bán "con". Cụ thể: - Khi bạn cầm Node 15 hất sang bên phải thì Node 15 sẽ làm cha và Node 18 sẽ làm Node con bên phải của Node 15, cây con Node 13 vẫn sẽ là cây con bên trái của Node 15.
- Mình cá là các bạn thấy thắc mắc ở Node 16 sẽ quăng đi đâu? Vì nếu xoay mà không bán con thì thành ra Node 15 có 3 liên kết (không còn là cây binary nữa).
- Node 16 sẽ bán mình cho Node bên trái của Node 18.
Tương tự với cây lệch phải bên phải: Cây lệch phải bên phải Chắc tới đây, các bạn sẽ hỏi cây lệch trái bên trái là gì? Cây lệch phải bên phải là gì? Thực ra do mình hiểu nhưng không biết giải thích thế nào cho dễ hiểu nên mình sẽ lấy ví dụ tường minh để các bạn tự nhận ra. Và đây là cây lệch trái bên phải: Mình đoán là nhìn hình các bạn cũng hiểu được lệch trái bên trái là gì rồi. Với cây lệch trái bên phải thì hơi phức tạp xíu, các bạn nên lấy giấy bút ra để vẽ và đọc kỹ để tránh nhầm lẫn. Đầu tiên, các bạn cần lấy cây con bên trái xoay bên trái để biến cây trở thành cây bên trái lệch trái. Tới đây, cân bằng cây quá dễ dàng chỉ cần dùng thuật toán cân bằng cây bên trái lệch trái là xong. Và tương tự như vậy với cây lệch phải bên phải. Tổng kết Mình đã giới thiệu xong phần lý thuyết về cây AVL và thuật toán để cân bằng cây AVL và mình có một số gợi ý sau đây: Giả lập cây AVL - Bạn có thể sử dụng trang này để xem bạn cân bằng cây có đúng hay không?
- Bạn nên tập xoay cây nhiều lần và là những cây phức tạp hơn trước khi code. Bạn có thể cho một cây bất kỳ bằng cách: vẽ cây trước, sau đó điền số vào.
- Bạn có thắc mắc gì về thuật toán đừng ngại để lại comment bên dưới nhé.
Chủ đề tương tự
Đưa website của bạn lên Internet trong vòng nửa nốt nhạc Đóng gói cài đặt kèm database trên Visual Studio 2019 Đóng gói cài đặt kèm database trên Visual Studio 2015 Đọc Nhiều File Excel Cùng Cấu Trúc Vào Gridview Đây có phải là mã nguồn Facebook từ 2003 You must log in or register to reply here. Chia sẻ: Facebook X (Twitter) Reddit Pinterest Tumblr WhatsApp Email Chia sẻ Link ĐANG THẢO LUẬN
- Nhờ tư vấn về mặt nạ lột mụn cho nam giới ? lúc 19:44 Hôm qua Gần 10 năm, Microsoft vẫn chưa hoàn thiện chế độ Dark Mode trên Windows lúc 14:20 Hôm qua các bác pro cho em hỏi với ạ lúc 15:29 Hôm qua Bạn sẽ chọn 8GB DDR4 hay 16GB DDR3 ? lúc 06:23, Chủ nhật Miễn phí trọn đời bản quyền Screencapt 1.100, phần mềm ghi màn hình tối ưu cho Windows lúc 18:38, Thứ bảy [Series Giải Đáp Bản Quyền] Internet Download Manager gói Lifetime lúc 12:11 Hôm qua Xin phần mềm dow.nload album nhạc ở nhaccu.atui.com và zin.g.mp3.co.m với ạ lúc 17:33, Thứ bảy
ĐỪNG BÕ LỠ
- Bản Tin Thị Trường Chứng Khoán Ngày 30/12/2024 lúc 22:17 Hôm qua Nhờ tư vấn về mặt nạ lột mụn cho nam giới ? lúc 19:44 Hôm qua Miễn phí 1 năm bản quyền AmoyShare AnyMusic, Tải Nhạc Dễ Dàng Từ Hơn 1.000 Trang Web lúc 15:39 Hôm qua các bác pro cho em hỏi với ạ lúc 15:29 Hôm qua Gần 10 năm, Microsoft vẫn chưa hoàn thiện chế độ Dark Mode trên Windows lúc 14:20 Hôm qua
Bài Viết Mới
-
Chứng khoánBản Tin Thị Trường Chứng Khoán Ngày 30/12/2024 - Started by motdoidoimotcauhua
- lúc 22:17 Hôm qua
- Trả lời: 0
- Nhờ tư vấn về mặt nạ lột mụn cho nam giới ?
- Started by pgvnz
- lúc 19:44 Hôm qua
- Trả lời: 5
- GiveawayMiễn phí 1 năm bản quyền AmoyShare AnyMusic, Tải Nhạc Dễ Dàng Từ Hơn 1.000 Trang Web
- Started by VNZ-NEWS
- lúc 15:39 Hôm qua
- Trả lời: 0
- các bác pro cho em hỏi với ạ
- Started by ngchinhbn
- lúc 15:29 Hôm qua
- Trả lời: 2
- Gần 10 năm, Microsoft vẫn chưa hoàn thiện chế độ Dark Mode trên Windows
- Started by VNZ-NEWS
- lúc 14:20 Hôm qua
- Trả lời: 2
- DIỄN ĐÀN
- Thư viện Tin Học
- Lập Trình
Từ khóa » Cách Cân Bằng Cây Avl
-
Cây AVL Và Các Thao Tác - TEK4
-
Cây AVL Trong Cấu Trúc Dữ Liệu Và Giải Thuật
-
Chi Tiết Bài Học Cây Cân Bằng - Vimentor
-
Cây AVL (AVL Tree) - Phần 1 (Insertion)
-
[PDF] CÂY CÂN BẰNG AVL
-
[Basic-DSAA] Cấu Trúc Dữ Liệu Cây - Cây AVL. - CodeLearn
-
Cấu Trúc Dữ Liệu Cây Cân Bằng - Cửu Dương Thần Công . Com
-
CTDL>: 9.Cấu Trúc Cây (tiếp) - Cây Cân Bằng AVL - YouTube
-
Thảo Luận - Cân Bằng Cây AVL (Code) | VN-Zoom
-
1.CÂY NHỊ PHÂN CÂN BẰNG HOÀN TOÀN
-
Cây AVL (AVL Tree) – Phần 2 (Deletion)