Api tìm kiếm nhị phân python

Trong hướng dẫn này, chúng tôi sẽ giới thiệu Cây AVL và chúng tôi sẽ xem xét các thuật toán để chèn, xóa và tìm kiếm các giá trị

2. Cây AVL là gì?

Cây AVL, được đặt theo tên của các nhà phát minh Adelson-Velsky và Landis, là một cây tìm kiếm nhị phân tự cân bằng [BST]

Cây tự cân bằng là cây tìm kiếm nhị phân cân bằng chiều cao sau khi chèn và xóa theo một số quy tắc cân bằng

Độ phức tạp thời gian trong trường hợp xấu nhất của BST là một hàm của chiều cao của cây. Cụ thể, đường đi dài nhất từ ​​gốc của cây đến một nút. Đối với BST có N nút, giả sử rằng mỗi nút chỉ có 0 hoặc một nút con. Do đó, chiều cao của nó bằng N và thời gian tìm kiếm trong trường hợp xấu nhất là O[N]. Vì vậy, mục tiêu chính của chúng tôi trong BST là giữ chiều cao tối đa gần với log[N]

Hệ số cân bằng của nút N là chiều cao[phải[AND]] – chiều cao[trái[N]]. Trong Cây AVL, hệ số cân bằng của nút chỉ có thể là một trong các giá trị 1, 0 hoặc -1

Hãy xác định một đối tượng Node cho cây của chúng ta

public class Node {
    int key;
    int height;
    Node left;
    Node right;
    ...
}

Tiếp theo, hãy xác định AVLTree

public class AVLTree {

    private Node root;

    void updateHeight[Node n] {
        n.height = 1 + Math.max[height[n.left], height[n.right]];
    }

    int height[Node n] {
        return n == null ? -1 : n.height;
    }

    int getBalance[Node n] {
        return [n == null] ? 0 : height[n.right] - height[n.left];
    }

    ...
}

3. Làm thế nào để cân bằng một cây AVL?

Cây AVL kiểm tra hệ số cân bằng của các nút sau khi chèn hoặc xóa nút. Nếu hệ số cân bằng của một nút lớn hơn một hoặc nhỏ hơn -1, cây sẽ tự cân bằng lại

Có hai thao tác để cân bằng lại cây

• quay phải và
• xoay trái

3. 1. Xoay phải

Hãy bắt đầu với vòng quay bên phải

Giả sử chúng ta có một BST gọi là T1, với Y là nút gốc, X là nút con bên trái của Y và Z là nút con bên phải của X. Với các đặc điểm của BST, chúng ta biết rằng X < Z < Y

Sau khi xoay phải Y, chúng ta có một cây gọi là T2 với X là gốc và Y là con phải của X và Z là con trái của Y. T2 vẫn là BST vì nó giữ nguyên thứ tự X < Z < Y

Hãy cùng xem thao tác xoay vòng bên phải cho AVLTree của chúng tôi

Node rotateRight[Node y] {
    Node x = y.left;
    Node z = x.right;
    x.right = y;
    y.left = z;
    updateHeight[y];
    updateHeight[x];
    return x;
}

3. 2. Thao tác xoay trái

Ta cũng có phép toán xoay trái

Giả sử BST có tên là T1, với Y là nút gốc, X là nút con bên phải của Y và Z là nút con bên trái của X. Với điều này, chúng ta biết rằng Y < Z < X

Sau khi xoay trái Y, chúng ta có một cây gọi là T2 với X là gốc và Y là con trái của X và Z là con phải của Y. T2 vẫn là BST vì nó giữ nguyên thứ tự Y < Z < X

Hãy xem thao tác xoay trái cho AVLTree của chúng ta

Node rotateLeft[Node y] {
    Node x = y.right;
    Node z = x.left;
    x.left = y;
    y.right = z;
    updateHeight[y];
    updateHeight[x];
    return x;
}

3. 3. Kỹ thuật tái cân bằng

Chúng ta có thể sử dụng các thao tác xoay phải và xoay trái trong các kết hợp phức tạp hơn để giữ Cây AVL cân bằng sau bất kỳ thay đổi nào trong các nút của nó. Trong một cấu trúc không cân bằng, ít nhất một nút có hệ số cân bằng bằng 2 hoặc -2. Hãy xem làm thế nào chúng ta có thể cân bằng cây trong những tình huống này

Khi hệ số cân bằng của nút Z là 2 thì cây con có Z là gốc ở một trong hai trạng thái này, coi Y là con phải của Z

Đối với trường hợp thứ nhất, chiều cao của con bên phải của Y[X] lớn hơn chiều cao của con bên trái [T2]. Chúng ta có thể cân bằng lại cây một cách dễ dàng bằng cách xoay trái Z

Đối với trường hợp thứ hai, chiều cao của con bên phải của Y [T4] nhỏ hơn chiều cao của con bên trái [X]. Tình huống này cần sự kết hợp của các thao tác xoay

Trong trường hợp này, trước tiên chúng ta xoay Y sang phải, để cây có hình dạng giống như trường hợp trước. Sau đó, chúng ta có thể cân bằng lại cây bằng cách xoay trái Z

Ngoài ra, khi hệ số cân bằng của nút Z là -2, cây con của nó ở một trong hai trạng thái này, vì vậy chúng tôi coi Z là gốc và Y là con trái của nó

