codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// Find the closest matching number from a binary search tree #include <iostream> #include <cassert> using namespace std; template <typename T> class BST { struct treeNode; struct treeNode { treeNode(const T& val) : val(val), left(0), right(0) {} T val; struct treeNode *left; struct treeNode *right; }; public: BST() : root(0) {} ~BST() { clean_(root); } void insert(const T& val) { treeNode *t = root; if(0 == root) root = new treeNode(val); else while(t){ if(val < t->val) { if(t->left) t = t->left; else t->left = new treeNode(val), t = 0; } else { if(t->right) t = t->right; else t->right = new treeNode(val), t = 0; } } } bool find(const T& val) { treeNode *t = root; while(t){ if(val == t->val) return true; if(val < t->val) t = t->left; else t = t->right; } return false; } T find_closest(const T& val) { const T v1( smallestEleGreaterThanVal(root, val) ); const T v2( LargestEleSmallerThanVal(root, val) ); return v1-val < val-v2 ? v1 : v2; } void debug_traverse() { if(root) debug_traverse(root); } private: T smallestEleGreaterThanVal(treeNode *t, T val) { T r = 9999; // FIXME:: Replace with T.infinity() or root while(t) { if(t->val == val) return val; if(t->val < val) return min(r, smallestEleGreaterThanVal(t->right, val)); else r = t->val, t = t->left; } return r; } T LargestEleSmallerThanVal(treeNode *t, T val) { T r = -9999; // FIXME:: Replace with -T.infinity() or root while(t) { if(t->val == val) return val; if(t->val > val) return max(r, LargestEleSmallerThanVal(t->left, val)); else r = t->val, t = t->right; } return r; } void debug_traverse(treeNode *t) { if(t->left) debug_traverse(t->left); cout << t->val << ' '; if(t->right) debug_traverse(t->right); } void clean_(treeNode *p) { if(p) { if(p->left) clean_(p->left); if(p->right) clean_(p->right); } delete p; } private: treeNode *root; }; int main() { BST<int> b; b.insert(15); b.insert(8); b.insert(45); b.insert(12); b.insert(65); b.insert(38); b.insert(1); b.insert(10); b.insert(4); b.insert(64); cout << "Tree contents are: "; b.debug_traverse(); cout << endl; assert( b.find(12) ); assert( !b.find(13) ); cout << "Content nearest to -5 is " << b.find_closest(-5) << endl; cout << "Content nearest to 7 is " << b.find_closest(7) << endl; cout << "Content nearest to 8 is " << b.find_closest(8) << endl; cout << "Content nearest to 9 is " << b.find_closest(9) << endl; cout << "Content nearest to 13 is " << b.find_closest(13) << endl; cout << "Content nearest to 100 is " << b.find_closest(100) << endl; return 0; } // Q: What is the practical usage of a function like find_closest? // A: It can find best matching floating point number from a tree // of floats or doubles in O(log N) time.
Private
[
?
]
Run code
Submit