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 p10

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

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

Hiệu chỉnh lại các chỉ số cân bằng: B5: AncestorNode-Bal = 0 B6: AncRL-Bal = 0 B7: AncR-Bal = -1 Chuyển vai trò của.Có hai cổng Modem cho phép dial out hoặc dial in, tích hợp sẵn dịch vụ NAT, Default GateWay, DHCP dùng cấp phát IP động cho các máy trạm. Hỗ trợ cả hai nghi thức thẩm định quyền truy cập PAP/CHAP, hỗ trợ Filter (cho hoặc cấm người dùng truy cập Internet).

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 p10

  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 c u -tr a c k c u -tr a c k B2: AncR->BAL_Left = AncRL->BAL_Right AncestorNode AncL -2 AncR AncRL 1 AncRR h 1 AncRLL AncRLR h h-1 h B3: AncRL->BAL_Left = AncestorNode AncestorNode AncL -2 AncR AncRL 1 AncRR h 1 AncRLL AncRLR h h-1 h Trang: 198
  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 c u -tr a c k c u -tr a c k B4: AncRL->BAL_Right = AncR AncestorNode AncL -2 AncR AncRL 1 AncRR h 1 AncRLL AncRLR h h-1 h Hieäu chænh laïi caùc chæ soá caân baèng: B5: AncestorNode->Bal = 0 B6: AncRL->Bal = 0 B7: AncR->Bal = -1 Chuyeån vai troø cuûa AncRL cho AncestorNode vaø chuùng ta coù caây caân baèng môùi: B8: AncestorNode = AncRL AncestorNode AncRL 0 AncR AncL 0 AncRLL AncRLR -1 AncRR h-1 h h h Trang: 199
  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 c u -tr a c k c u -tr a c k - AncRLL coù chieàu cao laø h-1 vaø AncRLR coù chieàu cao laø h (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 hoaøn toaøn gioáng vôùi tröôøng hôïp treân, duy chæ khaùc nhau veà giaù trò chæ soá caân baèng sau khi quay keùp. Chuùng ta cuõng thöïc hieän caùc böôùc sau: B1: AncestorNode->BAL_Right = AncRL->BAL_Left B2: AncR->BAL_Left = AncRL->BAL_Right B3: AncRL->BAL_Left = AncestorNode B4: AncRL->BAL_Right = AncR B5: AncestorNode->Bal = 1 B6: AncR->Bal = 0 B7: AncRL->Bal = 0 B8: AncestorNode = AncRL Sau khi quay keùp caây seõ trôû thaønh: AncestorNode AncRL 0 AncR AncL 1 AncRLL AncRLR 0 AncRR h-1 h h h Trang: 200
  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 c u -tr a c k c u -tr a c k - Caû AncRLL vaø AncRLR ñeàu coù chieàu cao laø h (AncRL->Bal =0; h ≥ 0) AncestorNode AncL -2 AncR AncRL 1 AncRR h 0 AncRLL AncRLR h h h Cuõng töông töï, chuùng ta caân baèng laïi AncestorNode baèng caùch quay keùp gioáng nhö tröôøng hôïp treân nhöng veà giaù trò chæ soá caân baèng sau khi quay thì khaùc nhau. Caùc böôùc thöïc hieän nhö sau: B1: AncestorNode->BAL_Right = AncRL->BAL_Left B2: AncR->BAL_Left = AncRL->BAL_Right B3: AncRL->BAL_Left = AncestorNode B4: AncRL->BAL_Right = AncR B5: AncestorNode->Bal = 0 B6: AncR->Bal = 0 B7: AncRL->Bal = 0 B8: AncestorNode = AncRL Sau khi quay keùp caây seõ trôû thaønh: AncestorNode AncRL 0 AncR AncL 0 AncRLL AncRLR 0 AncRR h h h h Trang: 201
  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 Ví duï: 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: c u -tr a c k c u -tr a c k BALTree 25 -1 19 0 40 0 NULL NULL 30 0 44 0 NULL NULL NULL NULL Caây nhò phaân tìm kieám caân baèng sau khi theâm nuùt coù Key = 27 nhö sau: BALTree 25 -2 19 0 40 1 NULL NULL 30 1 44 0 27 0 NULL NULL NULL NULL NULL Thöïc hieän quay ñôn caây con traùi cuûa BALTree->BAL_Right caây nhò phaân tìm kieám sau khi quay trôû thaønh caây nhò phaân tìm kieám nhö sau: BALTree 25 -2 19 0 30 -1 NULL NULL 27 0 40 -1 NULL NULL NULL 44 0 NULL NULL Thöïc hieän quay ñôn 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: Trang: 202
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