Hướng dẫn binary search tree python tutorial - hướng dẫn python cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân là một cấu trúc dữ liệu nhanh chóng cho phép chúng tôi duy trì danh sách các số được sắp xếp.

• Nó được gọi là cây nhị phân vì mỗi nút cây có tối đa hai đứa trẻ.
• Nó được gọi là cây tìm kiếm vì nó có thể được sử dụng để tìm kiếm sự hiện diện của một số trong thời gian ____.

Các thuộc tính tách một cây tìm kiếm nhị phân với cây nhị phân thông thường là

1. Tất cả các nút của cây con trái nhỏ hơn nút gốc
2. Tất cả các nút của cây con bên phải đều nhiều hơn nút gốc
3. Cả hai con của mỗi nút cũng là BST, tức là chúng có hai thuộc tính trên

Một cây có cây con phù hợp với một giá trị nhỏ hơn gốc được hiển thị để chứng minh rằng nó không phải là cây tìm kiếm nhị phân hợp lệ

Cây nhị phân ở bên phải không phải là cây tìm kiếm nhị phân vì cây con bên phải của nút "3" chứa giá trị nhỏ hơn nó.

Có hai hoạt động cơ bản mà bạn có thể thực hiện trên cây tìm kiếm nhị phân:

---

Hoạt động tìm kiếm

Thuật toán phụ thuộc vào thuộc tính của BST rằng nếu mỗi cây con bên trái có các giá trị bên dưới gốc và mỗi cây con bên phải có các giá trị phía trên gốc.

Nếu giá trị nằm dưới gốc, chúng ta có thể nói chắc chắn rằng giá trị không nằm trong phần cây con phù hợp; Chúng ta chỉ cần tìm kiếm ở cây con bên trái và nếu giá trị nằm trên gốc, chúng ta có thể nói chắc chắn rằng giá trị không nằm trong cây con bên trái; Chúng ta chỉ cần tìm kiếm trong phần con phù hợp.

Algorithm:

If root == NULL 
    return NULL;
If number == root->data 
    return root->data;
If number < root->data 
    return search(root->left)
If number > root->data 
    return search(root->right)

Hãy để chúng tôi cố gắng hình dung điều này với một sơ đồ.

4 không được tìm thấy vì vậy, không tìm thấy cây con bên trái 84 nên không được tìm thấy, qua đường bên phải của 344 is not found so, traverse through the right subtree of 34 is not found so, traverse through the left subtree of 64 is found

Nếu giá trị được tìm thấy, chúng ta trả về giá trị để nó được truyền trong mỗi bước đệ quy như trong hình dưới đây.

Nếu bạn có thể nhận thấy, chúng tôi đã gọi tìm kiếm trả về (nút struct*) bốn lần. Khi chúng tôi trả về nút mới hoặc null, giá trị sẽ được trả về nhiều lần cho đến khi tìm kiếm (root) trả về kết quả cuối cùng.

Nếu giá trị được tìm thấy trong bất kỳ người trừ nào, nó được truyền lên để cuối cùng nó được trả lại, nếu không thì null sẽ được trả về

Nếu giá trị không được tìm thấy, cuối cùng chúng ta cũng đến được với đứa trẻ bên trái hoặc bên phải của một nút lá là null và nó được truyền và trả về.

---

Chèn hoạt động

Chèn một giá trị ở vị trí chính xác tương tự như tìm kiếm vì chúng tôi cố gắng duy trì quy tắc rằng cây con bên trái nhỏ hơn root và cây con bên phải lớn hơn root.

Chúng tôi tiếp tục đi vào cây con bên phải hoặc cây con bên trái tùy thuộc vào giá trị và khi chúng tôi đạt đến một điểm con bên trái hoặc bên phải là null, chúng tôi đặt nút mới ở đó.

Algorithm:

If node == NULL 
    return createNode(data)
if (data < node->data)
    node->left  = insert(node->left, data);
else if (data > node->data)
    node->right = insert(node->right, data);  
return node;

Thuật toán không đơn giản như vẻ ngoài của nó. Chúng ta hãy cố gắng hình dung cách chúng ta thêm một số vào một BST hiện có.

43 Vì vậy, ngang qua đứa con phải của 844>3 so, transverse through the right child of 84<6 so, transverse through the left child of 6 Insert 4 as a left child of 6

Chúng tôi đã gắn nút nhưng chúng tôi vẫn phải thoát khỏi chức năng mà không gây ra bất kỳ thiệt hại nào cho phần còn lại của cây. Đây là nơi return node; ở cuối có ích. Trong trường hợp NULL, nút mới được tạo được trả về và gắn vào nút cha, nếu không thì cùng một nút được trả về mà không có bất kỳ thay đổi nào khi chúng tôi đi lên cho đến khi chúng tôi trở về gốc.

Điều này đảm bảo rằng khi chúng ta di chuyển trở lại cây, các kết nối nút khác không được thay đổi.

