Phân tích
Với định nghĩa của bạn của một cây nhị phân chúng ta có những điều sau đây,
Mỗi Node có một phụ huynh, L-con, và R-con .. nơi:
L < N
R > N
P > N
Chúng tôi cũng có thể làm điều này:
L < N AND R > N => L < N < R => L < R
L < N AND P > N => L < N < P => L < P
R > N AND P > N => N < MIN(P,R)
N < MIN(P,R) AND L < N => L < N < MIN(P,R)
Và bây giờ chúng ta hãy thử mở rộng nó, N.L = Left-child of N:
N.L < N
N.R > N
N.P > N
N.L.L < N.L < MIN(N, N.L.R)
N.L.R > N.L > N.L.L
N.R.L < N.R < MIN(N, N.R.R)
N.R.R > N.R > N.R.L
IF N IS N.P LEFT-CHILD: N < N.P < MIN(N.P.P, N.P.R)
IF N IS N.P RIGHT-CHILD: N > N.P.R
đề xuất giải pháp
vấn đề này có vẻ phức tạp, nhưng giải pháp của tôi sẽ được sử dụng hợp nhất phân loại sau khi chèn giá trị theo một thứ tự traversal trái Đúng-cha mẹ sẽ giúp sắp xếp hợp nhất để có được một thời gian phức tạp một nơi nào đó giữa trường hợp trung bình và tối ưu của nó, nhưng với một thủ thuật nhỏ bằng cách sử dụng so sánh tôi đã thực hiện ở trên.
Đầu tiên chúng tôi thu thập các nút cây trong một danh sách, sử dụng traversal Left-Right-phụ huynh, do thực tế là: N.L < N < MIN(N.R, N.P) và cho phụ huynh một trọng lượng cao hơn giả O(N.R) <= O(N.P) với giá trị giảm tuyến tính khi chúng tôi đi lại phía mỗi lần .. > N.R.R > N.R > N > N.L > N.L.L > .. .
Sau khi thu thập các nút cây theo thứ tự truyền tải đó, danh sách có một số khối được sắp xếp, sẽ giúp sắp xếp hợp nhất mà chúng ta sẽ sử dụng tiếp theo.
Giải pháp này làm việc trong: Time = O(n log n + n), Space = O(n)
Đây là thuật toán viết bằng Java (không kiểm tra):
private class Node Comparable<Node>
{
public Node R;
public Node L;
public int value;
public Node (Node L, int val, Node R)
{
this.L = L;
this.value = val;
this.R = R;
}
@Override
public int compareTo(Node other)
{
return ((other != null) ? (this.value-other.value) : 0);
}
}
class Main
{
private static Node head;
private static void recursive_collect (Node n, ArrayList<Node> list)
{
if (n == null) return;
if (n.left != null) recursive_collect (n.L, list);
if (n.right != null) recursive_collect (n.R, list);
list.add(n.value);
}
public static ArrayList<Node> collect()
{
ArrayList<Node> list = new ArrayList<Node>();
recursive_collect (head, list);
return list;
}
// sorting the tree: O(n log n + n)
public static ArrayList<Node> sortTree()
{
// Collecting nodes: O(n)
ArrayList<Node> list = collect();
// Merge Sort: O(n log n)
Collections.sort(list);
return list;
}
// The example in the picture you provided
public static void createTestTree()
{
Node left1 = new Node (new Node(null,-2,null), -1, new Node(null,0,null));
Node left2 = new Node (new Node(null,-1,null), 0, new Node(null,1,null));
Node right = new Node (left2, 1, new Node(null,2,null));
head = new Node (left1, 0, right);
}
// test
public static void main(String [] args)
{
createTestTree();
ArrayList<Node> list = sortTree();
for (Node n : list)
{
System.out.println(n.value);
}
}
}
Ý của bạn là gì theo độ phức tạp 'O (1) và O (n)'? Bạn có nghĩa là O (1) không gian? Tôi có thể tưởng tượng rằng có một thuật toán O (n) bằng cách cân bằng cây theo cách tương tự với cây AVL và sau đó thực hiện một quá trình truyền tải theo thứ tự. –
Sắp xếp chính xác có nghĩa là gì? Phương thức cần trả về một danh sách được sắp xếp? printf? Chúng ta có thể sửa đổi cái cây không? – Knoothe
Không gian O (1) là một yêu cầu thực sự? Chỉ cần làm bất kỳ traversal có vẻ khó khăn (nếu chúng ta không thể sửa đổi cây) để làm trong O (1) không gian. Có lẽ nó là O (chiều cao)? btw, bfs mất không gian Omega (n). Không O (log n). – Knoothe