Cây AVL: Hướng dẫn đầy đủ kèm triển khai bằng Python

Mất cân bằng trong Cây Tìm kiếm Nhị phân

Cây tìm kiếm nhị phân (BST) là một dạng cây nhị phân cấu trúc dữ liệu tổ chức dữ liệu theo một quy tắc sắp xếp cụ thể. Mỗi nút chứa một giá trị và có liên kết tới tối đa hai nút khác: trái và phải. Trong BST, quy tắc là giá trị của nút con trái phải nhỏ hơn giá trị nút cha, và giá trị của nút con phải phải lớn hơn.

BST có thể rất hiệu quả để tìm giá trị cụ thể vì cho phép loại bỏ một phần lớn của cây trong quá trình tìm kiếm. Ví dụ, nếu chúng ta đang tìm giá trị một trong cây trên, ta có thể bỏ qua tất cả các nút bên phải của sáu. Bởi vì tính chất sắp xếp đảm bảo tất cả các giá trị đó đều lớn hơn sáu.

Lý tưởng nhất, mỗi nút nên chia dữ liệu làm đôi, để mỗi bước đi xuống cây loại bỏ một nửa giá trị. Điều này dẫn đến tra cứu cực nhanh. Tuy nhiên, tùy thuộc vào thứ tự chèn, có thể dẫn đến cây mất cân bằng, không chia tách dữ liệu hiệu quả. Chẳng hạn, chèn giá trị từ nhỏ đến lớn sẽ tạo ra một cây tuyến tính, không tốt hơn một danh sách.

Cây AVL là gì

Cây AVL là một cây tìm kiếm nhị phân với tính chất bổ sung sau:

Với mỗi nút, chiều cao của cây con trái và cây con phải chênh lệch nhiều nhất là một.

Phân tích định nghĩa này, cây con trái của một nút bao gồm tất cả các nút bên trái nó, trong khi cây con phải bao gồm tất cả các nút bên phải. Chiều cao của cây được định nghĩa là độ dài đường đi dài nhất từ nút gốc (nút trên cùng) tới bất kỳ lá hậu duệ nào (nút không có con).

Hệ số cân bằng của một nút được tính là chênh lệch chiều cao giữa cây con trái và cây con phải của nó:

balance(N) = height(cây con trái của N) - height(cây con phải của N)

Ví dụ, balance(6) = 1 - 3 = -2.

Trong sơ đồ, nút 6 có hệ số cân bằng bằng -2, cho thấy cây không đáp ứng tiêu chí của cây AVL. Để một cây được phân loại là cây AVL, hệ số cân bằng của mỗi nút phải là -1, 0 hoặc 1.

Vì sao dùng cây AVL

Hiệu quả truy vấn trong cây tìm kiếm nhị phân phụ thuộc vào chiều cao của cây. Trong kịch bản xấu nhất, số nút cần kiểm tra bằng chiều cao của cây. Vấn đề then chốt với BST là chiều cao cây có thể bằng số lượng nút, nghĩa là một truy vấn có thể phải kiểm tra từng nút một.

Gọi M(h) là số nút tối thiểu cần thêm vào một cây tìm kiếm nhị phân để đạt chiều cao h. Với BST đơn giản, ta nhận thấy M(h) = h, tức ta có thể đạt chiều cao h chỉ với h nút. Điều này ngụ ý chiều cao của BST có thể tăng tuyến tính theo số nút, dẫn đến thời gian truy vấn tỷ lệ với kích thước bộ dữ liệu.

Chứng minh cây AVL có chiều cao logarit

Xét số nút tối thiểu, M(h), cần để tạo một cây AVL có chiều cao h. Vì là cây AVL, cần lưu ý hệ số cân bằng của mọi nút chỉ có thể là -1, 0 hoặc 1.

Tuy nhiên, với giả định cây có ít nút nhất để đạt chiều cao h, nút gốc không thể có cân bằng 0. Nếu có, ta có thể bỏ bớt một nút ở bên trái hoặc bên phải để đạt cân bằng -1 hoặc 1, vẫn tạo ra một cây AVL hợp lệ.