Chiều cao ở con bên trái của Y lớn hơn chiều cao ở con bên phải của nó, vì vậy chúng ta cân bằng cây với phép quay bên phải của Z

Hoặc trường hợp thứ 2 con bên phải của Y có chiều cao lớn hơn con bên trái

Vì vậy, trước hết, chúng tôi chuyển đổi nó thành hình dạng ban đầu với phép quay trái của Y, sau đó chúng tôi cân bằng cây với phép quay phải của Z

Hãy xem hoạt động tái cân bằng cho AVLTree của chúng tôi

Node rebalance[Node z] {
    updateHeight[z];
    int balance = getBalance[z];
    if [balance > 1] {
        if [height[z.right.right] > height[z.right.left]] {
            z = rotateLeft[z];
        } else {
            z.right = rotateRight[z.right];
            z = rotateLeft[z];
        }
    } else if [balance < -1] {
        if [height[z.left.left] > height[z.left.right]]
            z = rotateRight[z];
        else {
            z.left = rotateLeft[z.left];
            z = rotateRight[z];
        }
    }
    return z;
}

Chúng tôi sẽ sử dụng cân bằng lại sau khi chèn hoặc xóa một nút cho tất cả các nút trong đường dẫn từ nút đã thay đổi đến gốc

4. Chèn một nút

Khi chúng ta chèn một khóa vào cây, chúng ta phải xác định vị trí thích hợp của nó để chuyển các quy tắc BST. Vì vậy, chúng tôi bắt đầu từ thư mục gốc và so sánh giá trị của nó với khóa mới. Nếu khóa lớn hơn, chúng tôi tiếp tục sang bên phải - nếu không, chúng tôi chuyển sang con bên trái

Khi chúng tôi tìm thấy nút cha thích hợp, sau đó chúng tôi thêm khóa mới làm nút sang trái hoặc phải, tùy thuộc vào giá trị

Sau khi chèn nút, chúng tôi có BST, nhưng nó có thể không phải là Cây AVL. Do đó, chúng tôi kiểm tra các yếu tố cân bằng và cân bằng lại BST cho tất cả các nút trong đường dẫn từ nút mới đến gốc

Chúng ta hãy xem thao tác chèn

Node insert[Node node, int key] {
    if [node == null] {
        return new Node[key];
    } else if [node.key > key] {
        node.left = insert[node.left, key];
    } else if [node.key < key] {
        node.right = insert[node.right, key];
    } else {
        throw new RuntimeException["duplicate Key!"];
    }
    return rebalance[node];
}

Điều quan trọng cần nhớ là một khóa là duy nhất trong cây — không có hai nút nào chia sẻ cùng một khóa

Độ phức tạp thời gian của thuật toán chèn là một hàm của chiều cao. Vì cây của chúng ta cân bằng, chúng ta có thể giả sử rằng độ phức tạp thời gian trong trường hợp xấu nhất là O[log[N]]

5. Xóa một nút

Để xóa một khóa khỏi cây, trước tiên chúng ta phải tìm nó trong BST

Sau khi chúng tôi tìm thấy nút [được gọi là Z], chúng tôi phải giới thiệu ứng cử viên mới để thay thế nó trong cây. Nếu Z là lá, ứng cử viên trống. Nếu Z chỉ có một con, thì đứa trẻ này là ứng cử viên, nhưng nếu Z có hai con, quá trình này sẽ phức tạp hơn một chút

Giả sử con phải của Z có tên là Y. Đầu tiên, chúng tôi tìm nút ngoài cùng bên trái của Y và gọi nó là X. Sau đó, ta đặt giá trị mới của Z bằng giá trị của X và tiếp tục xóa X khỏi Y

Cuối cùng, chúng tôi gọi phương thức cân bằng lại ở cuối để giữ BST là Cây AVL

Đây là phương pháp xóa của chúng tôi

Node delete[Node node, int key] {
    if [node == null] {
        return node;
    } else if [node.key > key] {
        node.left = delete[node.left, key];
    } else if [node.key < key] {
        node.right = delete[node.right, key];
    } else {
        if [node.left == null || node.right == null] {
            node = [node.left == null] ? node.right : node.left;
        } else {
            Node mostLeftChild = mostLeftChild[node.right];
            node.key = mostLeftChild.key;
            node.right = delete[node.right, node.key];
        }
    }
    if [node != null] {
        node = rebalance[node];
    }
    return node;
}

Độ phức tạp thời gian của thuật toán xóa là một hàm của chiều cao của cây. Tương tự như phương pháp chèn, chúng ta có thể giả sử rằng độ phức tạp thời gian trong trường hợp xấu nhất là O[log[N]]

6. Tìm kiếm một nút

Tìm kiếm một nút trong Cây AVL cũng giống như với bất kỳ BST nào

Bắt đầu từ gốc của cây và so sánh khóa với giá trị của nút. Nếu khóa bằng giá trị, hãy trả về nút. Nếu khóa lớn hơn thì tìm từ con bên phải, ngược lại tiếp tục tìm từ con bên trái

Độ phức tạp thời gian của tìm kiếm là một hàm của chiều cao. Chúng ta có thể giả định rằng độ phức tạp thời gian trong trường hợp xấu nhất là O[log[N]]