Thảo Luận - Cân Bằng Cây AVL (Code) | VN-Zoom

Speedtest Telegram Discord VNZoom Beta

• DIỄN ĐÀN Kiến Thức Công Nghệ Khoa Học Mới Reviews Công Nghệ Công Nghệ AI 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 Discord VN-Zoom Chăn Nuôi Trồng trọt
• ĐÁNH GIÁ
• BÀI MỚI
• WINDOWS
• CÔNG NGHỆ AI

Đăng nhập Register Có gì mới? Tìm kiếm

Tìm kiếm

Everywhere Chủ đề This forum This thread Tìm kiếm dựa vào tiêu đề (tích để chọn) Bởi: Tìm kiếm Tìm kiếm nâng cao…

• Kiến Thức Công Nghệ Khoa Học Mới
• Reviews Công Nghệ
• Công Nghệ AI
• 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
• Discord VN-Zoom
• Chăn Nuôi
• Trồng trọt

Menu Đăng nhập Register Install the app Install

• DIỄN ĐÀN
• Thư viện Tin Học
• Lập Trình

You are using an out of date browser. It may not display this or other websites correctly.You should upgrade or use an alternative browser. Thảo luậnCân bằng cây AVL (Code)

• Thread starter statistics
• Ngày gửi 10/12/20

S

statistics

Moderator

Thành viên BQT Cân bằng cây là việc rất cần thiết để tối ưu việc tìm kiếm và thêm xoá dễ dàng hơn. Để cân bằng cây thì cây AVL là cây dễ dàng cân bằng nhất, các bạn có thể đọc thêm phần lý thuyết để hiểu rõ hơn về cách cân bằng cây AVL trước khi bắt đầu code. Xem bài lý thuyết: https://vn-z.vn/threads/thuat-toan-can-bang-cay-avl.32451/ Chuẩn bị Cấu trúc của một node cây AVL Một node cần lưu trữ bốn thuộc tính bao gồm:

• key: Để lưu giá trị của Node.
• p_left: lưu con trỏ trỏ tới bên trái.
• p_right: lưu con trỏ trỏ tới bên phải.
• height: lưu chiều cao của node.

C++: struct NODE { int key; NODE* p_left; NODE* p_right; int height; }; Quy ước Chúng ta nên quy ước một số việc:

• Tất cả các node lá hoặc node mới chưa thêm vào trong cây có height = 1.
• Một node bất kì có chiều cao (height) là max(pLeft, pRight) + 1 tức là chiều cao lớn nhất của node bên trái hoặc bên phải và cộng thêm một đơn vị.
• Một vị trí được cho là mất cân bằng khi height node bên phải và node bên trái chênh lệch nhau từ hai đơn vị trở lên.
• Khi kiểm tra cây có cân bằng hay không, quy ước: -1 là cây lệch trái, 0 là cây cân bằng, 1 là cây lệch bên phải của node đó.
• Mỗi khi thêm hoặc xoá phần tử ta cần cập nhật lại chiều cao của cây.
• Để có thể dễ dàng duyệt, trong phần code mình sẽ sử dụng phép duyệt LRN để duyệt từ cuối cây duyệt lên.

