Tree 總整理

Binary Search Tree

#include<stdio.h>
#include<stdlib.h>

struct BST{
    struct BST *left;
    struct BST *right;
    int val;
};
typedef struct BST BST;

BST* MinValueNode(BST* root){
    BST* current = root;
    while(current && current ->left != NULL){
        current = current->left;
    }
    return current;
}

BST* searchNode(BST* root, int data) {
    if (root == NULL || root->val == data) {
        return root;
    }
    if (data < root->val) {
        return searchNode(root->left, data);
    } else {
        return searchNode(root->right, data);
    }
}


BST* deleteNode(BST *root,int n){
    if(root == NULL)return root;
    if(n < root->val){
        root->left = deleteNode(root->left,n);
    }else if(n > root->val){
        root->right = deleteNode(root->right,n);
    }
    else{
        if(root->left == NULL){
            BST* nextNode = root->right;
            free(root);
            return nextNode;    
        }else if(root->right == NULL){
            BST* nextNode = root->left;
            free(root);
            return nextNode;
        }
        BST *SuccessorNode = MinValueNode(root->right);
        root->val = SuccessorNode->val;
        root->right = deleteNode(root->right,SuccessorNode->val);
    }
    return root;
}



BST* insertNode(BST *root,int n){
    if(root == NULL){
        BST* newNode = (BST *)malloc(sizeof(BST));
        newNode->val = n;
        newNode->left = NULL;
        newNode->right = NULL;
        root = newNode;
        return root;
    }
    if( n > root ->val){
        root->right = insertNode(root->right,n);
    }else if(n < root->val){
        root->left = insertNode(root->left,n);
    }
    return root;
}

void PrintTree(BST *root){
    if(root == NULL)return;
    PrintTree(root->left);
    printf("%d ",root->val);
    PrintTree(root->right);
}

int main(){
    BST *root = NULL;
    root = insertNode(root,1);
    root = insertNode(root,5);
    root = insertNode(root,10);
    root = insertNode(root,100);
    root = insertNode(root,25);

    root = deleteNode(root,10);

    PrintTree(root);


}

AVL Tree

最多的節點數為\(2^H-1\) 最少為 \(N_h = N_{h-1} + N_{h-2} + 1\)

	Actual
Insert	O(1)
Delete	O(logn)

insert

LL RR LR RL 到達的node當做轉換過後的root node 的左子樹當祖父的右子樹 node 的右子樹當作父節點的左子樹

delete

刪掉後看他的父節點變多少

• case 1 : 1 or -1

  不做任何事

• case 2 : 2 or -2

  要再看父節點的左子節點

  • case 1 : 0

    做一個LL Rotation

  • case 2 : 1

    做一個LL Rotation

  • case 3 : -1

    做一個LR Rotation

• case 3 : 0

  因為可能會改變到parent 因此要檢查parenet 是否符合case 2

m-way search tree

	Actual
Insert	O(logn)
Delete	O(logn)

full degree m tree 最大有 \(\frac{m^h - 1}{m-1}\) 個節點 \(m^h-1\)個資料

B-Tree

Balanced m-way search tree

• root degree >= 2
• Degree of other internal node >= \(\lceil \frac{m}{2} \rceil\)

insert

先尋找所在的位置 如果overflow 做split 再與父節點結合 直到沒有overflow 的操作

delete

分為是否在葉節點

• 刪除的資料在葉節點

如果隔壁有可以借的node 就做rotation 不行就做conbine

• 刪除的資料不在葉節點

左子樹找最大或右子樹找最小

Red-Black Tree

• 邊會分為黑色或紅色
• 不會有連續的紅色邊出現
• 每條路徑經過的黑色邊個數都是相同的

	Actual
Insert	O(logn)
Delete	O(logn)

insert

插入的新點先當成紅色，之後做rr ll rl lr rotation 到達的點當root並且更改為黑色

如果parent 是紅色的 且 他的 sibling 是紅色的 那就把他們都改成黑色 並且檢查parent 是否需要rotation

delete

可以分成 y0 y1 y2

• y0

  刪除的node 是紅色的或者是由紅色的邊與parent連

  可以直接刪

• y1

  黑色的邊且child 有紅色的 往有紅色的邊走，直到紅色的邊取代成黑色的為止

• y2

  黑色的邊 但是child 沒有紅色的 * Type 1 Sibling 是黑色且有紅色的child 刪除node後 做rr * Type 2 Sibling 是黑色且沒有紅色的child 刪除node後 其parent 如果是紅色 parent變黑色與其子樹變紅色 否則parent其子樹變紅色 * Type 3 Sibling 是紅色的 silbing 變成刪除node 的parent 並且交換顏色

B+ Tree

最下層有指標互相連線，上面的node皆變成索引

insert

類似b-tree 但是如果是最底層的需要合併 放在上面的會變成最左邊的值

delete

刪除為空的話跟sibling 借 parent 的索引值要改成sibling的最小值，沒得借直接刪除 刪除如果是空的可以跟隔壁子樹借，隔壁子樹沒辦法借直接conboine