- binary tree: how did you learn it? - 22 Updates
- new benchmark for my read/write algorithm... - 2 Updates
- binary tree: how did you learn it? - 1 Update
| Jeremy Murphy <jeremy.william.murphy@gmail.com>: Mar 09 07:13PM -0800 Dear readers, I'm doing some informal research for a talk I'll be giving, and what I'm interested in is firstly: how did you learn to program a binary tree in C++? Specifically, what implementation were you taught? Also, was it a general binary tree, or a binary _search_ tree, that was taught? A small code snippet would be helpful but no need for complete implementations. And if you were never taught it, I'd still be interested to hear that! Secondly, if you use a (general) binary tree occasionally now, which implementation do you use? Although I'm really interested in C++, I'd still be interested to hear if you learned it in C or maybe even Java since those languages can make similar trade offs and are not as distant in memory semantics as say Python or Haskell. Use your own discretion though, I don't want to upset anyone with a lot of non-C++ code flying around. :) Thanks, and I'll post a link to the presentation after it happens. Cheers. Jeremy |
| Cholo Lennon <chololennon@hotmail.com>: Mar 10 02:01AM -0300 On 3/10/19 12:13 AM, Jeremy Murphy wrote: > Secondly, if you use a (general) binary tree occasionally now, which implementation do you use? > Although I'm really interested in C++, I'd still be interested to hear if you learned it in C or maybe even Java since those languages can make similar trade offs and are not as distant in memory semantics as say Python or Haskell. Use your own discretion though, I don't want to upset anyone with a lot of non-C++ code flying around. :) > Thanks, and I'll post a link to the presentation after it happens. I learned about binary trees many years ago, in the early '90s (ohhh I was so young!), using Pascal and the classic book "Algorithms + Data Structures = Programs" by Niklaus Wirth, so if you want my first possible implementation just get that book ;-) Regards -- Cholo Lennon Bs.As. ARG |
| Melzzzzz <Melzzzzz@zzzzz.com>: Mar 10 06:53AM > tree in C++? Specifically, what implementation were you taught? > Also, was it a general binary tree, or a binary _search_ tree, that > was taught? Binary search tree. I can't remember but I think I used wikipedia. > A small code snippet would be helpful but no need for complete > implementations. Well, There is insert and delete operation. For search tree insert is done by going left right until node found. Then you insert node. for delete left right until node found. then find next which is at bottom, swap then delete last node. Here is my implementation of treap: #ifndef TREAP_H #define TREAP_H #include <functional> #include <cstddef> #include <utility> #include <cassert> #include <ctime> #include <string> #include <vector> #include <sstream> #include <iostream> #include <cstdlib> template <class K,class V, class Compare = std::less<K> > class Treap{ public: Treap(unsigned seed = time(0)) : root_(0),size_(0),counter_(0), seed_(seed) { } ~Treap() { delete root_; } size_t size()const{ return size_; } std::pair<K,V>& insert(const std::pair<K,V>& arg) { return insert_priv(arg); } V& operator[](const K& k) { return insert(std::pair<K,V>(k,V())).second; } V* find(const K& k)const; size_t depth()const { size_t fd,ld; first(root_,fd); last(root_,ld); if(fd>ld)return fd; else return ld; } void erase(const K& key) { remove(key); } std::string toString()const { std::string tmp; if(root_ == 0)tmp.append("Tree has no nodes"); else { tmp = toString(root_,"",true); } return tmp; } bool validate()const { return validate(root_); } size_t counter()const { return counter_; } void reset_counter() { counter_=0; } void clear() { delete root_; size_ = 0; root_ = 0; } template <class F> void for_each(F f) { for_each(root_,f); } void weight(size_t& left,size_t& right) { if(!root_) { left=right=0; return; } left = weight(root_->left_); right = weight(root_->right_); } private: struct Node{ Node(const std::pair<K,V>& data, Treap& trp) : parent_(0),left_(0),right_(0),priority_(trp.prn()),data_(data) { } ~Node() { delete left_; delete right_; } Node* rotate_left() { Node* n = left_; //std::cout<<"rotate left\n"<<toString(this,"",true)<<"\n"; if(n == 0) { return 0; } left_ = n->right_; if(left_)left_->parent_ = this; n->right_ = this; if(parent_) { if(parent_->left_ == this) { parent_->left_ = n; n->parent_ = parent_; } else { if(parent_->right_ != this) { std::cout<<"rotate left failed\nchild\n"<<toString(this,"",true)<<"\nparent\n"<<toString(parent_,"",true)<<"\n"; abort(); } parent_->right_ = n; n->parent_ = parent_; } } else { n->parent_ = 0; } parent_ = n; return n; } Node* rotate_right() { Node* n = right_; //std::cout<<"rotate right\n"<<toString(this,"",true)<<"\n"; if(n == 0) { return 0; } right_ = n->left_; if(right_)right_->parent_ = this; n->left_ = this; if(parent_) { if(parent_->left_ == this) { parent_->left_ = n; n->parent_ = parent_; } else { if(parent_->right_ != this) { std::cout<<"rotate right failed\nchild\n"<<toString(this,"",true)<<"\nparent\n"<<toString(parent_,"",true)<<"\n"; abort(); } parent_->right_ = n; n->parent_ = parent_; } } else { n->parent_ = 0; } parent_ = n; return n; } Node *parent_,*left_,*right_; unsigned priority_; std::pair<K,V> data_; }; size_t weight(Node* n) { if(!n)return 0; return weight(n->left_)+weight(n->right_)+1; } template <class F> void for_each(Node* n, F f) { if(!n)return; for_each(n->left_,f); f(n->data_); for_each(n->right_,f); } unsigned prn() { return rand_r(&seed_); } Node* first(Node* n,size_t& depth)const { Node *rc = 0; depth = 0; while(n) { ++depth; rc = n; n = n->left_; } return rc; } Node* last(Node* n,size_t& depth)const { Node* rc = 0; depth = 0; while(n) { ++depth; rc = n; n = n->right_; } return rc; } std::pair<K,V>& insert_priv(const std::pair<K,V>& ins_value,Node* node = 0) { if(root_ == 0) { if(!node) root_ = new Node(ins_value,*this); else { root_ = node; node->parent_ = node->left_ = node->right_ = 0; } ++size_; return root_->data_; } Compare cmp; Node* n = root_; Node *rc = 0, *prev = 0; bool ret; while(n) { prev = n; ret = cmp(ins_value.first,n->data_.first); if(ret) { n=n->left_; } else { rc = n; n = n->right_; } } if(rc && !cmp(rc->data_.first,ins_value.first)) { return rc->data_; } if(ret) { if(!node) { rc = prev->left_ = new Node(ins_value,*this); } else { rc = prev->left_ = node; rc->parent_ = rc->left_ = rc->right_ = 0; } prev->left_->parent_ = prev; } else { if(!node) { rc = prev->right_ = new Node(ins_value,*this); } else { rc = prev->right_ = node; rc->parent_ = rc->left_ = rc->right_ = 0; } prev->right_->parent_ = prev; } n = rc; rebalance_up(n); ++size_; return rc->data_; } void remove(const K& rem_value) { Compare cmp; Node* rc = 0,*n = root_; while(n) { bool ret = cmp(rem_value,n->data_.first); if(ret) { n = n->left_; } else { rc = n; n = n->right_; } } if(!rc || cmp(rc->data_.first,rem_value))return; Node* reb = 0; while(rc->left_ && rc->right_) { Node* n = rc->rotate_right(); if(root_ == rc)root_ = n; if(!reb && n->left_ && n->left_->priority_ < n->priority_)reb = n; } Node** parent_node = 0; if(rc->parent_) parent_node = ((rc->parent_->left_ == rc)?&rc->parent_->left_:&rc->parent_->right_); if(rc->left_ == 0 && rc->right_ == 0) { if(parent_node)*parent_node = 0; else root_ = 0; } else if(rc->left_ == 0) { if(parent_node) { *parent_node = rc->right_; rc->right_->parent_ = rc->parent_; } else { root_ = rc->right_; rc->right_->parent_ = 0; } rc->right_ = 0; } else if(rc->right_ == 0) { if(parent_node) { *parent_node = rc->left_; rc->left_->parent_ = rc->parent_; } else { root_ = rc->left_; rc->left_->parent_ = 0; } rc->left_ = 0; } delete rc; --size_; rebalance_left(reb); } bool validate(const Node* node)const { if(!node)return true; Compare cmp; if(node->left_ && !cmp(node->left_->data_.first,node->data_.first)) { return false; } if(node->right_ && !cmp(node->data_.first,node->right_->data_.first)) { return false; } if(node->left_ && node->left_->parent_ != node) { return false; } if(node->right_ && node->right_->parent_ != node) { return false; } if(node->left_ && node->priority_ > node->left_->priority_) { return false; } if(node->right_ && node->priority_ > node->right_->priority_) { return false; } bool rc1 = validate(node->left_); bool rc2 = validate(node->right_); return rc1 && rc2; } void rebalance_left(Node* node) { if(!node)return; rebalance_left(node->left_); while(node->left_ && node->left_->priority_ < node->priority_) { Node* n = node->rotate_left(); if(node == root_)root_ = n; } } void rebalance_right(Node* node) { if(!node)return; rebalance_right(node->right_); while(node->right_ && node->right_->priority_ < node->priority_) { Node* n = node->rotate_right(); if(node == root_)root_ = n; } } void rebalance_up(Node* n) { while(n->parent_ && n->priority_ < n->parent_->priority_) { if(n->parent_->left_ == n) n = n->parent_->rotate_left(); else n = n->parent_->rotate_right(); if(n->parent_ == 0)root_ = n; } } static std::string toString(const Node* node, const std::string& prefix, bool isTail) { std::string tmp; tmp.append(prefix).append(isTail ? "└── " : "├── "); if(!node) { tmp.append(" null"); return tmp; } std::ostringstream oss; const std::pair<K,V>& v = node->data_; oss<<"p:"<<node->priority_<<" ("<<v.first<<","<<v.second<<")"; tmp.append(oss.str()); oss.str(""); tmp.append("\n"); tmp.append(toString(node->left_,prefix + (isTail?" ":"│ "),false)); tmp.append("\n"); tmp.append(toString(node->right_,prefix + (isTail ? " " : "│ "),true)); return tmp; } public: class iterator{ public: iterator(Node* n):node_(n){} std::pair<K,V>& operator*()const{ return node_->data_; } std::pair<K,V>* operator->()const{ return &node_->data_; } bool operator==(const iterator& other)const { return node_ == other.node_; } bool operator!=(const iterator& other)const { return !(*this == other); } iterator& operator++() { if(node_->right_ != 0) { node_ = node_->right_; while(node_->left_ != 0) { node_ = node_->left_; } } else { Node* tmp = node_->parent_; while(tmp && node_ == tmp->right_) { node_ = tmp; tmp = tmp->parent_; } node_ = tmp; } return *this; } private: Node* node_; }; iterator begin() { size_t depth = 0; return iterator(root_,first(depth)); } iterator end()const { return iterator(0); } private: Node* root_; size_t size_,counter_; unsigned seed_; }; template <class K,class V, class Compare> V* Treap<K,V,Compare>::find(const K& k)const { Compare cmp; Node* n = root_,*tmp = 0; V* rc = 0; while(n) { bool ret = cmp(k,n->data_.first); if(ret) { n = n->left_; } else { tmp = n; n = n->right_; } } if(tmp && !cmp(tmp->data_.first,k)) { rc = &tmp->data_.second; } return rc; } 
Subscribe to:
Post Comments (Atom)
|
No comments:
Post a Comment