Cấu trúc dữ liệu cây đỏ đen và mô phỏng

KHÓA LUẬN TỐT NGHIỆP

Đề tài:

CẤU TRÚC DỮ LIỆU CÂY ĐỎ ĐEN

VÀ MÔ PHỎNG

Giáo viên hướng dẫn : PGS.TSKH. Trần Quốc Chiến

Sinh viên thực hiện : Phan Thị Như Ngọc

Lớp : 08SPT

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

KHOA TIN HỌC

Đà Nẵng - 5/ 2012

Trước khi trình bày đề tài, em xin bày tỏ lòng biết

ơn chân thành đến tất cả các thầy cô trong khoa Tin học,

đặc biệt PGS. TSKH. Trần Quốc Chiến trong thời gian

qua đã tận tâm giảng dạy, hướng dẫn tạo mọi điều kiện

thuận lợi để em hoàn thành đề tài này.

Em cũng xin thành thật cảm ơn những người thân,

bạn bè đã động viên, giúp đỡ trong thời gian xây dựng

đề tài.

Chân thành cảm ơn!!

Sinh viên thực hiện

Phan Thị Như Ngọc

LỜI CẢM ƠN

Ý KIẾN ĐÁNH GIÁ CỦA GIÁO VIÊN HƯỚNG DẪN

.........................................................................................................................

Đà Nẵng, ngày tháng năm

2012

Giáo viên hướng dẫn

PGS-TSKH Trần Quốc Chiến

MỤC LỤC

LỜI CẢM ƠN

Ý KIẾN ĐÁNH GIÁ CỦA GIÁO VIÊN HƯỚNG DẪN

MỤC LỤC

LỜI MỞ ĐẦU.......................................................................................................................7

I. LÍ DO CHỌN ĐỀ TÀI:................................................................................................7

II. MỤC TIÊU NHIỆM VỤ:...........................................................................................8

III. PHƯƠNG PHÁP NGHIÊN CỨU:...........................................................................8

IV. BỐ CỤC CỦA ĐỀ TÀI:............................................................................................9

CHƯƠNG I: TỔNG QUAN VỀ CẤU TRÚC CÂY .......................................................10

I. CẤU TRÚC CÂY:......................................................................................................10

1. ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM VỀ CÂY:...............................................10

2. SƠ ĐỒ CẤU TRÚC CÂY:....................................................................................11

3. ỨNG DỤNG CẤU TRÚC CÂY: ..........................................................................12

4. MỘT SỐ VÍ DỤ VỀ ĐỐI TƯỢNG CÁC CẤU TRÚC DẠNG CÂY:...............12

4.1. Sơ đồ tổ chức của một công ty:......................................................................12

4.2. Mục lục một quyển sách:................................................................................13

4.3. Biểu diễn biểu thức số học dưới dạng cây: x + y * (z - t) + u / v..................13

5. NHẬN XÉT:...........................................................................................................14

II. TÌM HIỂU CÂY NHỊ PHÂN : ................................................................................14

1. ĐỊNH NGHĨA :......................................................................................................14

2. MỘT SỐ DẠNG ĐẶC BIỆT CỦA CÂY NHỊ PHÂN :......................................14

3. TÍNH CHẤT :........................................................................................................16

CHƯƠNG II: CÂY NHỊ PHÂN TÌM KIẾM..................................................................17

I. MỘT SỐ KHÁI NIỆM:.............................................................................................17

II. SƠ ĐỒ CÂY NHỊ PHÂN TÌM KIẾM:..................................................................17

III. CẤU TRÚC DỮ LIỆU:...........................................................................................18

IV. CÁC THAO TÁC TRÊN CÂY NHỊ PHÂN TÌM KIẾM:...................................18

1. Khởi tạo cây Binary Search Tree:........................................................................18

1.1. Khởi tạo cây Binary Search Tree:.................................................................18

1.2. Tạo Node:.........................................................................................................18

1.3. Tạo cây nhị phân tìm kiếm: ...........................................................................19

