Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: Thắc mắc về cây nhị phân!

  1. #1
    Ngày gia nhập
    04 2008
    Bài viết
    8

    Red face Thắc mắc về cây nhị phân!

    Hi!
    Các bạn cho mình hỏi tí nha.Tại mình mới được học sơ qua về cấu trúc cây nên có vài thắc mắc nhỏ.
    - Cây nhị phân cân bằng khác cây nhị phân tìm kiếm ra sao,các trường hợp áp dụng từng loại.
    - Đối với cây nhị phân cân bằng,muốn tạo thành 1 cây,lấy dữ liệu từ 1 mảng do người dùng nhập vào thì viết code thế nào?

    Thanks mọi người nhé!

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    504

    Cây nhị phân cân bằng là trường hợp riêng của cây nhị phân tìm kiếm.

    Cây nhị phân cân bằng là 1 nhóm các loại cây nhị phân tìm kiếm có thuật toán để giữ một sự cân bằng nhất định trong cây, tức là giữ cho độ dài đường đi từ gốc đến lá khá đồng đều cho các lá, hay giữ cho số đỉnh của 2 cây con của cùng 1 đỉnh khá bằng nhau.

    Nhưng đôi khi từ "cây nhị phân cân bằng" còn dùng để chỉ 1 loại cụ thể trong nhóm này là cây AVL. Cây AVL là cây nhị phân cân bằng có "tính cân bằng" rất mạnh: chiều cao của 2 cây con của cùng 1 đỉnh chỉ sai khác nhau không quá 1 đơn vị, nói cách khác đường đi từ gốc đến lá xa nhất và gần nhất chỉ sai khác nhau không quá 1 đơn vị.

    Nói chung các cây nhị phân càng cân bằng thì phép Insert và Delete của nó càng phức tạp (để đảm bảo sự cân bằng sau mỗi phép toán này) và phép tìm kiếm của nó càng hiệu quả. Cây AVL được dùng khi:

    1/ Mọi phần tử đều có khả năng được tìm kiếm như nhau; và

    2/ Cần tìm kiếm rất thường xuyên trong khi Insert và Delete không thường xuyên lắm; hay khi cần đảm bảo độ phức tạp tìm kiếm trong trường hợp xấu nhất (tức độ phức tạp tối đa, chứ không phải là độ phức tạp bình quân) là thấp nhất có thể (trong khả năng của cấu trúc dữ liệu dạng cây nhị phân.)

    Trên cây AVL các thuật toán Insert và Delete sử dụng các phép biến đổi cây gọi là phép quay trái và quay phải (xem hình: http://en.wikipedia.org/wiki/Image:T...balancing.gif). Thuật toán Inseart và Delete được mô tả ở đây:
    http://en.wikipedia.org/wiki/AVL_tree
    Đã được chỉnh sửa lần cuối bởi Ada : 19-05-2008 lúc 04:47 PM.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn