Tree’s Theorem

01/11/2019

I. Các cấu trúc cây cơ bản

1. Binary Tree

Mỗi node trong cây có tối đa $2$ con.

2. Binary Search Tree

Là Binary Tree + giá trị của node luôn lớn hơn giá trị của node con trái và bé hơn giá trị của node con phải.

3. AVL Tree (height balanced binary tree)

Là self balancing Binary Search Tree + chênh lệch giữa cây con trái và cây con phải tại bất kì node nào luôn không vượt quá $1$. (<=1)

4. Red-Black Tree

Là self balancing Binary Search Tree +

• Không có 2 node RED liên tiếp
• Chiều cao đen luôn không đổi tại mọi node.
• tất cả node lá là BLACK
• Root always black (sometime this property is omitted)

$\rightarrow$ Hệ quả: Path từ root đến lá xa nhất không dài hơn gấp $2$ lần path từ root đến lá gần nhất. (Dùng property $1$ để suy ra).

II. So sánh AVL Tree vs Red-Black Tree

Giống nhau:

• Cả 2 đều là self balancing Binary Search Tree
• Các thao tác: Search, Insert, Delete đều mất chi phí $O(log(n))$.

Khác nhau:

• AVL is more stricly balance than Red_black Tree

$\rightarrow$ Suy ra

• AVL search nhanh hơn
• AVL chèn lâu hơn

Các CTDL như set, map đều dùng red-black tree (set chưa chắc :v), trong khi AVL dùng trong database (where fast look up required)

III. Duyệt cây

1typedef struct Node* ref;
2struct Node{
3    int value;
4    Node* left;
5    Node* right;
6};

1. Preorder

1//root-left-right
2void preorder(ref root){
3    if (root == NULL) return;
4    cout << root.value << endl;
5    preorder(root->left);
6    preorder(root->right);
7}

2. Inorder

1//left-root-right
2void Inorder(ref root){
3    if (root == NULL) return;
4    Inorder(root->left);
5    cout << root->value;
6    Inorder(root->right);
7}

3. Postorder

1//left-right-root
2void Postorder(ref root){
3    if (root == NULL) return;
4    Postorder(root->left);
5    Postorder(root->right);
6    cerr << root->value;
7}

4. DFS and BFS

1void dfs(int v, int p = 0){
2    for(auto u:g[v]){
3        if (u == p) continue;
4        dfs(u, v);
5    }
6}