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

Ủng hộ Speedtest VNZ-News Telegram VNZoom Beta

• 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
• BRANDS Asus Apple Sony Bphone SamSung Corsair LG Nokia Xiaomi HTC Canon Nikon Oppo OnePlus ViVo Google Microsoft NVIDIA Lenovo Huawei
• DONATE

Đă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…

• 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

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

• 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!.

Adblocker detected! Please consider reading this notice.

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

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

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
  Kinh doanh & Khởi Nghiệp
• 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
  Chuyện trò linh tinh
• 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
  Phần Mềm
• 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
  Phần Mềm
• 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
  Tin tức công nghệ và Đời sống

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

Top