almost 3 years ago

source

Binary Search Trees - C Program ( Source Code and Documentation )

note

一開始我拿到這份 code 就自以為的把其中一個方向加上等號
以為作者漏掉了有相同 value 的 case
但後來去查了 BST 的定義,似乎 key 要是唯一的,所以不允許這種情形發生

但是實作上總是會有遇到這種情況的時候
Programming Interviews Exposed 的作者就回答了讀者的這個問題:Duplicate Values in Binary Trees

我把作者的回答簡短用自己的話再說一次:

你當然直接可以只幫一邊加上等號,但當相同 key 出現超過兩次的時候,就不會是一個 balanced tree
(可以想像 insert 7 個 5 的時候,會跟一個 height 7 的 linked list 等效)

另一個折衷的辦法是幫兩邊都加上等號,這樣 [5,5,5,5,5,5,5] 就可以建出一個 height 為 3 的 balanced tree
(按:但假設是 [5,4,6,5,5,5] 的話,不管你選擇走哪邊,一定會建出一個 unbalanced tree,
又回到上面的 case,所以除了兩邊等號之外,還要去做 rotation,才能解決 unblanced 的問題)

最後作者說其實在實務上他看過的都是把這些 key 當做一個 set 處理
像是 這篇文章 說的,在每一個 node 下面用一個 list 去儲存,這樣會比加上等號來得好

source code

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

typedef struct treeNode
{
    int data;
    struct treeNode *left;
    struct treeNode *right;
} treeNode;

treeNode* FindMin(treeNode *node)
{
    // There is no element in the tree
    if(node == NULL) {
        return NULL;
    }

    // Go to the left sub tree to find the min element */
    if(node->left)
        return FindMin(node->left);
    else
        return node;
}

treeNode* FindMax(treeNode *node)
{
    if(node == NULL) {
        return NULL;
    }

    if(node->right) 
        FindMax(node->right);
    else
        return node;
}

treeNode* Insert(treeNode *node, int data)
{
    if(node == NULL) // create element
    {
        treeNode *temp;
        temp = (treeNode *)malloc(sizeof(treeNode));
        temp -> data = data;
        temp -> left = temp -> right = NULL;
        return temp;
    }

    if(data > (node->data) ) {
        node->right = Insert(node->right, data);
    }
    else if(data < (node->data)) {
        node->left = Insert(node->left, data);
    }

    // Else there is nothing to do as the data is already in the tree.
    return node;
}

treeNode* Delete(treeNode *node, int data)
{
    treeNode *temp;
    if(node == NULL) {
        printf("Element Not Found");
    }
    else if(data < node->data) {
        node->left = Delete(node->left, data);
    }
            
    else if(data > node->data) {
        node->right = Delete(node->right, data);
    }
    else // data == node->data
    {
        // Now We can delete this node and replace with either minimum element
        //   in the right sub tree or maximum element in the left subtree
        if(node->right && node->left)
        {
            // replace this node with minimum element in the right sub tree
            temp = FindMin(node->right);
            node -> data = temp->data;

            // As we replaced it with some other node, we have to delete that node
            node -> right = Delete(node->right, temp->data);
        }
        else
        {
            // only 1 or 0 children
            // directly remove it from the tree and connect its parent to its child
            temp = node;

            if(node->left == NULL)
                node = node->right;
            else if(node->right == NULL)
                node = node->left;
            
            free(temp); // temp is longer required
        }
    }
    return node;
}

treeNode* Find(treeNode *node, int data)
{
    if(node == NULL) // not found
        return NULL;

    if(data > node->data)
        return Find(node->right, data);
    else if(data < node->data)
        return Find(node->left, data);
    else //found
        return node;
}

void PrintInorder(treeNode *node)
{
    if(node == NULL) {
        return;
    }

    PrintInorder(node->left);
    printf("%d ", node->data);
    PrintInorder(node->right);
}

void PrintPreorder(treeNode *node)
{
    if(node == NULL) {
        return;
    }

    printf("%d ", node->data);
    PrintPreorder(node->left);
    PrintPreorder(node->right);
}

void PrintPostorder(treeNode *node)
{
    if(node == NULL) {
        return;
    }

    PrintPostorder(node->left);
    PrintPostorder(node->right);
    printf("%d ", node->data);
}

int main()
{
    treeNode *root = NULL;
    root = Insert(root, 5);
    root = Insert(root, -1);
    root = Insert(root, 3);
    root = Insert(root, -14);
    root = Insert(root, 8);
    root = Insert(root, 10);
    root = Insert(root, 9);
    root = Insert(root, 6);
    PrintInorder(root);
    printf("\n");

    root = Delete(root, 5);
    root = Delete(root, -1);
    PrintInorder(root);
    printf("\n");

    treeNode *temp;
    temp = FindMin(root);
    printf("Minimum element is %d\n", temp->data);

    temp = FindMax(root);
    printf("Maximum element is %d\n", temp->data);

    temp = Find(root, 8);
    if(temp == NULL) {
        printf("Element 8 not found\n");
    }
    else {
        printf("Element 8 Found\n");
    }

    temp = Find(root, 2);
    if(temp == NULL) {
        printf("Element 2 not found\n");
    }
    else {
        printf("Element 6 Found\n");
    }

    return 0;
}
← Twitch Plays Pokemon: 「群眾媒體」的可能? 請不要使用 emome →
 
comments powered by Disqus