- Published on
The Algorithm Design Manual (3rd) Exercise Solution 'E3-13'
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
Exercise 3-13
Question
Two elements of a binary search tree have been swapped by mistake. Give an algorithm to identify these two elements so they can be swapped back.
Solution
Both c++ code.
Solution-1
The outline of the algorithm is that we traverse the tree in-order and record the nodes in which violations against the rule of in-order sequence of value occured.
#include <cassert>
#include <concepts>
#include <memory>
#include <utility>
#include <vector>
template <std::totally_ordered T>
class Binary_search_tree {
private:
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};
void swap_val(p_tree t1, p_tree t2) {
T tmp{t1->item};
t1->item = t2->item;
t2->item = tmp;
}
// Traverse the tree in order
// The value of node must be increaced in order, too.
// If they violates, return false, otherwise return true
bool check_balanced_impl(p_tree p_root) {
T curr{};
bool undefined_val{true};
auto helper{[&](auto helper, p_tree tree) -> bool {
if (!tree) return true;
if (!helper(helper, tree->left)) return false;
if (undefined_val) {
undefined_val = false;
} else if (tree->item < curr)
return false;
curr = tree->item;
return helper(helper, tree->right);
}};
return helper(helper, p_root);
}
public:
Binary_search_tree(std::initializer_list<T> list) {
for (auto &&e : list) insert_tree(e);
};
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) -> void {
p_tree *p_tree;
if (val < parent->item)
p_tree = &(parent->left);
else
p_tree = &(parent->right);
if (!(*p_tree)) {
*p_tree = std::make_shared<tree>(val, parent, nullptr, nullptr);
return;
} else {
helper(helper, *p_tree);
}
}};
if (!root) {
root = std::make_shared<tree>(val, nullptr, nullptr, nullptr);
} else
helper(helper, root);
++size;
}
bool check_balanced() { return check_balanced_impl(root); }
// For test of mistaken situation
void swap_target_2(p_tree tr1, p_tree tr2) { swap_val(tr1, tr2); }
/*
Traverse the tree in order
The value of node must be increaced in order, too.
When there is a violation, record the previous node and current node.
Continue the check of sanity of value from the next node.
If there is additional violation, record the node and return the two.
Else, return the recored prevous node and the node in which violation
occured.
*/
std::pair<p_tree, p_tree> identify_swapped() {
std::vector<p_tree> to_be_swappeds;
p_tree prev{nullptr};
auto helper{[&](auto helper, p_tree tree) -> bool {
if (!tree) return true;
if (!helper(helper, tree->left)) return false;
if (prev && tree->item < prev->item) {
if (!to_be_swappeds.size()) {
to_be_swappeds.push_back(prev);
to_be_swappeds.push_back(tree);
} else {
to_be_swappeds.back() = tree;
return false;
}
}
prev = tree;
return helper(helper, tree->right);
}};
helper(helper, root);
return {to_be_swappeds.front(), to_be_swappeds.back()};
}
void correct_swapped() {
auto to_be_swapped{identify_swapped()};
swap_val(to_be_swapped.first, to_be_swapped.second);
}
};
int main(int argc, char const *argv[]) {
Binary_search_tree<int> tree{8, 4, 12, 2, 6, 10, 14, 1,
3, 5, 7, 9, 11, 13, 15, 16};
auto test_swapping_2{[&tree](int i1, int i2) {
assert(tree.check_balanced());
auto tr_node1{tree.search_tree(i1)};
auto tr_node2{tree.search_tree(i2)};
tree.swap_target_2(tr_node1, tr_node2);
assert(!tree.check_balanced());
tree.correct_swapped();
assert(tree.check_balanced());
}};
test_swapping_2(8, 4);
test_swapping_2(8, 2);
test_swapping_2(8, 1);
test_swapping_2(4, 1);
test_swapping_2(2, 1);
test_swapping_2(4, 6);
test_swapping_2(4, 5);
test_swapping_2(2, 6);
test_swapping_2(1, 6);
test_swapping_2(1, 7);
test_swapping_2(4, 12);
test_swapping_2(4, 9);
test_swapping_2(4, 16);
test_swapping_2(2, 14);
test_swapping_2(2, 15);
test_swapping_2(2, 16);
test_swapping_2(5, 13);
return 0;
}
Solution-2
The solution is more complicated and inefficient than previous one.
But anyway it works and tests are passed.
The outline of the algorithm is check the violations against a rule of a range of node's value.
Rule: each tree node has open interval of its value which is determined by two ancestral trees.
#include <cassert>
#include <concepts>
#include <functional>
#include <initializer_list>
#include <memory>
#include <numeric>
#include <stdexcept>
#include <vector>
template <std::totally_ordered T>
class Binary_search_tree {
private:
struct tree;
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};
void swap_val(p_tree t1, p_tree t2) {
T tmp{t1->item};
t1->item = t2->item;
t2->item = tmp;
}
bool check_labeling_sanity_impl(p_tree p_root) {
bool result{true};
auto helper{[&](auto helper, p_tree tree, p_tree lbound,
p_tree ubound) -> bool {
// each tree has open interval of its value
// which is determined by two ancestral trees
// if curernt_value <= lower bound, set result=false
// if curernt_value => upper bound, set result=false
// search recursively
if (!tree) return true;
if ((lbound && tree->item <= lbound->item) ||
(ubound && tree->item >= ubound->item)) {
result = false;
return false;
}
if (!helper(helper, tree->left, lbound, tree)) return false;
if (!helper(helper, tree->right, tree, ubound)) return false;
return true;
}};
helper(helper, p_root, nullptr, nullptr);
return result;
}
public:
Binary_search_tree(std::initializer_list<T> list) {
for (auto &&e : list) insert_tree(e);
};
p_tree search_tree(T searchee) {
auto helper{[&](auto helper, p_tree tree) -> p_tree {
if (!tree) return p_tree{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) {
std::function<void(p_tree)> helper{[&val, &helper](p_tree parent) {
// std::unique_ptr<p_tree> p_tree;
p_tree *p_tree;
if (val < parent->item)
// p_tree = std::make_unique<p_tree>(&(parent->left));
p_tree = &(parent->left);
else
// p_tree = std::make_unique<p_tree>(parent->right);
p_tree = &(parent->right);
if (!(*p_tree)) {
*p_tree = std::make_shared<tree>(val, parent, nullptr, nullptr);
return;
} else {
helper(*p_tree);
}
}};
if (!root) {
root = std::make_shared<tree>(val, nullptr, nullptr, nullptr);
} else
helper(root);
++size;
}
int get_max_depth() {
int max_d{0};
int rest_of_elem{size};
std::function<bool(p_tree, int)> helper{
[&max_d, &rest_of_elem, &helper](p_tree tree, int curr_d) {
// if tree is null, exit
if (!tree) return true;
// update the max_depth
max_d = std::max(max_d, curr_d);
// decrement the rest of elements
--rest_of_elem;
// if the diff between max_degth_at_that_time and current_depth
// is greater than rest_of_elements, stop the
// sebsequent recursion
if ((max_d - curr_d) > rest_of_elem) return false;
// recurse for the left and right subtrees
if (!helper(tree->left, curr_d + 1)) return false;
if ((max_d - curr_d) > rest_of_elem) return false;
if (!helper(tree->right, curr_d + 1)) return false;
return true;
}};
helper(root, 0);
return max_d;
}
bool check_labeling_sanity() { return check_labeling_sanity_impl(root); }
void swap_target_2(p_tree tr1, p_tree tr2) { swap_val(tr1, tr2); }
std::pair<p_tree, p_tree> identify_swapped() {
// each tree has open interval of its value
// which is determined by two ancestral trees
// first, find the tree violating the interval
// there are two reasons of violation
// [1] the tree which represents the interval's edge (lower bound or
// upper bound)
// is to be re-swapped
// [2] the current tree where the violation occures
// is to be re-swapped
// case_1: assume both [1] and [2] to be reswapped:
// swap the two tree's value and check the labeling sanity
// case_2: assume [1] to be reswapped: search the next violation
// from the subtree of the current tree
// case_3: assume [2] to be reswapped: search the next violation
// from the root tree
std::pair<p_tree, p_tree> results{nullptr, nullptr};
struct Bound_with_own_bounds {
p_tree tree;
p_tree lbound;
p_tree ubound;
};
std::function<bool(p_tree, p_tree, p_tree, T)> subhelper_findnext{
[&](p_tree tree, p_tree lbound, p_tree ubound, T searchee) {
if (!tree) return true;
if ((lbound && tree->item <= lbound->item) ||
(ubound && tree->item >= ubound->item)) {
results.second = tree;
return false;
}
if (searchee < tree->item) {
if (!subhelper_findnext(tree->left, lbound, tree, searchee))
return false;
} else {
if (!subhelper_findnext(tree->right, tree, ubound,
searchee))
return false;
}
return true;
}};
std::function<bool(p_tree, Bound_with_own_bounds,
Bound_with_own_bounds)>
helper{[&](p_tree tree, Bound_with_own_bounds lboundset,
Bound_with_own_bounds uboundset) {
if (!tree) return true;
auto is_both_reswapped{
[&](p_tree tgttree,
Bound_with_own_bounds boundset) -> bool {
if (boundset.lbound &&
tgttree->item <= boundset.lbound->item)
return false;
if (boundset.ubound &&
tgttree->item >= boundset.ubound->item)
return false;
swap_val(tgttree, boundset.tree);
auto sanity{check_labeling_sanity_impl(boundset.tree)};
swap_val(tgttree, boundset.tree);
return sanity;
}};
if (lboundset.tree && tree->item <= lboundset.tree->item) {
if (is_both_reswapped(tree, lboundset)) {
results.first = tree;
results.second = lboundset.tree;
return false;
}
results.first = lboundset.tree;
subhelper_findnext(tree->right, tree, uboundset.tree,
lboundset.tree->item);
if (results.second) return false;
results.first = tree;
subhelper_findnext(root, nullptr, nullptr, tree->item);
if (!results.second)
throw std::logic_error("cannot find the next error");
return false;
}
if (uboundset.tree && tree->item >= uboundset.tree->item) {
if (is_both_reswapped(tree, uboundset)) {
results.first = tree;
results.second = uboundset.tree;
return false;
}
results.first = uboundset.tree;
subhelper_findnext(tree->left, lboundset.tree, tree,
uboundset.tree->item);
if (results.second) return false;
results.first = tree;
subhelper_findnext(root, nullptr, nullptr, tree->item);
if (!results.second)
throw std::logic_error("cannot find the next error");
return false;
}
if (!helper(tree->left, lboundset,
{tree, lboundset.tree, uboundset.tree}))
return false;
if (!helper(tree->right, {tree, lboundset.tree, uboundset.tree},
uboundset))
return false;
return true;
}};
helper(root, {nullptr, nullptr, nullptr}, {nullptr, nullptr, nullptr});
return results;
}
void correct_swapped() {
auto to_be_swapped{identify_swapped()};
swap_val(to_be_swapped.first, to_be_swapped.second);
}
};
int main(int argc, char const *argv[]) {
Binary_search_tree<int> tree{8, 4, 12, 2, 6, 10, 14, 1,
3, 5, 7, 9, 11, 13, 15, 16};
auto test_swapping_2{[&tree](int i1, int i2) {
assert(tree.check_labeling_sanity());
auto tr_node1{tree.search_tree(i1)};
auto tr_node2{tree.search_tree(i2)};
tree.swap_target_2(tr_node1, tr_node2);
assert(!tree.check_labeling_sanity());
tree.correct_swapped();
assert(tree.check_labeling_sanity());
}};
test_swapping_2(8, 4);
test_swapping_2(8, 2);
test_swapping_2(8, 1);
test_swapping_2(4, 1);
test_swapping_2(2, 1);
test_swapping_2(4, 6);
test_swapping_2(4, 5);
test_swapping_2(2, 6);
test_swapping_2(1, 6);
test_swapping_2(1, 7);
test_swapping_2(4, 12);
test_swapping_2(4, 9);
test_swapping_2(4, 16);
test_swapping_2(2, 14);
test_swapping_2(2, 15);
test_swapping_2(2, 16);
test_swapping_2(5, 13);
return 0;
}