Morris Traversal

介紹一下 Morris traversal ，一個 O(1) 空間複雜度的樹遍歷演算法。
故事是從二元樹開始。一般對二元樹的子樹刪除，最樸素的作法是這樣寫⋯⋯

TreeNode *left, *right;
~TreeNode() {
	if ( left ) {
			left->~TreeNode();
			delete left;
	}
	if ( right ) {
			right->~TreeNode();
			delete right;
	}
}

而從 C++11 開始提供的 unique_ptr 是件不錯的事情，STL 提供的指標在管理該指標的物件被釋放時也會釋放 unique_ptr 所指向的物件記憶體，避免造成不必要的 memory leak 。

std::unique_ptr is a smart pointer that owns and manages another object through a pointer and disposes of that object when the unique_ptr goes out of scope.

CppReference

可以改寫成，這樣記憶體管理就會變得由 STL 來做了。 這時候問題就出現了！

std::unique_ptr<TreeNode> left, right;

STL 會遞迴的呼叫樹結構中的子節點，讓子節點也去刪除他們的 unique_ptr ，直到葉節點為止，並 bottom-up 移除這棵樹的記憶體。如果你現在有一顆很大的樹且不平衡，這樣遞迴的呼叫有可能造成 stack frame 突然長大，當資料龐大時 stack frame 炸掉可能就造成 core dump 了。
這時就需要以一種 stateless 的，避免遞迴式呼叫的，樹遍歷演算法才行！那就是 Morris Traversal 。在介紹 Morris Traversal 之前可以先了解 Tail Recursion 。

Tail Recursion

一般寫地回函數時很容易寫成以下形式，讓子結構計算出結果之後再與當前狀態進行運算。這代表在子結構回傳之後才會被完成，所以當前函數的堆疊內容就必須被記錄。在最後才能被計算。

func recsum(x) {
    if (x === 1) {
        return x;
    } else {
        return x + recsum(x - 1);
    }
}
/****** Stack Frame **********/
// calculation performed after all results resolved
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1))) 15

但許多時候對計算不需要子結構這樣的性質或計算沒有優先順序時，我們可以將計算結果累加並傳至下一層的函數呼叫，使得堆疊不需要累積子結構的計算結果，不需要在子函數回傳後做任何額外的計算。這就叫 Tail Recursion 。而且在編譯器找到 Tail recursion 的函式呼叫時會做 Tail Call Optimization (TCO) ，往下一層的函式呼叫不會創造新的 stack 空間而是直接覆蓋當前函式呼叫的 stack 空間。

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}
/****** Stack Frame **********/
// calculation performed as function recurse
// no extra calculation needed after proceeding function call returns.
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

Base Case

回到樹的遍歷。從 base case 出發：

• 假設樹只有一整條像 Linked-List 一般，每個節點都只有右子樹。這時不斷往下即可，就是剛剛所提到的 tail recurse ，堆疊空間並不會額外增長。
• 對一個葉節點來說，也不需要額外的遞迴，直接回傳。

Visiting Left Sub-tree

接著要處理左子樹的部分，假設節點為 X。對左子樹找到子樹中最右側的節點，假設它叫做 Y 。令 Y 的右子節點為 X 。注意這時樹的狀態被改變且不是一個合法的樹，但是接下來會在遍歷的過程中把多設置的邊移除，回到原本樹的狀態。新增邊之後拜訪左子節點。

下圖為例，以節點 6 為根的左子樹中最右側為節點 5 ，新增一條 back-edge 至節點 6 。

Induction & Back-edge Removal

會發現我們正在以 in-order 的方式拜訪整棵樹。

從 6 → 1 → back-edge 回到 2 → 右子樹 3 → 4 → back-edge 回到 5 → 6 。

而當我們回到跟節點 6 時會再一次尋找左子樹中最右側的節點，當發現這個節點已經有 back-edge 時，代表已經做過左子數樹遍歷，可以往右子樹移動了。最多設置 back-edge N 次，而每個節點最多拜訪兩次。整體而言時間複雜度是 O(N) ，而因為我們從頭到尾都是 tail recursion ，所以不會增長 stack frame ，空間複雜度是 O(1) 。

In-order Traversal

void in_order () {
	Node now = root, tmp = nullptr;
	while ( now ) {
		if ( !now->left ) {
			cout << now->data << ", ";
			tmp = now;
			now = tmp->right;
			} else {
			tmp = now->left;
			while ( tmp->right and tmp->right != now ) {
				tmp = tmp->right;
			}
			if ( !tmp->right ) {
				tmp->right = now;
				now = now->left;
			} else {
				tmp->right.reset();
				cout << now->data << ", ";
				now = now->right;
			}
		}
	}
	cout << "\n";
}

In-order Deletion

用 Morris Traversal 來做 deletion 的話，左訪就代表會經過 back-edge 再回來，且回來時因為左子數已經被 in-order 刪除所以不需要有 back-edge clean-up 這種事。我在刪除 back-edge 那邊擺了 assert(0) 來保證不會做到這件事。在往右拜訪子節點時就會把自己刪除。

~Tree () { // morris traversal deletion
	Node *now = root, *tmp = nullptr;
	while ( now ) {
		if ( !now->left ) {
			tmp = now;
			now = now->right;
			delete tmp;
		} else {
			tmp = now->left;
			while ( tmp->right and tmp->right != now ) {
				tmp = tmp->right;
			}
			if ( !tmp->right ) { // left-subtree visit
				tmp->right = now;
				tmp = now;
				now = now->left;
				tmp->left = nullptr;
			} else { // no repeating left visit
				assert(0);
			}
		}
	}
}

Implementation of Morris traversal and Morris traverse-deletion:
Gist – morris.cpp

Original link: eopXD