Tài nguyên

Các ý kiến mới nhất

Hỗ trợ trực tuyến

  • (Trần Văn Luân)
  • (Nguyễn Đăng Nhật Quang)
  • (Trần Đức Anh)

Điều tra ý kiến

Bạn thấy trang này như thế nào?
Đẹp
Bình thường
Sơ sài
Ý kiến khác

Thống kê

  • truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Ảnh ngẫu nhiên

    Hinh0023.jpg Hinh0022.jpg Hinh0015.jpg

    Thành viên trực tuyến

    0 khách và 0 thành viên

    Cây tìm kiếm nhị phân

    Nhấn vào đây để tải về
    Báo tài liệu có sai sót
    Nhắn tin cho tác giả
    (Tài liệu chưa được thẩm định)
    Nguồn: st
    Người gửi: Trần Đức Anh (trang riêng)
    Ngày gửi: 10h:29' 10-11-2011
    Dung lượng: 615.5 KB
    Số lượt tải: 9
    Số lượt thích: 0 người
    TRƯỜNG ĐHSP HÀ NỘI
    LỚP CHK15 - KHOA CNTT
    BÀI GIẢNG MÔN
    CẤU TRÚC DỮ LIỆU
    CÂY TÌM KIẾM NHỊ PHÂN
    KHÁI NIỆM
    TÌM KIẾM
    THÊM
    XOÁ
    GIẢNG VIÊN HƯỚNG DẪN
    PGS.TS LÊ KHẮC THÀNH
    HỌC VIÊN THỰC HIỆN
    NGUYỄN VIỆT HUỲNH MAI
    DUYỆT
    KHÁI NIỆM
    1.CÂY
    Cây là một tập hữu hạn các nút, trong đó có một nút đặc biệt gọi là gốc (root). Giữa các nút có một quan hệ phân cấp gọi là "quan hệ cha con".
    2. CÂY NHỊ PHÂN
    Cây nhị phân là cây có thứ tự và có đặc điểm mọi nút trên cây có tối đa 2 con:
    ? Cây con trái
    ? Cây con phải

    KHÁI NIỆM(tt)
    3. CÂY TÌM KIẾM NHỊ PHÂN
    - Cây tìm kiếm nhị phân được tổ chức theo một cây nhị phân.
    - Cây tìm kiếm nhị phân có thể được biểu diễn bởi một cấu trúc dữ liệu nối kết.
    - Ngoài một trường key, mỗi nút chứa một trường left, right và p trỏ đến các nút tương ứng với con trái, con phải và cha của nó. Nếu thiếu một con hoặc cha trường thích hợp sẽ chứa giá trị NIL. Nút gốc là nút duy nhất trong cây có trường cha là NIL.
    - Các khoá trong cây tìm kiếm nhị phân được lưu trữ theo tính chất sau:
    - Cho x là một nút trong cây tìm kiếm nhị phân. Nếu y là một nút trong cây con trái của x, thì key[y] ? key[x]. Nếu y là một nút trong cây con phải của x, thì key[x] ? key[y].

    0
    KHÁI NIỆM(tt)
    4. VÍ DỤ CÂY TÌM KIẾM NHỊ PHÂN
    1
    4
    4
    5
    10
    8
    0
    1
    4
    4
    5
    10
    8
    Chọn nút số 4 làm nút gốc
    Các nút con là 1 0 4 5 8 10
    Chọn nút số 0 làm nút gốc
    Các nút con là 1 5 4 4 8 10
    0
    1
    4
    4
    5
    10
    8
    DUYỆT CÂY
    1. Duyệt theo thứ tự trước (NODE-LEFT-RIGHT)
    NLR_TREE(x)
    IF X<>NIL THEN
    PRINT key(x)
    NLR_TREE(Left[x])
    NLR_TREE(Right[x])
    0
    1
    4
    4
    5
    10
    8
    4
    Kết quả duyệt:
    4
    1
    1
    0
    0
    4
    4
    5
    5
    8
    8
    10
    10
    Ý tưởng:
    Thăm nút gốc sau đó thăm các nút
    của cây con trái rồi đến cây con phải
    DUYỆT CÂY
    2. Duyệt theo thứ tự giữa (LEFT-NODE-RIGHT)
    LNR_TREE(x)
    IF X<>NIL THEN
    LNR_TREE(Left[x])
    PRINT key(x)
    LNR_TREE(Right[x])
    0
    1
    4
    4
    5
    10
    8
    4
    Kết quả duyệt:
    4
    1
    1
    0
    0
    4
    4
    5
    5
    8
    8
    10
    10
    Ý tưởng:
    Thăm các nút của cây con trái sau đó thăm nút gốc rồi đến cây con phải
    DUYỆT CÂY
    3. Duyệt theo thứ tự sau (LEFT- RIGHT- NODE)
    LRN_TREE(x)
    IF X<>NIL THEN
    LRN_TREE(Left[x])
    LRN_TREE(Right[x])
    PRINT key(x)
    0
    1
    4
    4
    5
    10
    8
    4
    Kết quả duyệt:
    4
    1
    1
    0
    0
    4
    4
    5
    5
    8
    8
    10
    10
    Ý tưởng:
    Thăm các nút của cây con trái sau đó thăm đến cây con phải rồi đến nút gốc
    TÌM KIẾM TRÊN CÂY
    SEARCHNODE(x,k)
    While x<>NIL và k<>key[x]
    Do if k3. x:=left(x)
    4. else
    5. x:=right(x)
    6. return x
    13
    18
    44
    37
    88
    71
    99
    Ý tưởng:
    Cho một biến trỏ đến gốc của cây và một khoá k. Thủ tục tìm kiếm SEARCHNODE trả về một biến trỏ đến một nút có khoá k nếu như nó tồn tại, nếu không nó trỏ về NIL
    23
    40
    15
    59
    55
    Ví dụ: Tìm nút có khoá 55
    So sánh 55 với nút gốc
    55 > 44
    55 < 88
    55 < 59
    55 = 55
    Đã tìm thấy !
    THÊM NÚT VÀO CÂY
    Ý tưởng:
    - Khi thêm một giá trị mới v vào một cây tìm kiếm nhị phân T, ta dùng thủ tục TREE-INSERT.
    - Thủ tục TREE-INSERT được truyền qua một nút z , với key[z]=v, left[z]=NIL, và right[z]=NIL. Thủ tục sửa đổi T và vài trường của z theo cách thức mà z được truyền vào một vị trí thích hợp trong cây.
    - Thủ tục TREE-INSERT bắt đầu tại nút gốc của cây và lần theo một lộ trình đi xuống. Biến trỏ x lần theo lộ trình, và biến trỏ y được duy trì dưới dạng cha của x. Sau khi khởi tạo dòng lặp while trong các dòng 3-7 sẽ khiến hai biến trỏ này dời xuống, đi theo con trái hay phải tùy thuộc vào phép so sánh của key[z] với key[x], cho đến khi x được ấn định là NIL. NIL là vị trí ở đó ta muốn đặt mục đầu vào z. Các dòng 8-13 ấn định các biến trỏ khiến z được chèn.
    THÊM NÚT VÀO CÂY (tt)
    TREE-INSERT(T,z)
    1. y:=NIL
    2. x:= root[T]
    3. while x <> NIL
    4. do y:=x
    5. if key[z]6. then x :=left[x]
    7. else x := right[x]
    8. p[z] :=y
    9. if y=NIL
    10. then root[T]:= z
    11. else if key[z]< key[y]
    12. then left[y]:=z
    13. else right[y]:=z
    THÊM NÚT VÀO CÂY (tt)
    13
    18
    44
    37
    88
    71
    99
    Ví dụ:
    Thêm vào cây T một nút z, với key[z]=12, left[z]=NIL, right[z]=NIL.
    23
    40
    15
    59
    55
    12
    NIL
    NIL
    Nút Z
    x
    y
    x
    y
    x
    y
    x
    Nút Z được thêm vào
    Bắt đầu tại nút gốc, con trỏ x đi xuống,
    con trỏ y duy trì dạng cha của x
    XOÁ NÚT TRÊN CÂY TKNP
    1. PHẦN TỬ KẾ VỊ
    Nếu tất cả các khóa điều riêng biệt, phần tử kế vị của nút x là nút có khóa nhỏ nhất lớn hơn key[x]. thủ tục dưới đây trả về phần tử kế vị của một nút x trong một cây tìm kiếm nhị phân nếu nó tồn tại, và NIL nếu x có khóa lớn nhất trong cây.
    TREE-SUCCESSOR(x)
    1. if right[x] <> NIL
    2. then return TREE-MINIMUM(right[x])
    3. else y:= p[x]
    4. while y <> NIL và x=right[y]
    5. do x:=y
    6. y:=p[y]
    7. return y
    XOÁ NÚT TRÊN CÂY TKNP (tt)
    13
    18
    44
    37
    88
    71
    99
    23
    40
    15
    59
    55
    Ví dụ với cây bên dưới:
    Phần tử kế vị của nút có khóa 40 là nút có khóa 44.
    Phần tử kế vị của nút có khóa 44 là nút có khóa 55.
    XOÁ NÚT TRÊN CÂY TKNP (tt)
    2. XÓA NÚT TRÊN CÂY
    Thủ tục để xóa một nút z đã cho ra khỏi cây tìm kiếm nhị phân chấp nhận một biến trỏ đến z dưới dạng một đối số. Thủ tục xét ba trường hợp:
    - Nếu z không có các con, ta sửa đổi cha của nó là p[z] bằng NIL.
    - Nếu nút chỉ có một con đơn lẻ, ta "nối khử" z bằng cách tạo một nối kết mới giữa con của nó và cha của nó.
    - Nếu nút có hai con, ta nối khử phần tử kế vị y của z, không có con trái và thay nội dung của z bằng nội dung của y.
    TREE-DELETE(T,z)
    1.if left[z]=NIL or right[z]=NIL
    2. then y:=z
    3. else y:= TREE-SUCCESSOR(z)
    4.if left[y]<> NIL
    5. then x := left[y]
    6. else x:= right[y]
    7.if x <> NIL
    8. then p[x] := p[y]
    9.if p[y]=NIL
    10. then root[T] :=x
    11. else if y=left[p[y]]
    12. then left[p[y]] :=x
    13. else right[p[y]] :=x
    14.if y<> z
    15. then key[z] :=key[y]
    16.return y
    XOÁ NÚT TRÊN CÂY TKNP (tt)
    1-3 xác định nút y để khử
    4-6 ấn định x dựa trên y
    7-13 nối khử y bằng cách sửa đổi các biến trỏ trong p[y] và x
    14-16 nội dung của z được dời từ y sang z
    XOÁ NÚT TRÊN CÂY TKNP (tt)
    13
    18
    44
    37
    88
    71
    99
    1. TRƯỜNG HỢP Z KHÔNG CÓ NÚT CON
    23
    40
    15
    59
    55
    Z
    NIL
    Nút 15 đã được xoá!
    XOÁ NÚT TRÊN CÂY TKNP(tt)
    13
    18
    44
    37
    88
    2. TRƯỜNG HỢP Z CÓ 1 NÚT
    23
    40
    15
    Z
    Nút 88 đã được xoá!
    XOÁ NÚT TRÊN CÂY TKNP (tt)
    13
    18
    44
    37
    88
    3. TRƯỜNG HỢP Z CÓ ĐỦ 2 NÚT CON
    33
    40
    29
    Z
    Nút 18 đã được xoá!
    25
    y
     
    Gửi ý kiến