The Algorithm Design Manual (3rd) Exercise Solution 'E3-23'

Table of Contents

Introduction
Repository
Exercise 3-23
- Question
- Solution

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-23

Question

Assume we are given a standard dictionary (balanced binary search tree) defined on a set of n strings, each of length at most l. We seek to print out all strings beginning with a particular prefix p. Show how to do this in $O(ml \log{n})$ time, where m is the number of strings.

Solution

Routine

Every node in binary search tree is restricted so that its value must be in certain range, and the range is determined by the path the program passes through from the root to the node.

So, compare the lower bound of the range and prefix string. If the first k letter of the lower bound string is smaller than the prefix (k is the length of prefix), the examination of the node finishes.
The same check applies to the upper bound and the prefix (check prefix < upper bound).

Then, check if the node's value contains prefix, and if so print the value.

Do the above from the root recursively.

Complexity

It costs at most $O(\log{n})$ to find one node containing prefix string. And there are m strings satisfying the condition.
Printing costs at most l.

So, total cost is $O(ml\log{n})$ ;

Code

C++ code.

#include <cassert>
#include <concepts>
#include <initializer_list>
#include <memory>
#include <sstream>
#include <string>
#include <vector>

constexpr std::string_view SPACE{" "};

template <std::totally_ordered T>
class Binary_search_tree {
   protected:
    struct tree {
        T item;
        std::shared_ptr<tree> parent;
        std::shared_ptr<tree> left;
        std::shared_ptr<tree> right;
    };
    using p_tree = std::shared_ptr<tree>;

    p_tree root;
    int size{0};

   public:
    Binary_search_tree(std::initializer_list<T> list) {
        for (auto &&e : list) insert_tree(e);
    };

    int get_size() const { return size; };

    p_tree search_tree(T searchee) {
        auto helper{[&](auto helper, p_tree tree) -> p_tree {
            if (!tree) return nullptr;
            if (tree->item == searchee)
                return tree;
            else if (searchee < tree->item)
                return helper(helper, tree->left);
            else
                return helper(helper, tree->right);
        }};
        return helper(helper, root);
    }

    void insert_tree(T val) {
        auto helper{[&](auto helper, p_tree parent, bool is_min) -> void {
            p_tree *p_tree;
            if (val < parent->item)
                p_tree = &(parent->left);
            else {
                p_tree = &(parent->right);
                is_min = false;
            }
            if (!(*p_tree)) {
                *p_tree = std::make_shared<tree>(val, parent, nullptr, nullptr);
                return;
            } else {
                helper(helper, *p_tree, is_min);
            }
        }};
        if (!root) {
            root = std::make_shared<tree>(val, nullptr, nullptr, nullptr);
        } else
            helper(helper, root, true);
        ++size;
    }
};

class Printable_str_tree : public Binary_search_tree<std::string> {
   public:
    void print_all_prefixed(std::ostream &o, const std::string_view prefix) {
        const auto compare_prefix{[](const std::string_view text,
                                     const std::string_view prefix) -> int {
            return text.compare(0, prefix.size(), prefix);
        }};

        const auto helper{[&](auto helper, p_tree tree, p_tree lbound,
                              p_tree ubound) -> void {
            if (!tree || (lbound && 0 < compare_prefix(lbound->item, prefix)) ||
                (ubound && compare_prefix(ubound->item, prefix) < 0))
                return;
            if (!compare_prefix(tree->item, prefix)) o << tree->item << SPACE;

            helper(helper, tree->left, lbound, tree);
            helper(helper, tree->right, tree, ubound);
        }};
        helper(helper, root, nullptr, nullptr);
    }
};

auto split(const std::string &s, const std::string_view delim) {
    std::vector<std::string> result;
    size_t pos{0};
    size_t p_data_stt{0};
    while ((pos = s.find(delim, pos)) != std::string::npos) {
        if (p_data_stt != pos) {
            result.push_back(s.substr(p_data_stt, pos - p_data_stt));
            p_data_stt = pos + 1;
        }
        ++pos;
    }

    return result;
}

int main(int argc, char const *argv[]) {
    Printable_str_tree str_tree{{"a", "b"}};
    std::ostringstream ss;

    str_tree.print_all_prefixed(ss, "a");
    auto printeds{split(ss.str(), SPACE)};
    std::sort(printeds.begin(), printeds.end());
    assert(printeds == (std::vector<std::string>{"a"}));
    ss.str("");
    ss.clear();

    str_tree.print_all_prefixed(ss, "b");
    printeds = split(ss.str(), SPACE);
    std::sort(printeds.begin(), printeds.end());
    assert(printeds == (std::vector<std::string>{"b"}));
    ss.str("");
    ss.clear();

    str_tree.print_all_prefixed(ss, "c");
    printeds = split(ss.str(), SPACE);
    std::sort(printeds.begin(), printeds.end());
    assert(!printeds.size());
    ss.str("");
    ss.clear();

    str_tree = {{"abc", "ade", "abd", "adf"}};

    str_tree.print_all_prefixed(ss, "a");
    printeds = split(ss.str(), SPACE);
    std::sort(printeds.begin(), printeds.end());
    assert(printeds == (std::vector<std::string>{"abc", "abd", "ade", "adf"}));
    ss.str("");
    ss.clear();

    str_tree.print_all_prefixed(ss, "ab");
    printeds = split(ss.str(), SPACE);
    std::sort(printeds.begin(), printeds.end());
    assert(printeds == (std::vector<std::string>{"abc", "abd"}));
    ss.str("");
    ss.clear();

    str_tree.print_all_prefixed(ss, "ad");
    printeds = split(ss.str(), SPACE);
    std::sort(printeds.begin(), printeds.end());
    assert(printeds == (std::vector<std::string>{"ade", "adf"}));
    ss.str("");
    ss.clear();

    str_tree = {{"pd", "qd", "pi", "qb", "ow", "od", "pj",
                 "oe", "pa", "pf", "ph", "ob", "pe", "pc",
                 "qc", "oa", "oc", "pb", "ox", "qa", "pg"}};

    str_tree.print_all_prefixed(ss, "p");
    printeds = split(ss.str(), SPACE);
    std::sort(printeds.begin(), printeds.end());
    assert(printeds ==
           (std::vector<std::string>{"pa", "pb", "pc", "pd", "pe", "pf", "pg",
                                     "ph", "pi", "pj"}));
    ss.str("");
    ss.clear();

    return 0;
}