Giả sử cân bằng của gốc là 1 (lý luận tương tự nếu cân bằng là -1). Điều này ngụ ý cấu trúc cây như sau:

Mặt khác, cả cây con trái và phải cũng phải là cây AVL, mỗi cây có số nút tối thiểu cần thiết cho chiều cao tương ứng của chúng (nếu không, có thể loại bỏ thêm nút). Tổng số nút bằng 1 (cho gốc) cộng số nút ở cây con trái cộng số nút ở cây con phải.

M(h) = 1 + (nút ở L) + (nút ở R) = 1 + M(h - 1) + M(h - 2)

Khi chiều cao tăng, ta cần thêm nhiều nút hơn để đạt chiều cao đó. Do đó:

M(h - 1) > M(h - 2)

Kết hợp hai điều trên, ta có thể nói rằng:

M(h) = 1 + M(h - 1) + M(h - 2) > 1 + 2 × M(h - 2) > 2 × M(h - 2)

Ta có thể áp dụng điều này h/2 lần cho đến khi đạt M(1) = 1 hoặc M(2) = 2:

M(h) > 2 × M(h - 2) > 2 × 2 × M(h - 4) > 2 × 2 × 2 × M(h - 6) > … > 2(h/2)

Để rõ ràng, hình sau minh họa ví dụ cụ thể khi h = 7 và h = 6:

Kết luận rằng số nút tối thiểu trong một cây AVL có chiều cao h ít nhất là 2(h/2):

M(h) > 2(h/2)

Lấy log cơ số hai hai vế, ta được:

log2(M(h)) > log2(2(h/2)) = h/2

Do đó, nhân hai vế với hai, ta suy ra chiều cao nhiều nhất bằng hai lần log cơ số 2 của số nút:

2 × log2(M(h)) > h

Ta đã chứng minh rằng:

Chiều cao của một cây AVL chứa N nút nhiều nhất là 2 × log2(N).

Điều này cho thấy các truy vấn trong cây AVL chỉ cần kiểm tra một phần nhỏ dữ liệu. Ví dụ, với một tỷ phần tử, log xấp xỉ 30, nghĩa là ngay cả với một tỷ điểm dữ liệu, chỉ cần kiểm tra khoảng 60 điểm để tìm một mục cụ thể. Đây là cải thiện đáng kể so với BST, vốn trong kịch bản xấu nhất phải kiểm tra toàn bộ một tỷ điểm dữ liệu.

Để hiểu sâu hơn về độ phức tạp thời gian của thuật toán và sự khác nhau giữa độ phức tạp tuyến tính và logarit, hãy xem bài viết về Ký hiệu Big-O và Độ phức tạp thời gian.

Duy trì cân bằng với cây AVL

Cây AVL đảm bảo truy vấn nhanh bằng cách buộc hệ số cân bằng của mỗi nút là -1, 0 hoặc 1. Để đảm bảo cân bằng của mỗi nút được duy trì, chúng ta cần cân bằng lại cây sau khi chèn một giá trị mới.

Chèn trong BST hoạt động bằng cách đi theo đường từ gốc xuống cây. Ta đi trái khi giá trị cần chèn nhỏ hơn, và đi phải trong trường hợp ngược lại.

Một thao tác chèn làm tăng chiều cao nhiều nhất là một. Vì vậy, nếu tính chất cân bằng không còn sau khi chèn, có nghĩa là đã có một nút với cân bằng -1, giờ thành -2, hoặc nút với cân bằng 1, giờ thành 2. Trường hợp đầu tiên chính là điều xảy ra trong ví dụ trên.

Xoay đơn

Để khôi phục cân bằng, ta dựa vào thao tác xoay cây. Một xoay trái trên nút A tái cấu trúc cây bằng cách xoay A sang trái, như minh họa dưới đây:

Trong sơ đồ:

• BL là cây con trái của B
• BR là cây con phải
• AL là cây con trái của A

Lưu ý rằng sau khi xoay, thứ tự các nút vẫn hợp lệ:

1. Nút A nhỏ hơn B vì B là con phải của nó.
2. Các nút trong BL lớn hơn A vì chúng nằm bên phải A.
3. Các nút trong AL nhỏ hơn B vì chúng nhỏ hơn A.

Xoay phải hoạt động đối xứng, bằng cách xoay A sang phải.

Hãy xem ví dụ cụ thể bằng cách sửa mất cân bằng của cây sau khi chèn 19 bằng xoay trái trên nút 6.

Sau khi chèn, ta sẽ sửa mất cân bằng bằng cách xoay một nút có cân bằng -2 hoặc 2. Ở đây, hệ số cân bằng của nút 6 là -2, nghĩa là cây nghiêng về bên phải, nên ta áp dụng xoay trái (theo hướng ngược với mất cân bằng). Nếu cân bằng bằng 2, thì dùng xoay phải.

Xoay kép

Trong ví dụ trước, cây nghiêng hoàn toàn về bên phải, nên chỉ cần một lần xoay trái để khôi phục cân bằng. Tuy nhiên, một số trường hợp có dạng zíc-zắc, nơi cây nghiêng về một phía nhưng cây con lại nghiêng về phía đối diện. Để thấy điều này, hãy quay lại cây ban đầu trước khi chèn 19 và thay vào đó chèn 7:

Trong trường hợp này, cây vẫn nghiêng phải, nhưng cây con gốc tại 10 lại nghiêng trái. Khi đó, trước hết ta cần xoay nút 10 sang phải:

Lưu ý nút B không có con phải. Chúng tôi vẫn hiển thị bằng màu xanh trong sơ đồ để dễ hình dung. 

Sau khi xoay phải, ta quay lại trường hợp trước đó, nơi một lần xoay trái trên 6 sẽ khôi phục cân bằng:

Cách triển khai cây AVL trong Python

Bắt đầu với việc triển khai nút.

Triển khai nút

Mỗi nút của cây có năm thuộc tính:

• Giá trị nó lưu trữ (self.value)
• Nút cha (self.parent)
• Con trái (self.left)
• Con phải (self.right)
• Chiều cao của cây con gốc tại nút đó (self.height)

class Node:
  def __init__(self, value, parent = None):
    self.value = value
    self.parent = parent
    self.left = None
    self.right = None
    self.height = 1Được hỗ trợ bởi

Chúng ta dùng giá trị None để biểu diễn nút thiếu. height mặc định đặt là 1 vì một cây chỉ gồm một nút có chiều cao là 1. 

Để hỗ trợ việc triển khai cây, ta bổ sung một số phương thức cho lớp Node.

# Inside the Node class
  def left_height(self):
    # Get the heigth of the left subtree
    return 0 if self.left is None else self.left.height
  
  def right_height(self):
    # Get the height of the right subtree
    return 0 if self.right is None else self.right.height
  def balance_factor(self):
    # Get the balance factor
    return self.left_height() - self.right_height()
  def update_heigth(self):
    # Update the heigth of this node
    self.height = 1 + max(self.left_height(),self.right_height())
    
  def set_left(self, node):
    # Set the left child
    self.left = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  
  def set_right(self, node):
    # Set the right child
    self.right = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  def is_left_child(self):
    # Check whether this node is a left child
    return self.parent is not None and self.parent.left == self
  
  def is_right_child(self):
    # Check whether this node is a right child
    return self.parent is not None and self.parent.right == selfĐược hỗ trợ bởi

Lưu ý ta dùng các phương thức .set_left() và .set_right() để gán con trái và con phải tương ứng. Lý do dùng các phương thức này, thay vì sửa trực tiếp thuộc tính self.left và self.right, là bất cứ khi nào thay đổi con, cần cập nhật cả nút cha của con mới cũng như chiều cao của nút.

Triển khai cây AVL

Cây AVL duy trì một tham số là nút gốc của cây, tức nút trên cùng.

class AVLTree:
  def __init__(self):
    self.root = NoneĐược hỗ trợ bởi

Để duy trì cân bằng của cây, ta cần triển khai các phép xoay trái và phải. Hãy xem lại xoay trái được minh họa thế nào trong sơ đồ:

# Inside the AVLTree class
  
  def rotate_left(self, a):
    b = a.right
    # 1. The new right child of A becomes the left child of B
    a.set_right(b.left)
    # 2. The new left child of B becomes A
    b.set_left(a)
    return b # 3. Return B to replace A with itĐược hỗ trợ bởi

Xoay phải được triển khai đối xứng:

# Inside the AVLTree class
  
  def rotate_right(self, a):
    b = a.left
    a.set_left(b.right)
    b.set_right(a)
    return bĐược hỗ trợ bởi

Dùng các phép xoay, ta có thể cân bằng lại cây. Một nút cần cân bằng lại khi hệ số cân bằng đạt 2 (cây nghiêng trái) hoặc -2 (cây nghiêng phải). Tổng cộng có bốn kịch bản cần xét:

Ta triển khai bốn trường hợp này trong phương thức .rebalance().

# Inside the AVLTree class
  
  def rebalance(self, node):
    if node is None:
      # Empty tree, no rebalancing needed
      return None
    balance = node.balance_factor()
    if abs(balance) <= 1:
      # The node is already balanced, no rebalancing needed
      return node
    if balance == 2: 
      # Cases 1 and 2, the tree is leaning to the left
      if node.left.balance_factor() == -1: 
        # Case 2, we first do a left rotation
        node.set_left(self.rotate_left(node.left))
      return self.rotate_right(node)
    # Balance must be -2
    # Cases 3 and 4, the tree is leaning to the left
    if node.right.balance_factor() == 1:
      # Case 4, we first do a right rotation
      node.set_right(self.rotate_right(node.right)) 
    return self.rotate_left(node)Được hỗ trợ bởi

Lưu ý trong mỗi trường hợp, phương thức trả về nút gốc của cây con vừa được cân bằng. Gốc cây con mới này sẽ được dùng sau đó để cập nhật con trong quá trình cân bằng lại.

Thêm một nút vào cây AVL tương tự quá trình trong BST thông thường, với bước bổ sung là khôi phục cân bằng sau khi chèn nút. Để thêm một nút trong BST, ta bắt đầu ở gốc và đi xuống cây. Ở mỗi bước, so sánh giá trị cần thêm với giá trị nút hiện tại. Nếu giá trị cần thêm nhỏ hơn, đi trái; ngược lại đi phải. Khi đi xuống, ta theo dõi nút cha để có thể chèn nút mới làm con của nó.

Khi tới một nút trống, có hai trường hợp:

1. Nút cha là None thì cây rỗng nên nút mới là gốc mới của cây.
2. Đã tìm được nút cha nên cần đặt nút mới làm con trái hoặc con phải, tùy theo giá trị nút.

# Inside the AVLTree class
  def add(self, value):
    self.size += 1
    parent = None
    current = self.root
    while current is not None:
      parent = current
      if value < current.value:
        # Value to insert is smaller than node value, go left
        current = current.left
      else:
        # Value to insert is larger than node value, go right
        current = current.right
    # We found the parent, create the new node
    new_node = Node(value, parent)
    # Case 1: The parent is None so the new node is the root
    if parent is None:
      self.root = new_node
    else:
      # Case 2: Set the new node as a child of the parent
      if value < parent.value:
        parent.left = new_node
      else:
        parent.right = new_node
    # After a new node is added, we need to restore balance
    self.restore_balance(new_node)Được hỗ trợ bởi

Điểm khác biệt duy nhất giữa phương thức .add() của BST và cây AVL nằm ở bước cuối. Đó là đi ngược lên cây và cân bằng lại các nút, bắt đầu từ nút vừa thêm tới gốc, và cân bằng từng nút bằng phương thức .rebalance().

# Inside the AVLTree class
  def restore_balance(self, node):
    current = node
    # Go up the tree and rebalance left and right children
    while current is not None:
      current.set_left(self.rebalance(current.left))
      current.set_right(self.rebalance(current.right))
      current.update_heigth()
      current = current.parent
    self.root = self.rebalance(self.root)
    self.root.parent = NoneĐược hỗ trợ bởi

Lưu ý phương thức .rebalance() không làm gì khi nút đã cân bằng — nó chỉ trả về chính nút đó. Do vậy, khi đi ngược lên cây, ta có thể gọi nó cho cả hai phía, dù chỉ một phía có thể mất cân bằng. Lời gọi còn lại sẽ giữ nguyên cây.

Hãy nhớ rằng ta triển khai .rebalance() để trả về gốc (có thể) mới của cây con. Lý do là để ta có thể cập nhật con trái và con phải của các nút hiện tại khi đi lên khôi phục cân bằng.

Sơ đồ sau minh họa các bước của .restore_balance() khi đi lên cây.

Trong ví dụ này, đầu tiên ta thêm nút 8. Sau đó, quá trình khôi phục cân bằng bắt đầu tại nút này và đi ngược lên cây, kiểm tra và cân bằng lại con trái và phải của mỗi nút gặp phải. Quá trình tiếp tục cho tới khi đạt nút 10. Cho tới điểm này, không lời gọi nào của .rebalance() có hiệu lực, vì các nút vẫn cân bằng.

Tuy nhiên, khi tới nút 10, quan sát thấy con trái của nó, nút 7, có hệ số cân bằng -2, cần cân bằng lại. Do đó, gọi .rebalance(7), kết quả là thay thế con trái của nút 10 bằng gốc mới của cây con trái, nút 8, qua đó khôi phục cân bằng cho cây.

Các thao tác bổ sung của cây AVL

Ngoài thêm và xóa phần tử trong khi duy trì cân bằng, cây AVL còn hỗ trợ một số thao tác thiết yếu khác.

Giá trị nhỏ nhất và lớn nhất

Nhờ tính có thứ tự của BST, giá trị nhỏ nhất nằm ở nút ngoài cùng bên trái của cây, trong khi giá trị lớn nhất nằm ở nút ngoài cùng bên phải.

Chúng tôi đã triển khai hai hàm trợ giúp xác định nút ngoài cùng bên trái và ngoài cùng bên phải bắt đầu từ một nút cho trước. Các hàm này hữu ích để hỗ trợ việc triển khai xóa nút.

# Inside the AVLTree class
  
  def leftmost(self, starting_node):
    # Find the leftmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.left
    return previous
  def minimum(self):
    # Return the minimum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.leftmost(self.root).valueĐược hỗ trợ bởi

# Inside the AVLTree class
 
  def rightmost(self, starting_node):
    # Find the rightmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.right
    return previous
  
  def maximum(self):
    # Fidn the maximum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.rightmost(self.root).valueĐược hỗ trợ bởi

Contains

Để xác định cây có chứa một giá trị cụ thể hay không, ta tận dụng tính có thứ tự của cây để dẫn dắt việc tìm kiếm. Bắt đầu từ gốc, đi sang trái nếu giá trị cần tìm nhỏ hơn nút hiện tại và sang phải nếu lớn hơn. Nếu đi đến cuối cây mà vẫn không tìm thấy giá trị mong muốn, tức là giá trị đó không có trong cây.

Để hỗ trợ quá trình này, ta triển khai một phương thức trợ giúp gọi là .locate_node(). Phương thức này đặc biệt hữu ích không chỉ cho việc tìm kiếm mà còn cho các thao tác như xóa giá trị khỏi cây. Ngoài ra, ta dùng phương thức .__contains__(), cho phép dùng toán tử in để đơn giản hóa việc kiểm tra sự hiện diện của một giá trị trong cây.

# Inside the AVLTree class

  def locate_node(self, value):

    # Returns the node containing a given value or None if no

    # such node exists

    current = self.root

    while current is not None:

      if value == current.value:

        return current

      if value < current.value:

        current = current.left

      else:

        current = current.right

    return None

  def __contains__(self, value):

    node = self.locate_node(value)

    return node is not NoneĐược hỗ trợ bởi

Xóa

Xóa một nút trong cây AVL có thể đặc biệt thách thức khi nút đó nằm ở giữa cây. Nếu nút là lá, nghĩa là không có con, ta có thể dễ dàng xóa bằng cách đặt con trái hoặc con phải của nút cha thành None tùy việc nút là con trái hay con phải.

Một trường hợp đặc biệt xảy ra khi nút cần xóa là gốc của cây. Khi đó, ta có thể xóa nút bằng cách đặt gốc thành None.

# Inside the AVLTree class

  def delete_leaf(self, node):

    if node.parent is None:

      self.root = None

    elif node.is_left_child():

      node.parent.left = None

      node.parent = None

    else:

      node.parent.right = None

      node.parent = NoneĐược hỗ trợ bởi

Để xóa một giá trị khỏi cây AVL, trước tiên ta phải tìm nút chứa giá trị đó bằng phương thức .locate_node(). Khi đã định vị nút, ta có thể xóa bằng phương thức .delete_leaf() nếu nó là nút lá. Nếu không phải nút lá, việc xóa trực tiếp sẽ phá vỡ cấu trúc cây. Để xử lý, ta tìm một nút thay thế phù hợp. Nếu nút cần xóa có con trái, ta chọn nút ngoài cùng bên phải trong cây con trái. Cách này đảm bảo cây duy trì thứ tự.

Sơ đồ dưới đây minh họa việc loại bỏ nút 10 khỏi cây. Vì nó có con trái, ta thay thế bằng nút ngoài cùng bên phải trong cây con trái. Sau khi thay thế, điều quan trọng là cân bằng lại cây, bắt đầu từ nút cha của nút vừa thay thế.

Trong ví dụ này, nút thay thế là một nút lá. Tuy nhiên, nếu nút thay thế có con, cần gán lại chúng cho nút cha của nút thay thế. Vì nút thay thế là nút cực trị (ngoài cùng bên trái hoặc ngoài cùng bên phải), nó chỉ có thể có tối đa một con. Do đó, việc gán lại này luôn khả thi.

# Inside the AVLTree class

  def delete(self, value):

    # Delete a value from the tree

    node = self.locate_node(value)

    if node is None:

      raise Exception("Value not stored in tree")

    replacement = None

    rebalance_node = node.parent

    if node.left is not None:

      # There's a left child so we replace with rightmost node

      replacement = self.rightmost(node.left)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.left)

      else:

        replacement.parent.set_right(replacement.left)

    elif node.right is not None:

      # There's a right child so we replace with the leftmost node

      replacement = self.leftmost(node.right)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.right)

      else:

        replacement.parent.set_right(replacement.right)

    if replacement:

      # We found a replacement so replace the value

      node.value = replacement.value

      rebalance_node = replacement.parent

    else:

      # No replacement so it means the node to delete is a leaf

      self.delete_leaf(node)

    if rebalance_node is not None:

      self.restore_balance(rebalance_node)Được hỗ trợ bởi

Truy vấn khoảng

Truy vấn khoảng liên quan đến việc xác định tất cả các giá trị nằm giữa hai giá trị xác định. Nhờ tính có thứ tự của cây AVL, ta có thể tìm các giá trị này hiệu quả.

Để tìm tất cả các giá trị trong khoảng được xác định bởi cận dưới lb và cận trên ub, ta sử dụng cách tiếp cận đệ quy để tìm kiếm cây. Với mỗi nút gặp phải, nếu giá trị của nó nằm trong khoảng này, ta đưa vào kết quả. Sau đó, tiếp tục khám phá cả cây con trái và phải để tìm tiếp.

Ta bỏ qua cây con trái nếu giá trị của nút nhỏ hơn cận dưới vì tất cả giá trị trong cây con trái đều nhỏ hơn giá trị của nút. Tương tự, ta bỏ qua cây con phải nếu giá trị của nút lớn hơn cận trên, vì tất cả giá trị trong cây con phải sẽ lớn hơn giá trị của nút.

  def search(self, node, lb, ub, results):

    # Search for values between lower bound and upper bound

    if node is None:

      return

    if lb <= node.value and node.value <= ub:

      results.append(node.value)

    if node.value >= lb:

      self.search(node.left, lb, ub, results)

    if node.value <= ub:

      self.search(node.right, lb, ub, results)

  def range_query(self, lb, ub):

    # Search for values between lower bound and upper bound

    results = []

    self.search(self.root, lb, ub, results)

    return resultsĐược hỗ trợ bởi