2. Duyệt cây nhị phân tìm kiếm:...............................................................................20

2.1. Duyệt theo thứ tự trước (Node - Left - Right): ............................................20

2.2. Duyệt theo thứ tự giữa (Left - Node - Right): ..............................................21

2.3. Duyệt theo thứ tự sau (Left - Right - Node): ................................................21

3. Tìm một phần tử x trong cây:...............................................................................22

 Giải thuật tìm kiếm: ..........................................................................................22

 Nhận xét:.............................................................................................................22

3.1. Tìm theo đệ quy: .............................................................................................24

3.2. Tìm theo không đệ quy:..................................................................................25

3.3. Thêm một nút vào cây Binary Search Tree: ................................................25

3.4. Nhận xét:..........................................................................................................27

4. Hủy một phần tử có khóa X:.................................................................................27

4.1. Trường hợp 1: X là nút lá. .............................................................................27

4.2. Trường hợp 2: X chỉ có một con (bên trái hoặc bên phải)..........................28

4.3. Trường hợp 3: X có đủ hai con......................................................................29

5. Hủy toàn bộ cây nhị phân tìm kiếm:....................................................................32

V. NHẬN XÉT: ..............................................................................................................33

CHƯƠNG III: CÂY ĐỎ ĐEN..........................................................................................34

I. GIỚI THIỆU: .............................................................................................................34

II. ĐỊNH NGHĨA:..........................................................................................................34

III. TÍNH CHẤT:...........................................................................................................35

IV. THUẬN LỢI KHI SỬ DỤNG:...............................................................................36

V. CẤU TRÚC CÂY ĐỎ ĐEN:....................................................................................38

1. Cấu trúc lưu trữ: ...................................................................................................38

2. Khai báo cây đỏ đen:.............................................................................................38

VI. CÁC THUẬT TOÁN CƠ BẢN CỦA BLACK AND RED TREE:.....................39

1. Phép quay:..............................................................................................................39

2. Thêm một node mới:..............................................................................................39

2.1. Các phép lật màu trên đường đi xuống:.......................................................41

2.2. Các phép quay khi chèn node:.......................................................................42

2.3. Các thao tác khôi phục cây:...........................................................................49

2.4. Các trường hợp vi phạm chính: ....................................................................50

2.4.1. Trường hợp 1:..........................................................................................50

2.4.2. Trường hợp 2:..........................................................................................51

2.4.3. Trường hợp 3:..........................................................................................52

2.5. Nhận xét khi chèn:..........................................................................................53

2.6. Code: ................................................................................................................54

3. Xóa một node: ........................................................................................................57

3.1. Trường hợp 1:.................................................................................................58

3.2. Trường hợp 2:.................................................................................................58

3.3. Trường hợp 3:.................................................................................................59

3.4. Trường hợp 4:.................................................................................................59

4. Tìm kiếm: ...............................................................................................................61

I. GIỚI THIỆU NGÔN NGỮ LẬP TRÌNH:.............................................................64

1. Vài nét về ngôn ngữ Java:.....................................................................................64

2. Một số đặc điểm của ngôn ngữ Java:...................................................................64

3. Giới thiệu ứng dụng của Java vào chương trình cây đỏ đen: ...........................65

II. DEMO CHƯƠNG TRÌNH:.....................................................................................66

KẾT LUẬN.........................................................................................................................68

TÀI LIỆU THAM KHẢO.................................................................................................69

Thư viện tri thức trực tuyến

Cấu trúc dữ liệu cây đỏ đen và mô phỏng

Nội dung xem thử

Mô tả chi tiết

Tài liệu tương tự (6)

Cấu trúc dữ liệu và giải thuật

Cấu trúc dữ liệu và Thuật toán

Cấu trúc dữ liệu và thuật toán (Tái bản)

Cấu trúc dữ liệu và thuật giải

Cấu trúc dữ liệu nâng cao

Cấu trúc dữ liệu