độ phức tạp của Morris Traversal o (n) như thế nào?

Question

http://geeksforgeeks.org/?p=6358 Có ai vui lòng giải thích cách Morris Traversal có độ phức tạp về thời gian là o(n) không? Trong quá trình truyền tải, bất cứ khi nào nút có con trái, một bản sao của nó được tạo cho đúng con của người tiền nhiệm của nó. Trường hợp xấu nhất là người tiền nhiệm phải được tìm thấy cho mỗi nút

while(pre->right != NULL && pre->right != current) 
     pre = pre->right; 

Điều gì sẽ làm tăng sự phức tạp? Tôi có thiếu gì ở đây không?

Answer 1

nó sẽ không làm tăng độ phức tạp khi thuật toán chỉ xây dựng lại cây theo một hướng (xây dựng lại chỉ có O (n) sau đó chỉ có O (n) lần nữa in chúng ... nhưng chúng đã hợp nhất cả hai chức năng vào một chức năng tương tự và đã cho một tên đặc biệt cho algo thats nó ...

Answer 2

Một cách khác để xem xét nó là tìm ra bao nhiêu lần một nút cây sẽ được đi ngang. thời gian cho một cây nhị phân) Chúng tôi đang xem xét O (n).

Answer 3

Bài viết gốc cho quá trình truyền qua Morris là Traversing binary trees simply and cheaply. Nó cho rằng độ phức tạp thời gian là O (n) trong phần Giới thiệu:

Nó cũng hiệu quả, mất thời gian tỷ lệ thuận với số lượng nút trong cây và không yêu cầu ngăn xếp thời gian chạy cũng như bit 'cờ' trong các nút.

Bài báo đầy đủ nên có phân tích độ phức tạp về thời gian. Nhưng không thể truy cập toàn bộ giấy miễn phí.

Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间） thực hiện một số phân tích. Cô ấy là bản dịch của phần có liên quan:

Cây nhị phân n-nút có cạnh n-1. Trong quá trình truyền tải của Morris, một cạnh được truy cập nhiều nhất là 2 lần. Một lượt truy cập là để định vị một nút. Một lượt truy cập là để tìm kiếm người tiền nhiệm của một số nút. Trong cây nhị phân sau, đường đứt nét màu đỏ là để định vị một nút. Đường đứt nét màu đen là để tìm nút tiền thân.