intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Giáo trình hướng dẫn dùng thuật toán thêm một nút vào bên trái nhất của cây nhị phân p9

Chia sẻ: Dgdsfg Hkuyou | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST
Báo xấu
94
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'giáo trình hướng dẫn dùng thuật toán thêm một nút vào bên trái nhất của cây nhị phân p9', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình hướng dẫn dùng thuật toán thêm một nút vào bên trái nhất của cây nhị phân p9

  1. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o BALTree c u -tr a c k c u -tr a c k 25 -2 19 0 40 -1 NULL NULL 30 0 44 -1 NULL NULL NULL 50 0 NULL NULL Thöïc hieän quay caây con phaûi cuûa BALTree, caây nhò phaân tìm kieám sau khi quay trôû thaønh caây nhò phaân tìm kieám caân baèng nhö sau: BALTree 40 0 25 0 44 -1 19 0 30 0 NULL 50 0 NULL NULL NULL NULL NULL NULL b1) AncRL vaø AncRR ñeàu coù chieàu cao laø h+1 (AncR->Bal = 0) AncestorNode AncL -2 AncR AncRL 0 AncRR h h+1 h+1 Vieäc baèng laïi ñöôïc thöïc hieän töông töï nhö tröôøng hôïp a1) ôû treân: B1: AncestorNode->BAL_Right = AncR->BAL_Left Trang: 193
  2. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o AncestorNode c u -tr a c k c u -tr a c k AncL -2 AncR 0 AncRR h h+1 h+1 B2: AncR->BAL_Left = AncestorNode AncestorNode AncL -2 AncR 0 AncRR h h+1 h+1 B3: AncR->Bal = 1, AncestorNode->Bal = -1 Vieäc quay keát thuùc, caây trôû thaønh caây caân baèng. AncR AncestorNode 1 AncRR AncL -1 AncRL h h+1 h+1 Chuyeån vai troø cuûa AncR cho AncestorNode: AncestorNode = AncR Trang: 194
  3. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o Keát quaû sau pheùp quay: c u -tr a c k c u -tr a c k AncestorNode AncR 1 AncRR AncL -1 AncRL h h+1 h+1 c1) AncRL coù chieàu cao laø h+1 vaø AncRR coù chieàu cao laø h (AncR->Bal = 1) AncestorNode AncL -2 AncR AncRL 1 AncRR h h+1 h Ñeå caân baèng laïi AncestorNode chuùng ta thöïc hieän vieäc quay keùp: quay caây con traùi AncRL vaø quay caây con phaûi AncR (Double Rotation). Ví duï: Vieäc theâm nuùt coù Key = 27 vaøo caây nhò phaân tìm kieám caân baèng sau ñaây seõ laøm cho caây maát caân baèng vaø chuùng ta phaûi caân baèng laïi theo tröôøng hôïp naøy: BALTree 25 -1 19 0 40 0 NULL NULL 30 0 44 0 NULL NULL NULL NULL Trang: 195
  4. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o Vieäc quay ñöôïc tieán haønh cuï theå nhö sau: c u -tr a c k c u -tr a c k Goïi: AncRLL = AncRL->BAL_Left AncRLR = AncRL->BAL_Right ⇒ AncRLL vaø AncRLR coù chieàu cao toái ña laø h ⇒ Caây con coù nuùt goác AncestorNode coù theå ôû vaøo moät trong ba daïng sau: - AncRLL coù chieàu cao laø h vaø AncRLR coù chieàu cao laø h-1 (AncRL->Bal =1; h ≥ 1) AncestorNode AncL -2 AncR AncRL 1 AncRR h 1 AncRLL AncRLR h h-1 h Ñeå caân baèng laïi AncestorNode ñaàu tieân chuùng ta thöïc hieän vieäc quay ñôn caây con traùi AncRL cuûa AncR leân thaønh nuùt goác caây con phaûi cuûa AncestorNode, chuyeån AncR nuùt thaønh nuùt goác caây con phaûi cuûa AncRL vaø chuyeån AncRLR thaønh nuùt goác caây con traùi cuûa AncR. Sau khi quay caây seõ trôû thaønh: AncestorNode AncL -2 AncRL AncRLL -1 AncR h AncRLR -1 AncRR h h-1 h Trang: 196
  5. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o Baây giôø chuùng ta tieáp tuïc thöïc hieän vieäc quay ñôn caây con phaûi AncRL cuûa c u -tr a c k c u -tr a c k AncestorNode leân thaønh nuùt goác vaø chuyeån AncRLL nuùt thaønh nuùt goác caây con phaûi cuûa AncestorNode. Sau khi quay caây seõ trôû neân caân baèng: AncRL AncestorNode 0 AncR AncL 0 AncRLL AncRLR -1 AncRR h-1 h h h Nhö vaäy ñeå thöïc hieän quaù trình quay keùp naøy chuùng ta thöïc hieän caùc böôùc sau: B1: AncestorNode->BAL_Right = AncRL->BAL_Left AncestorNode AncL -2 AncR AncRL 1 AncRR h 1 AncRLL AncRLR h h-1 h Trang: 197
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2