zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG

Chia sẻ: Le Van Hiep Anh Hiệp | Ngày: | Loại File: PPT | Số trang:15

Báo xấu

381
lượt xem 52
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cây nhị phân tìm kiếm cân bằng là cây mà tại mỗi nút của nó độ cao của cây con trái và của cây con...

Chủ đề:

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

Lưu

Nội dung Text: CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG

NỘI DUNG CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG Cấu trúc dữ liệu và thuật giải
Ðịnh nghĩa  Cây nhị phân tìm kiếm cân bằng là cây mà tại mỗi nút của nó độ cao của cây con trái và của cây con phải chênh lệch không quá một 44 Cấu trúc dữ liệu và thuật giải Ví dụ: 23 88 59 108 13 37 15 30 40 55 71
Tổ chức dữ liệu • Chỉ số cân bằng = độ lệch giữa cây trái và cây phải của một nút • Các giá trị hợp lệ : ⇔ – CSCB( p) = 0 Độ cao cây trái ( p) = Độ cao cây phải ( p) Cấu trúc dữ liệu và thuật giải ⇔ – CSCB( p) = 1 Độ cao cây trái ( p) < Độ cao cây phải ( p) ⇔ – CSCB( p) = -1 Độ cao cây trái ( p) > Độ cao cây phải ( p)
Tổ chức dữ liệu(tt) typedef struct tagAVLNode { balFactor; //chỉ số cân bằng char Data key; struct tagAVLNode* pLeft; struct tagAVLNode* pRight; Cấu trúc dữ liệu và thuật giải }AVLNode; typedef AVLNode*AVLTree;
Các trường hợp mất cân bằng do lệch trái T T LT LT h-1 h-1 R R 1 1 h-1 h h-1 h R L L1 R1 Cấu trúc dữ liệu và thuật giải 1 1 T LT h-1 R 1 h h L1 L1
Các trường hợp mất cân bằng do lệch phải T T RT RT h-1 h-1 L L 1 1 h-1 h-1 h h L R R1 L1 Cấu trúc dữ liệu và thuật giải T 1 1 RT h-1 L 1 h h L1 R1
Các thao tác trên cây cân bằng Khi thêm hay xoá 1 nút trên cây, cĩ thể làm cho cây mất tính cân bằng, khi ấy ta phải tiến hành cân bằng lại. • Cây có khả năng mất cân bằng khi thay đổi chiều cao: – Lệch nhánh trái, thêm bên trái – Lệch nhánh phải, thêm bên phải Cấu trúc dữ liệu và thuật giải – Lệch nhánh trái, hủy bên phải – Lệch nhánh phải, hủy bên trái • Cân bằng lại cây : tìm cách bố trí lại cây sao cho chiều cao 2 cây con cân đối: – Kéo nhánh cao bù cho nhánh th ấp – Phải bảo đảm cây vẫn là Nhị phân tìm kiếm
Các trường hợp mất cân bằng do lệch trái 1 .1 Cây T lệch trái, cây trái T1 của T cũng lệch trái T T 1 T L T Cấu trúc dữ liệu và thuật giải h-1 h 1 R L1 h-1 h h-1 R1 h-1 R1 R L1
Các trường hợp mất cân bằng do lệch trái 1 . 2 Cây T lệch trái, cây trái T1 của T không lệch T T 1 Cấu trúc dữ liệu và thuật giải T L T h-1 h 1 R L1 h h h-1 R L1 R1 R1
Các trường hợp mất cân bằng do lệch trái 1 . 3 Cây T lệch trái, cây trái T1 của T lệch phải T T2 T1 h-1 Cấu trúc dữ liệu và thuật giải R T1 T T2 h-1 R1 L1 h-1 h-1 h L1 L2 R2 R L2 R2
Các trường hợp mất cân bằng do lệch phải 1 .1 Cây T lệch phải, cây phải T1 của T cũng lệch phải T T 1 T L T Cấu trúc dữ liệu và thuật giải h-1 h 1 R L1 h-1 h h-1 R1 h-1 R1 R L1
Các trường hợp mất cân bằng do lệch phải 1 . 2 Cây T lệch phải, cây phải T1 của T không lệch T T 1 T L T Cấu trúc dữ liệu và thuật giải h-1 h 1 R L1 h h h h-1 R R1 L1 R1
Các trường hợp mất cân bằng do lệchcây phiải T1 của T lệch phả 1 . 3 Cây T lệch phải, trái T2 T T T1 T1 h-1 Cấu trúc dữ liệu và thuật giải R T2 h-1 h-1 h-1 R1 L1 R R2 L2 L1 h R2 L2
Thêm 1 nút • Thêm bình thường như trường hợp cây NPTK • Nếu cây tăng trưởng chiều cao: – Lần ngược về gốc để phát hiện nút bị mất cân bằng Cấu trúc dữ liệu và thuật giải – Tiến hành cân bằng lại nút đó bằng thao tác cân bằng thích hợp • Việc cân bằng lại chỉ cần thực hiện 1 lần tại nơi mất cân bằng
Hủy 1 nút • Hủy bình thường như trường hợp cây NPTK • Nếu cây giảm chiều cao: – Lần ngược về gốc để phát hiện nút bị mất cân bằng – Tiến hành cân bằng lại nút đó bằng thao tác cân bằng thích hợp Cấu trúc dữ liệu và thuật giải – Tiếp tục lần ngược lên nút cha… • Việc cân bằng lại co thể lan truyền lên tận gốc

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.