Xây dựng cây tìm kiếm nhị phân cân bằng

Question

Có phương pháp xây dựng cây tìm kiếm nhị phân cân bằng không?

Ví dụ:

1 2 3 4 5 6 7 8 9 

     5 
    /\ 
    3 etc 
    /\ 
    2 4 
/
1 

Tôi đang nghĩ đến có một phương pháp để làm điều này, mà không sử dụng các loại cây tự cân bằng phức tạp hơn. Nếu không, tôi có thể tự làm điều đó, nhưng có thể ai đó đã làm điều này rồi :)

---

Cảm ơn câu trả lời! Đây là mã python thức:

def _buildTree(self, keys): 
    if not keys: 
     return None 

    middle = len(keys) // 2 

    return Node(
     key=keys[middle], 
     left=self._buildTree(keys[:middle]), 
     right=self._buildTree(keys[middle + 1:]) 
     ) 

Answer 1

Đối với mỗi cây con:

• Tìm các yếu tố giữa cây con và đặt rằng ở phía trên cùng của cây.
• Tìm tất cả các phần tử trước phần tử ở giữa và sử dụng thuật toán này đệ quy để lấy cây con trái.
• Tìm tất cả các phần tử sau phần tử ở giữa và sử dụng thuật toán này một cách đệ quy để có được cây con phù hợp.

Nếu bạn sắp xếp các phần tử của mình trước (như trong ví dụ), việc tìm phần tử trung gian của cây con có thể được thực hiện trong thời gian không đổi.

Đây là thuật toán đơn giản để xây dựng cây cân bằng một lần. Nó không phải là một thuật toán cho một cây tự cân bằng.

Dưới đây là một số mã nguồn trong C# mà bạn có thể thử cho chính mình:

public class Program 
{ 
    class TreeNode 
    { 
     public int Value; 
     public TreeNode Left; 
     public TreeNode Right; 
    } 

    TreeNode constructBalancedTree(List<int> values, int min, int max) 
    { 
     if (min == max) 
      return null; 

     int median = min + (max - min)/2; 
     return new TreeNode 
     { 
      Value = values[median], 
      Left = constructBalancedTree(values, min, median), 
      Right = constructBalancedTree(values, median + 1, max) 
     }; 
    } 

    TreeNode constructBalancedTree(IEnumerable<int> values) 
    { 
     return constructBalancedTree(
      values.OrderBy(x => x).ToList(), 0, values.Count()); 
    } 

    void Run() 
    { 
     TreeNode balancedTree = constructBalancedTree(Enumerable.Range(1, 9)); 
     // displayTree(balancedTree); // TODO: implement this! 
    } 

    static void Main(string[] args) 
    { 
     new Program().Run(); 
    } 
} 

Answer 2

Bài viết này giải thích một cách chi tiết:

Tree Tái cân bằng trong tối ưu thời gian và không gian
http://www.eecs.umich.edu/~qstout/abs/CACM86.html

Ngoài ra ở đây:

One- Time Binary Search Tree Balancing: Thuật toán Ngày/Stout/Warren (DSW)
http://penguin.ewu.edu/~trolfe/DSWpaper/

Nếu bạn thực sự muốn thực hiện việc này một cách nhanh chóng, bạn cần một cây tự cân bằng.

Nếu bạn chỉ muốn xây dựng một cây đơn giản, mà không cần phải đi đến những rắc rối của việc cân bằng nó, chỉ cần ngẫu nhiên các yếu tố trước khi chèn chúng vào cây.

Answer 3

Tận dụng trung bình của dữ liệu của bạn (hay chính xác hơn, các yếu tố gần nhất trong mảng của bạn đến trung bình) thư mục gốc của cây. Và theo cách đệ quy.