Các cây tự cân bằng khác

Chúng ta đã triển khai một cây AVL có thể thực hiện các thao tác sau:

• Thêm một giá trị
• Xóa một giá trị
• Tra cứu một giá trị
• Truy vấn giá trị nhỏ nhất và lớn nhất
• Truy vấn tất cả giá trị nằm giữa hai giá trị

Gói avltree cung cấp một triển khai Python phản ánh các khả năng này.

Các cây tìm kiếm nhị phân tự cân bằng khác như cây đỏ-đen, cây splay và B-tree cũng cung cấp các chức năng tương tự. Nhìn chung, hiệu năng của chúng tương đương trong hầu hết ứng dụng, vì tất cả đều duy trì chiều cao bảo đảm dạng logarit. Tuy nhiên, cây AVL cân bằng tinh hơn, tối ưu hóa truy vấn tìm kiếm với cái giá là chèn có thể chậm hơn do yêu cầu cân bằng nghiêm ngặt.

Cây splay đặc biệt hiệu quả trong các kịch bản mà phần tử vừa được truy cập thường xuyên được dùng lại, khiến chúng là lựa chọn tuyệt vời cho bộ nhớ đệm (cache).

B-tree được thiết kế đặc thù để hoạt động hiệu quả trên đĩa thay vì trong bộ nhớ, rất hữu ích khi quản lý bộ dữ liệu lớn vượt quá khả năng bộ nhớ, như khi tạo chỉ mục cơ sở dữ liệu.

Các cải tiến tiếp theo

Có nhiều cách để cải thiện triển khai của chúng ta. Dưới đây là một vài gợi ý bài tập để đào sâu hiểu biết về cây AVL:

• Trong triển khai hiện tại, các nút chỉ lưu một giá trị. Để dùng làm chỉ mục cơ sở dữ liệu, cần lưu trữ cả dòng dữ liệu vì giá trị sẽ tương ứng với một cột của bảng. Ta có thể nâng cấp triển khai để cây AVL hoạt động tương tự từ điển, ánh xạ giá trị tới các dòng tương ứng.
• Triển khai của chúng ta không hỗ trợ giá trị trùng lặp. Tuy nhiên, có thể chỉnh sửa để cho phép nhiều nút có cùng giá trị.
• Thông thường, cây AVL được triển khai theo cách đệ quy. Chúng tôi chọn tránh cách này để không cần hiểu sâu về đệ quy. Mặc dù triển khai đệ quy thường thanh thoát và cô đọng hơn, chúng đòi hỏi nắm vững khái niệm đệ quy.

Kết luận

BST là một dạng cấu trúc dữ liệu cây nhị phân tổ chức dữ liệu theo một trật tự cụ thể. Cách tổ chức này cho phép tránh phải kiểm tra toàn bộ dữ liệu khi tìm kiếm giá trị cụ thể. Tuy nhiên, BST có thể mất cân bằng, dẫn đến hiệu năng suy giảm, và trong một số trường hợp có thể phải kiểm tra toàn bộ dữ liệu.

Cây AVL giải quyết vấn đề này bằng cách áp đặt các thuộc tính cân bằng bổ sung thông qua các phép xoay. Những thuộc tính này đảm bảo chiều cao cây duy trì dạng logarit so với kích thước bộ dữ liệu, mang lại cải thiện đáng kể.

Độ phức tạp thời gian dạng logarit là một bước tiến lớn so với tuyến tính, khiến cây AVL cực kỳ hiệu quả cho việc xử lý truy vấn. Ngay cả với bộ dữ liệu hàng tỷ bản ghi, cây AVL chỉ cần kiểm tra một vài điểm dữ liệu để định vị phần tử, giúp hiệu quả hơn rất nhiều.