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

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...
Nội dung trích xuất từ tài liệu:
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ẰNGCấ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 44Cấ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 R1Cấ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 L1Cấ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ảiCấu trúc dữ liệu và thuật giải – Lệc ...