Chia nhỏ vấn đề Trước khi bắt tay vào làm, chúng ta nên thực hiện bước chia để trị, tức là chia nhỏ vấn đề ra thành các vấn đề con rồi từ từ giải quyết các vấn đề đó trước rồi đến vấn đề cha. Hãy suy nghĩ thật đơn giản, hãy tạo version 1 rồi sau đó tối ưu lại thành version 2, đừng cố làm hoàn hảo ngay lúc đầu, mình học được điều này từ thầy mình và mình thấy việc code nhẹ nhàng hơn rất nhiều. Thường thì lúc viết, mình sẽ suy luận từ trên xuống dưới để tạo ra các hàm, mục đích là để chia nhỏ vấn đề. Nhưng lúc mình code mình sẽ code từ dưới code lên. Tức là mình sẽ viết hàm findMax sau đó viết các hàm xoay cho tới hàm kiểm tra node và cuối cùng là hàm cân bằng cây. Khi viết từng hàm, mình sẽ suy nghĩ hết tất cả các trường hợp có thể xảy ra và viết như một đứa trẻ, tức là mình không ngồi đánh giá xem liệu dòng code đó có dư thừa hay không? Có hay không thì mặc kệ, việc đó để cho version 2 làm. Và tin mình đi, mình gần như debug khá ít. Lưu ý: Trong các hàm này, lúc bạn xoay cây sẽ không có vấn đề, nhưng lúc bạn cập nhật height cho node sẽ xảy ra trường hợp node chỉ có một con trái hoặc phải, dẫn tới node còn lại là null, và bạn cần phải xử lý trường hợp đó trước. Tham khảo code cân bằng cây AVL Code của hàm findMaxHeight: C++: int findMaxHeight(NODE* pLeft, NODE* pRight) { if (pLeft == nullptr) return pRight->height; else if (pRight == nullptr) return pLeft->height; return pLeft->height > pRight->height ? pLeft->height : pRight->height; } Code trên không cần giải thích quá nhiều, đơn giản nó sẽ kiểm tra hai node con xem thằng nào lớn hơn thì trả về thằng lớn hơn đó. Code hàm rotateLeftLeft: C++: //Xoay trai void rotateLeftLeft(NODE* &pRoot) { NODE* temp = pRoot->p_left; // giu P1 pRoot->p_left = pRoot->p_left->p_right; // bán con temp->p_right = pRoot; // Xoay pRoot = temp;// P1 lên làm cha //Cap nhat height. Cần xác định là những node lá sẽ không thay đổi height nên ta chỉ cập nhật các node không phải lá NODE* pNow = pRoot->p_right; pNow->height = findMaxHeight(pNow->p_left, pNow->p_right) + 1; pRoot->height = findMaxHeight(pRoot->p_left, pRoot->p_right) + 1; } Vì là hàm xoay cây sẽ thay đổi ngay chính cây truyền vào, nên ở đây mình sẽ dùng tham chiếu. Bạn đừng hỏi là dùng con trỏ là trỏ vào địa chỉ rồi thì dùng tham chiếu để làm gì nha. Vì đơn giản là khi bạn dùng con trỏ nó sẽ sinh ra một con trỏ tạm trỏ vào pRoot ở trên, thì code sẽ sai ở dòng "pRoot = temp" pRoot tạm này sẽ được gán bằng temp chứ không được gán vào cây. Bạn cần lưu ý pRoot lúc này là một node con trỏ ở ngoài chứ không phải con trỏ của cây. Tới đây, chắc các bạn cũng đã hiểu tại sao truyền tham chiếu rồi, ý đồ của mình nằm ở đây. Bạn để ý vòng tròn màu đỏ, bên trái là con trỏ thuộc cây, bên phải là con trỏ ở ngoài cây. Tới lúc này bạn đọc code ở trên dễ hiểu hơn rồi đấy. Sự khác nhau giữa truyền tham chiếu và con trỏ Code hàm rotateLeftRight: C++: void rotateLeftRight(NODE*& pRoot) { NODE* pCur = pRoot->p_left; // pCur giữ vị trí P1 để thực hiện quay trái trước, pCur lúc này đóng vai trò là pRoot của cây con nhỏ pRoot->left pRoot->p_left = pCur->p_right; pCur->p_right = nullptr; pRoot->p_left->p_left = pCur; //Cập nhật height cho cây sau khi xoay . NODE* pNow = pRoot->p_left; NODE* pNow1 = pNow->p_left; pNow1->height = findMaxHeight(pNow1->p_left, pNow1->p_right) + 1; pNow->height = findMaxHeight(pNow->p_left, pNow->p_right) + 1; //Thực hiện xong công việc quay trái, bây giờ thực hiện công việc quay phải //Cây hiện tại đã biến thành cây lệch trái bên trái => gọi hàm cũ là xong. rotateLeftLeft(pRoot); } Bạn hiểu được các phần trên thì phần này không cần giải thích gì nữa vì nó nằm ở phần lý thuyết. Tương tự cho hai hàm bên phải vì nó đối xứng nhau. Code hàm isBalanceTree: C++: /*Check Tree is Balance*/ int isBalanceTree(NODE* pRoot) { if (pRoot == nullptr || pRoot->p_left == nullptr && pRoot->p_right == nullptr) { // trái phải đều null return 0; // can bang } else if (pRoot->p_left == nullptr ) { // trái null phải không null if (pRoot->p_right->height > 1) // lệch nhau 2 đơn vị, vì null thì xem như height bằng 0 return 1; else return 0; } else if (pRoot->p_right == nullptr) { // phải null trái không null if (pRoot->p_left->height > 1) // lệch nhau 2 đơn vị, vì null thì xem như height bằng 0 return -1; else return 0; } int check = pRoot->p_right->height - pRoot->p_left->height; if (check >= 2) { // lệch nhau 2 đơn vị mà dương return 1; // lech phai } else if (check <= -2) { // lệch nhau 2 đơn vị mà âm return -1; // lech trai } else return 0; } Đặt tên là isBalanceTree nhưng thật ra nó kiểm tra xem node tại đó có cân bằng hay không thôi. Mà mình thấy là tên không sai, bởi vì node đang xét cân bằng thì cây con ở dưới cũng cân bằng cộng thêm việc mình duyệt cây là duyệt từ dưới lên trên. Code hàm BalanceTree: C++: //Balance AVL /*Bool is check succesfull*/ bool BalanceTree(NODE* &pRoot) { if (pRoot == nullptr) { return 0; } BalanceTree(pRoot->p_left); BalanceTree(pRoot->p_right); if (isBalanceTree(pRoot) == -1) { // lech trai NODE* p1 = pRoot->p_left; int index = p1->p_right->height - p1->p_left->height; if (index <= 0) { rotateLeftLeft(pRoot); } else { rotateLeftRight(pRoot); } } else if ( isBalanceTree(pRoot) == 1 ) { // lech phai NODE* p1 = pRoot->p_right; int index = p1->p_right->height - p1->p_left->height; if (index >= 0) { rotateRightRight(pRoot); } else { rotateRightLeft(pRoot); } } } Các bước phức tạp chủ yếu các hàm trên, hàm này chỉ đơn giản là kiểm tra xem node bị mất cân bằng ở đâu, và mất cân bằng loại gì? trái trái, trái phải, phải phải hay phải trái rồi gọi hàm xoay thôi. Nãy giờ, mình chỉ đi cân bằng cây, nhưng cây chỉ bị mất cân bằng khi thêm hoặc xoá. Vậy lúc thêm, xoá một giá trị nào đó trong cây, bạn cần cập nhật lại height của tất cả các node. C++: void Insert(NODE*& pRoot, int x) { if (pRoot == nullptr) { return; } if (x == pRoot->key) { return; } if (x > pRoot->key) { Insert(pRoot->p_right, x); if (pRoot->p_right == nullptr) { NODE* cur = createNode(x); pRoot->p_right = cur; } if (pRoot->p_left == nullptr) { pRoot->height = abs(pRoot->p_right->height) + 1; } else { pRoot->height = findMaxHeight(pRoot->p_left, pRoot->p_right) + 1; } } else { Insert(pRoot->p_left, x); if (pRoot->p_left == nullptr) { NODE* cur = createNode(x); pRoot->p_left = cur; } if (pRoot->p_right == nullptr) { pRoot->height = abs(pRoot->p_left->height) + 1; } else { pRoot->height = findMaxHeight(pRoot->p_left, pRoot->p_right) + 1; } } } Hàm Insert này mình chỉ lấy bên hàm Insert của cây bình thường chỉ thêm phần cập nhật lại height của node. Code hoàn thiện C++: struct NODE { int key; NODE* p_left; NODE* p_right; int height; }; NODE* createNode(int data) { NODE* p = new NODE; p->key = data; p->p_left = nullptr; p->p_right = nullptr; p->height = 1; return p; } int findMaxHeight(NODE* pLeft, NODE* pRight) { if (pLeft == nullptr) return pRight->height; else if (pRight == nullptr) return pLeft->height; return pLeft->height > pRight->height ? pLeft->height : pRight->height; } /*Check Tree is Balance*/ int isBalanceTree(NODE* pRoot) { if (pRoot == nullptr || pRoot->p_left == nullptr && pRoot->p_right == nullptr) { // trái phải đều null return 0; // can bang } else if (pRoot->p_left == nullptr ) { // trái null phải không null if (pRoot->p_right->height > 1) // lệch nhau 2 đơn vị, vì null thì xem như bậc bằng 0 return 1; else return 0; } else if (pRoot->p_right == nullptr) { // phải null trái không null if (pRoot->p_left->height > 1) // lệch nhau 2 đơn vị, vì null thì xem như bậc bằng 0 return -1; else return 0; } int check = pRoot->p_right->height - pRoot->p_left->height; if (check >= 2) { // lệch nhau 2 đơn vị mà dương return 1; // lech phai } else if (check <= -2) { // lệch nhau 2 đơn vị mà âm return -1; // lech trai } else return 0; } //Xoay trai void rotateLeftLeft(NODE* &pRoot) { NODE* temp = pRoot->p_left; // giu P1 pRoot->p_left = pRoot->p_left->p_right; // bán con temp->p_right = pRoot; // Xoay pRoot = temp;// P1 lên làm cha //Cap nhat height. Cần xác định là những node lá sẽ không thay đổi height nên ta chỉ cập nhật các node không phải lá NODE* pNow = pRoot->p_right; pNow->height = findMaxHeight(pNow->p_left, pNow->p_right) + 1; pRoot->height = findMaxHeight(pRoot->p_left, pRoot->p_right) + 1; } void rotateLeftRight(NODE*& pRoot) { NODE* pCur = pRoot->p_left; // pCur giữ vị trí P1 để thực hiện quay trái trước, pCur lúc này đóng vai trò là pRoot của cây con nhỏ pRoot->left pRoot->p_left = pCur->p_right; pCur->p_right = nullptr; pRoot->p_left->p_left = pCur; //Cập nhật height cho cây sau khi xoay . NODE* pNow = pRoot->p_left; NODE* pNow1 = pNow->p_left; pNow1->height = findMaxHeight(pNow1->p_left, pNow1->p_right) + 1; pNow->height = findMaxHeight(pNow->p_left, pNow->p_right) + 1; //Thực hiện xong công việc quay trái, bây giờ thực hiện công việc quay phải //Cây hiện tại đã biến thành cây lệch trái bên trái => gọi hàm cũ là xong. rotateLeftLeft(pRoot); } //Balance AVL /*Bool is check succesfull*/ bool BalanceTree(NODE* &pRoot) { if (pRoot == nullptr) { return 0; } BalanceTree(pRoot->p_left); BalanceTree(pRoot->p_right); if (isBalanceTree(pRoot) == -1) { // lech trai NODE* p1 = pRoot->p_left; int index = p1->p_right->height - p1->p_left->height; if (index <= 0) { rotateLeftLeft(pRoot); } else { rotateLeftRight(pRoot); } } else if ( isBalanceTree(pRoot) == 1 ) { // lech phai NODE* p1 = pRoot->p_right; int index = p1->p_right->height - p1->p_left->height; if (index >= 0) { rotateRightRight(pRoot); } else { rotateRightLeft(pRoot); } } } Tổng kết Mong là bài viết dễ hiểu. Cây AVL là khởi đầu của các loại cây sau này như cây đỏ đen, cây AA các bạn tìm hiểu kỹ và tự code thử trước khi tham khảo bài viết. Mình sử dụng văn nói để dễ truyền đạt và dễ hiểu nên có thể từ ngữ sẽ không chuẩn 100%. Bạn có thể sử dụng trang web này để kiểm tra bản thân code đúng hay sai. Giả lập AVL tree Sửa lần cuối: 10/12/20 Bạn chỉ nhìn thấy những gì bạn muốn thấy. Bạn chỉ nhìn thấy những gì tôi muốn cho bạn thấy.

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

simpboy

Gà con

ủa cái xoay trái trái là sao v ạ, em xem ko hiểu S

statistics

Moderator

Thành viên BQT

simpboy nói: ủa cái xoay trái trái là sao v ạ, em xem ko hiểu Nhấn để mở rộng...

simpboy nói: ủa cái xoay trái trái là sao v ạ, em xem ko hiểu Nhấn để mở rộng...

bạn xem bài lý thuyết này nha, nó sẽ giải thích kỹ á.

Thuật toán cân bằng cây AVL

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... vn-z.vn 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

Mời Trải nghiệm xây dựng mô phỏng “hạ tầng AI” Game Data Center trong vai kỹ sư hạ tầng số. lúc 18:37 Hôm qua “Bà mẹ 14 tuổi” phiên bản đời thực ở Nhật gây chú ý: Hai mẹ con trông như chị em song sinh lúc 06:22 Hôm qua Lộ điểm benchmark Samsung Galaxy S26 Ultra : AnTuTu vượt mốc 3,72 triệu, test không gặp hiện tượng quá nhiệt lúc 10:35 Hôm qua Hàng loạt bom tấn PC chạy mượt trên Android, game thủ thử xong chỉ biết thốt lên “quá đã” lúc 07:44, Thứ hai Mùa 2 loạt phim người đóng One Piece Into the Grand Line, Từ Núi Đảo Ngược đến Đảo Drum: Netflix sẽ chính thức lên sóng vào ngày 10/3. lúc 17:07, Chủ nhật Test mù thú vị: dân audio không phân biệt được tín hiệu âm thanh truyền qua dây đồng xịn, chuối… hay bùn ướt lúc 11:04, Thứ hai Meta khai tử Messenger.com: từ tháng 4/2026 chỉ còn sử dụng qua ứng dụng di động hoặc Facebook lúc 21:30, Thứ sáu