Hình ảnh cho thấy tầm quan trọng của việc trả lại phần tử gốc ở cuối để các phần tử không mất vị trí của chúng trong bước đệ quy hướng lên.

---

Hoạt động xóa

Có ba trường hợp để xóa một nút từ cây tìm kiếm nhị phân.

Trường hợp tôi

Trong trường hợp đầu tiên, nút bị xóa là nút lá. Trong trường hợp như vậy, chỉ cần xóa nút khỏi cây.

4 là để xóa nútDelete the node

Trường hợp II

Trong trường hợp thứ hai, nút bị xóa đã xóa có một nút con duy nhất. Trong trường hợp như vậy, hãy làm theo các bước dưới đây:

1. Thay thế nút đó bằng nút con của nó.
2. Hủy bỏ nút trẻ khỏi vị trí ban đầu của nó.

6 sẽ được xóacopy the value of its child to the node and delete the child Final tree

Trường hợp III

Trong trường hợp thứ ba, nút bị xóa có hai con. Trong trường hợp như vậy, hãy làm theo các bước dưới đây:

1. Nhận được người kế thừa trước của nút đó.
2. Thay thế nút bằng cách kết hợp trước.
3. Loại bỏ người kế thừa trước khỏi vị trí ban đầu của nó.

3 sẽ được xóaCopy the value of the inorder successor (4) to the nodeDelete the inorder successor

---

Ví dụ về Python, Java và C/C ++

# Binary Search Tree operations in Python


# Create a node
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


# Inorder traversal
def inorder(root):
    if root is not None:
        # Traverse left
        inorder(root.left)

        # Traverse root
        print(str(root.key) + "->", end=' ')

        # Traverse right
        inorder(root.right)


# Insert a node
def insert(node, key):

    # Return a new node if the tree is empty
    if node is None:
        return Node(key)

    # Traverse to the right place and insert the node
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    return node


# Find the inorder successor
def minValueNode(node):
    current = node

    # Find the leftmost leaf
    while(current.left is not None):
        current = current.left

    return current


# Deleting a node
def deleteNode(root, key):

    # Return if the tree is empty
    if root is None:
        return root

    # Find the node to be deleted
    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif(key > root.key):
        root.right = deleteNode(root.right, key)
    else:
        # If the node is with only one child or no child
        if root.left is None:
            temp = root.right
            root = None
            return temp

        elif root.right is None:
            temp = root.left
            root = None
            return temp

        # If the node has two children,
        # place the inorder successor in position of the node to be deleted
        temp = minValueNode(root.right)

        root.key = temp.key

        # Delete the inorder successor
        root.right = deleteNode(root.right, temp.key)

    return root


root = None
root = insert(root, 8)
root = insert(root, 3)
root = insert(root, 1)
root = insert(root, 6)
root = insert(root, 7)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 4)

print("Inorder traversal: ", end=' ')
inorder(root)

print("\nDelete 10")
root = deleteNode(root, 10)
print("Inorder traversal: ", end=' ')
inorder(root)

// Binary Search Tree operations in Java

class BinarySearchTree {
  class Node {
    int key;
    Node left, right;

    public Node(int item) {
      key = item;
      left = right = null;
    }
  }

  Node root;

  BinarySearchTree() {
    root = null;
  }

  void insert(int key) {
    root = insertKey(root, key);
  }

  // Insert key in the tree
  Node insertKey(Node root, int key) {
    // Return a new node if the tree is empty
    if (root == null) {
      root = new Node(key);
      return root;
    }

    // Traverse to the right place and insert the node
    if (key < root.key)
      root.left = insertKey(root.left, key);
    else if (key > root.key)
      root.right = insertKey(root.right, key);

    return root;
  }

  void inorder() {
    inorderRec(root);
  }

  // Inorder Traversal
  void inorderRec(Node root) {
    if (root != null) {
      inorderRec(root.left);
      System.out.print(root.key + " -> ");
      inorderRec(root.right);
    }
  }

  void deleteKey(int key) {
    root = deleteRec(root, key);
  }

  Node deleteRec(Node root, int key) {
    // Return if the tree is empty
    if (root == null)
      return root;

    // Find the node to be deleted
    if (key < root.key)
      root.left = deleteRec(root.left, key);
    else if (key > root.key)
      root.right = deleteRec(root.right, key);
    else {
      // If the node is with only one child or no child
      if (root.left == null)
        return root.right;
      else if (root.right == null)
        return root.left;

      // If the node has two children
      // Place the inorder successor in position of the node to be deleted
      root.key = minValue(root.right);

      // Delete the inorder successor
      root.right = deleteRec(root.right, root.key);
    }

    return root;
  }

  // Find the inorder successor
  int minValue(Node root) {
    int minv = root.key;
    while (root.left != null) {
      minv = root.left.key;
      root = root.left;
    }
    return minv;
  }

  // Driver Program to test above functions
  public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();

    tree.insert(8);
    tree.insert(3);
    tree.insert(1);
    tree.insert(6);
    tree.insert(7);
    tree.insert(10);
    tree.insert(14);
    tree.insert(4);

    System.out.print("Inorder traversal: ");
    tree.inorder();

    System.out.println("\n\nAfter deleting 10");
    tree.deleteKey(10);
    System.out.print("Inorder traversal: ");
    tree.inorder();
  }
}

// Binary Search Tree operations in C

#include 
#include 

struct node {
  int key;
  struct node *left, *right;
};

// Create a node
struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// Inorder Traversal
void inorder(struct node *root) {
  if (root != NULL) {
    // Traverse left
    inorder(root->left);

    // Traverse root
    printf("%d -> ", root->key);

    // Traverse right
    inorder(root->right);
  }
}

// Insert a node
struct node *insert(struct node *node, int key) {
  // Return a new node if the tree is empty
  if (node == NULL) return newNode(key);

  // Traverse to the right place and insert the node
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);

  return node;
}

// Find the inorder successor
struct node *minValueNode(struct node *node) {
  struct node *current = node;

  // Find the leftmost leaf
  while (current && current->left != NULL)
    current = current->left;

  return current;
}

// Deleting a node
struct node *deleteNode(struct node *root, int key) {
  // Return if the tree is empty
  if (root == NULL) return root;

  // Find the node to be deleted
  if (key < root->key)
    root->left = deleteNode(root->left, key);
  else if (key > root->key)
    root->right = deleteNode(root->right, key);

  else {
    // If the node is with only one child or no child
    if (root->left == NULL) {
      struct node *temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL) {
      struct node *temp = root->left;
      free(root);
      return temp;
    }

    // If the node has two children
    struct node *temp = minValueNode(root->right);

    // Place the inorder successor in position of the node to be deleted
    root->key = temp->key;

    // Delete the inorder successor
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

// Driver code
int main() {
  struct node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 6);
  root = insert(root, 7);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 4);

  printf("Inorder traversal: ");
  inorder(root);

  printf("\nAfter deleting 10\n");
  root = deleteNode(root, 10);
  printf("Inorder traversal: ");
  inorder(root);
}

// Binary Search Tree operations in C++

#include 
using namespace std;

struct node {
  int key;
  struct node *left, *right;
};

// Create a node
struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// Inorder Traversal
void inorder(struct node *root) {
  if (root != NULL) {
    // Traverse left
    inorder(root->left);

    // Traverse root
    cout << root->key << " -> ";

    // Traverse right
    inorder(root->right);
  }
}

// Insert a node
struct node *insert(struct node *node, int key) {
  // Return a new node if the tree is empty
  if (node == NULL) return newNode(key);

  // Traverse to the right place and insert the node
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);

  return node;
}

// Find the inorder successor
struct node *minValueNode(struct node *node) {
  struct node *current = node;

  // Find the leftmost leaf
  while (current && current->left != NULL)
    current = current->left;

  return current;
}

// Deleting a node
struct node *deleteNode(struct node *root, int key) {
  // Return if the tree is empty
  if (root == NULL) return root;

  // Find the node to be deleted
  if (key < root->key)
    root->left = deleteNode(root->left, key);
  else if (key > root->key)
    root->right = deleteNode(root->right, key);
  else {
    // If the node is with only one child or no child
    if (root->left == NULL) {
      struct node *temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL) {
      struct node *temp = root->left;
      free(root);
      return temp;
    }

    // If the node has two children
    struct node *temp = minValueNode(root->right);

    // Place the inorder successor in position of the node to be deleted
    root->key = temp->key;

    // Delete the inorder successor
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

// Driver code
int main() {
  struct node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 6);
  root = insert(root, 7);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 4);

  cout << "Inorder traversal: ";
  inorder(root);

  cout << "\nAfter deleting 10\n";
  root = deleteNode(root, 10);
  cout << "Inorder traversal: ";
  inorder(root);
}

---

Sự phức tạp của cây tìm kiếm nhị phân

Độ phức tạp về thời gian

Hoạt động	Sự phức tạp trường hợp tốt nhất	Độ phức tạp trường hợp trung bình	Sự phức tạp trường hợp xấu nhất
Tìm kiếm	O (log n)	O (log n)	Trên)
Chèn	O (log n)	O (log n)	Trên)
Chèn	O (log n)	O (log n)	Trên)

Chèn

Độ phức tạp không gian

Độ phức tạp không gian cho tất cả các hoạt động là O (N).

---

Ứng dụng cây tìm kiếm nhị phân

1. Trong lập chỉ mục đa cấp trong cơ sở dữ liệu
2. Để phân loại động
3. Để quản lý các khu vực bộ nhớ ảo trong nhân Unix

Làm thế nào để bạn thực hiện một cây tìm kiếm nhị phân trong Python?

Python có cây tìm kiếm nhị phân không?

Làm thế nào để bạn viết một cây tìm kiếm nhị phân?

Cây tìm kiếm nhị phân với ví dụ là gì?