ĐỪNG BÕ LỠ

Mời Trải nghiệm xây dựng mô phỏng “hạ tầng AI” Game Data Center trong vai kỹ sư hạ tầng số. lúc 18:37 Hôm qua Lộ điểm benchmark Samsung Galaxy S26 Ultra : AnTuTu vượt mốc 3,72 triệu, test không gặp hiện tượng quá nhiệt lúc 10:35 Hôm qua Mozilla phát hành Firefox 148, cho phép tắt toàn bộ AI chỉ với một cú nhấp lúc 08:53 Hôm qua Honor ấn định họp báo toàn cầu MWC 2026 ngày 1/3: ra mắt điện thoại gập Magic V6, ROBOT PHONE lần đầu lộ diện lúc 08:35 Hôm qua Steam Next Fest tháng 2/2026 chính thức khởi động: Chơi demo miễn phí, săn game mới cả tuần lúc 06:29 Hôm qua

Bài Viết Mới

• Mời Trải nghiệm xây dựng mô phỏng “hạ tầng AI” Game Data Center trong vai kỹ sư hạ tầng số.
  • Started by VNZ-Relax
  • lúc 18:37 Hôm qua
  • Trả lời: 1
  Trò Chơi Mới - News Games
• Lộ điểm benchmark Samsung Galaxy S26 Ultra : AnTuTu vượt mốc 3,72 triệu, test không gặp hiện tượng quá nhiệt
  • Started by VNZ-NEWS
  • lúc 10:35 Hôm qua
  • Trả lời: 1
  Android OS
• Mozilla phát hành Firefox 148, cho phép tắt toàn bộ AI chỉ với một cú nhấp
  • Started by VNZ-NEWS
  • lúc 08:53 Hôm qua
  • Trả lời: 0
  Phần Mềm
• Honor ấn định họp báo toàn cầu MWC 2026 ngày 1/3: ra mắt điện thoại gập Magic V6, ROBOT PHONE lần đầu lộ diện
  • Started by VNZ-NEWS
  • lúc 08:35 Hôm qua
  • Trả lời: 0
  Kiến Thức Công Nghệ Khoa Học , Sản Phẩm Mới
• Steam Next Fest tháng 2/2026 chính thức khởi động: Chơi demo miễn phí, săn game mới cả tuần
  • Started by VNZ-Relax
  • lúc 06:29 Hôm qua
  • Trả lời: 0
  Trò Chơi Mới - News Games

• DIỄN ĐÀN
• Thư viện Tin Học
• Lập Trình

Top