Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Threaded Tree Causes SegFault
78 views
Skip to first unread message
xerofoify
Nov 28, 2016, 4:12:06 PM11/28/16
to
Greetings All,
Seems the tree is now segfaulting and can't figure out why. I am getting very annoyed with and have no idea why. I have tried everything I can think of to no result, I will post the code again. But can someone show me a complete working insert and constructor as I have no idea why this doesn't work.
#include <iostream>
using namespace std;
//Threaded Binary Tree Class that is templated to hold Node pointers with data type T
template <class T>
class ThreadedTree{
//Internal Node Class for each Node in the tree
struct Node{
//Constructor for Node Class
//Takes the data to be held as a paramater and Node pointers for left and right elements
//defaults are nullptr for left and right elements and data is set to default value for data type T
Node(const T& data = T{}, Node* left = nullptr, Node* right = nullptr){
data_ = data;
right_ = right;
left_ = left;
}
T data_;
Node*left_;
Node* right_;
bool leftThread;
bool rightThread;
//Finds the leftmost from the struct Node pointer passed in, returns nullptr if the Node is nullptr
struct Node* leftMost(struct Node *n){
if (n == nullptr){
return nullptr;
}
while (n->left_ != nullptr){
n = n->left_;
}
return n;
}
//Finds the rightmost from the struct Node pointer passed in, returns nullptr if the Node is nullptr
struct Node* rightMost(struct Node *n){
if (n == nullptr){
return nullptr;
}
while (n->right_ != nullptr){
n = n->right_;
}
return n;
}
};
Node* root_;
void cleanup(Node* subtreeroot){
if(subtreeroot==root_){
return;
}
if (subtreeroot){
cleanup(subtreeroot->left_);
cleanup(subtreeroot->right_);
delete subtreeroot;
}
}
public:
class const_iterator{
protected:
friend class ThreadedTree;
//Constructor that sets curr_ internal Node for iterator to Node passed in agrument Node* c
const_iterator(Node* c){ curr_ = c; }
Node* curr_;
//Checks current node is not nullptr
bool checkData(){
return curr_ == nullptr;
}
public:
//Constructor that sets curr_ internal iterator Node to nullptr
const_iterator(){
curr_ = nullptr;
}
//Takes a interger and makes iterator point to next right element before returning previous element
const_iterator operator++(int){
if(curr_==nullptr){
}
const_iterator old = *this;
if (curr_->rightThread){
curr_ = curr_->right_;
}
else {
curr_ = curr_->left_;
curr_ = curr_->rightMost(curr_);
}
return const_iterator(old);
}
//Takes a interger and makes iterator point to next left element before returning previous element
const_iterator operator--(int){
const_iterator old =*this;
if(curr_==nullptr){
return nullptr;
}
if (curr_->leftThread){
curr_ = curr_->left_;
}
else{
curr_ = curr_->right_;
curr_ = curr_->leftMost(curr_);
}
return const_iterator(old);
}
//Takes no arguments and makes iterator point to next right element
const_iterator operator++(){
if (curr_==nullptr){
return nullptr;
}
if(curr_->rightThread){
curr_= curr_->right_;
}
else{
curr_ = curr_->left_;
curr_ = curr_->rightMost(curr_);
}
return iterator(curr_);
}
//Takes no arguments and makes iterator point to next left element
const_iterator operator--(){
if(curr_==nullptr){
return nullptr;
}
if(curr_->leftThread){
curr_ = curr_->right_;
}
else{
curr_ = curr_->right_;
curr_ = curr_->leftMost(curr_);
}
return iterator(curr_);
}
//Takes no arguments and returns internal Node of iterator
const T& operator*(){
return curr_->data_;
}
//Takes const_iterator reference and sees if internal element equals passed reference's element
bool operator==(const const_iterator& rhs) const{
return curr_ == rhs.curr_;
}
//Takes const_iterator reference and sees if internal element does not equals passed reference's element
bool operator!=(const const_iterator& rhs) const{
return curr_ != rhs.curr_;
}
friend class ThreadedTree;
};
class iterator :public const_iterator{
protected:
//Constructor that sets curr_ internal iterator Node to Node passsed
iterator(Node* c) :const_iterator(c){}
public:
// Constructor that sets curr_ internal iterator Node to nullptr
iterator() :const_iterator(){}
const T& operator*(){
return this->curr_->data_;
}
iterator operator++(int){
iterator old = *this;
if(this->checkData()) {
return nullptr;
}
if (this->curr_->rightThread){
this->curr_ = this->curr_->right_;
}
else{
Node* pass = this->curr_->left_;
this->curr_ = this->curr_->left_;
this->curr_ = this->curr_->rightMost(pass);
}
return iterator(old);
}
//Takes a interger and makes iterator point to left element before returning previous element
iterator operator--(int){
const_iterator old = *this;
if(this->checkData()){
return nullptr;
}
if (this->curr->leftThread){
this->curr = this->curr->right_;
}
else{
Node* pass = this->curr_->left_;
this->curr_ = this->curr_->right_;
this->curr_ = this->curr_->leftMost(pass);
}
return iterator(old);
}
//Takes a interger and makes iterator point to next right element before returning previous element
iterator operator++(){
if(this->checkData()){
return nullptr;
}
if (*this->curr->rightThread){
this->curr = this->curr->right_;
}
else{
this->curr_ = this->curr_->left_;
this->curr_ = this->curr_->rightMost(this->curr_->right_);
}
return iterator(this->curr_);
}
//Takes no arguments and makes iterator point to next right element
iterator operator--(){
if(this->checkData()){
return nullptr;
}
if(this->curr->leftThread){
this->curr = this->curr->right_;
}
else{
this->curr_ = this->curr_->right_;
this->curr_ = this->curr_->leftMost(this->curr_->left_);
}
return iterator(this->curr_);
}
friend class ThreadedTree;
};
//Constructor that creates new Tree, takes no arguments and sets tree to new state
ThreadedTree(){
root_ = new Node();
root_->leftThread = true;
root_->leftThread = false;
}
void printTree()
{
Node *tmp = root_, *p;
for (;;)
{
p = tmp;
tmp = tmp->right_;
if (!p->rightThread)
{
while (!tmp->leftThread)
{
tmp = tmp->left_;
}
}
if (tmp == root_)
break;
cout<<tmp->data_<<" ";
}
cout<<endl;
}
//Takes const reference of type T and inserts it into tree, returns iterator to inserted Node
iterator insert(const T& data){
Node* p = root_;
for (;;){
if (p->data_ < data){
if (p->leftThread)
break;
p = p->right_;
}
else if (p->data_ > data){
if (p->rightThread)
break;
p = p->left_;
}
}
Node* tmp = new Node();
tmp->data_ = data;
tmp->rightThread = tmp->leftThread = true;
if (p->data_ < data){
tmp->right_ = p->right_;
tmp->left_ = p;
p->right_ = tmp;
p->rightThread = false;
return iterator(p->right_);
}
else{
tmp->right_ = p;
tmp->left_ = p->left_;
p->left_ = tmp;
p->leftThread = false;
return iterator(p->left_);
}
}
//Takes const reference of type T and finds it in table,if not found returns nullptr
iterator find(const T& data) const{
Node *tmp = root_->left_;
for (;;){
if (tmp->data_ > data){
if (tmp->rightThread)
return nullptr;
tmp = tmp->right_;
}
else if (tmp->data_ < data){
if (tmp->leftThread)
return nullptr;
tmp = tmp->left_;
}
else{
return iterator(tmp);
}
}
}
//Takes no arguments and returns leftmost Node in Tree as iterator
iterator begin(){
Node* curr = root_;
if (curr->right_ == nullptr && curr->left_ == nullptr) {
return nullptr;
}
if (curr != nullptr) {
while(curr->left_!=nullptr){
curr = curr->left_;
}
}
return iterator(curr);
}
//Takes no arguments and returns rightmost Node in Tree as iterator
iterator end(){
return nullptr;
}
//Takes no arguments and returns leftmost Node in Tree as const_iterator
const_iterator begin() const{
Node* curr = root_;
if (curr->right_ == nullptr && curr->left_ == nullptr) {
return nullptr;
}
if (curr != nullptr) {
while(curr->left_!=nullptr){
curr = curr->left_;
}
}
return const_iterator(curr);
}
//Takes no arguments and returns rightmost Node in Tree as iterator
const_iterator end() const{
return nullptr;
}
//Destructor that destroys tree
~ThreadedTree(){
cleanup(root_);
}
};
Seems the tree is now segfaulting and can't figure out why. I am getting very annoyed with and have no idea why. I have tried everything I can think of to no result, I will post the code again. But can someone show me a complete working insert and constructor as I have no idea why this doesn't work.
#include <iostream>
using namespace std;
//Threaded Binary Tree Class that is templated to hold Node pointers with data type T
template <class T>
class ThreadedTree{
//Internal Node Class for each Node in the tree
struct Node{
//Constructor for Node Class
//Takes the data to be held as a paramater and Node pointers for left and right elements
//defaults are nullptr for left and right elements and data is set to default value for data type T
Node(const T& data = T{}, Node* left = nullptr, Node* right = nullptr){
data_ = data;
right_ = right;
left_ = left;
}
T data_;
Node*left_;
Node* right_;
bool leftThread;
bool rightThread;
//Finds the leftmost from the struct Node pointer passed in, returns nullptr if the Node is nullptr
struct Node* leftMost(struct Node *n){
if (n == nullptr){
return nullptr;
}
while (n->left_ != nullptr){
n = n->left_;
}
return n;
}
//Finds the rightmost from the struct Node pointer passed in, returns nullptr if the Node is nullptr
struct Node* rightMost(struct Node *n){
if (n == nullptr){
return nullptr;
}
while (n->right_ != nullptr){
n = n->right_;
}
return n;
}
};
Node* root_;
void cleanup(Node* subtreeroot){
if(subtreeroot==root_){
return;
}
if (subtreeroot){
cleanup(subtreeroot->left_);
cleanup(subtreeroot->right_);
delete subtreeroot;
}
}
public:
class const_iterator{
protected:
friend class ThreadedTree;
//Constructor that sets curr_ internal Node for iterator to Node passed in agrument Node* c
const_iterator(Node* c){ curr_ = c; }
Node* curr_;
//Checks current node is not nullptr
bool checkData(){
return curr_ == nullptr;
}
public:
//Constructor that sets curr_ internal iterator Node to nullptr
const_iterator(){
curr_ = nullptr;
}
//Takes a interger and makes iterator point to next right element before returning previous element
const_iterator operator++(int){
if(curr_==nullptr){
}
const_iterator old = *this;
if (curr_->rightThread){
curr_ = curr_->right_;
}
else {
curr_ = curr_->left_;
curr_ = curr_->rightMost(curr_);
}
return const_iterator(old);
}
//Takes a interger and makes iterator point to next left element before returning previous element
const_iterator operator--(int){
const_iterator old =*this;
if(curr_==nullptr){
return nullptr;
}
if (curr_->leftThread){
curr_ = curr_->left_;
}
else{
curr_ = curr_->right_;
curr_ = curr_->leftMost(curr_);
}
return const_iterator(old);
}
//Takes no arguments and makes iterator point to next right element
const_iterator operator++(){
if (curr_==nullptr){
return nullptr;
}
if(curr_->rightThread){
curr_= curr_->right_;
}
else{
curr_ = curr_->left_;
curr_ = curr_->rightMost(curr_);
}
return iterator(curr_);
}
//Takes no arguments and makes iterator point to next left element
const_iterator operator--(){
if(curr_==nullptr){
return nullptr;
}
if(curr_->leftThread){
curr_ = curr_->right_;
}
else{
curr_ = curr_->right_;
curr_ = curr_->leftMost(curr_);
}
return iterator(curr_);
}
//Takes no arguments and returns internal Node of iterator
const T& operator*(){
return curr_->data_;
}
//Takes const_iterator reference and sees if internal element equals passed reference's element
bool operator==(const const_iterator& rhs) const{
return curr_ == rhs.curr_;
}
//Takes const_iterator reference and sees if internal element does not equals passed reference's element
bool operator!=(const const_iterator& rhs) const{
return curr_ != rhs.curr_;
}
friend class ThreadedTree;
};
class iterator :public const_iterator{
protected:
//Constructor that sets curr_ internal iterator Node to Node passsed
iterator(Node* c) :const_iterator(c){}
public:
// Constructor that sets curr_ internal iterator Node to nullptr
iterator() :const_iterator(){}
const T& operator*(){
return this->curr_->data_;
}
iterator operator++(int){
iterator old = *this;
if(this->checkData()) {
return nullptr;
}
if (this->curr_->rightThread){
this->curr_ = this->curr_->right_;
}
else{
Node* pass = this->curr_->left_;
this->curr_ = this->curr_->left_;
this->curr_ = this->curr_->rightMost(pass);
}
return iterator(old);
}
//Takes a interger and makes iterator point to left element before returning previous element
iterator operator--(int){
const_iterator old = *this;
if(this->checkData()){
return nullptr;
}
if (this->curr->leftThread){
this->curr = this->curr->right_;
}
else{
Node* pass = this->curr_->left_;
this->curr_ = this->curr_->right_;
this->curr_ = this->curr_->leftMost(pass);
}
return iterator(old);
}
//Takes a interger and makes iterator point to next right element before returning previous element
iterator operator++(){
if(this->checkData()){
return nullptr;
}
if (*this->curr->rightThread){
this->curr = this->curr->right_;
}
else{
this->curr_ = this->curr_->left_;
this->curr_ = this->curr_->rightMost(this->curr_->right_);
}
return iterator(this->curr_);
}
//Takes no arguments and makes iterator point to next right element
iterator operator--(){
if(this->checkData()){
return nullptr;
}
if(this->curr->leftThread){
this->curr = this->curr->right_;
}
else{
this->curr_ = this->curr_->right_;
this->curr_ = this->curr_->leftMost(this->curr_->left_);
}
return iterator(this->curr_);
}
friend class ThreadedTree;
};
//Constructor that creates new Tree, takes no arguments and sets tree to new state
ThreadedTree(){
root_ = new Node();
root_->leftThread = true;
root_->leftThread = false;
}
void printTree()
{
Node *tmp = root_, *p;
for (;;)
{
p = tmp;
tmp = tmp->right_;
if (!p->rightThread)
{
while (!tmp->leftThread)
{
tmp = tmp->left_;
}
}
if (tmp == root_)
break;
cout<<tmp->data_<<" ";
}
cout<<endl;
}
//Takes const reference of type T and inserts it into tree, returns iterator to inserted Node
iterator insert(const T& data){
Node* p = root_;
for (;;){
if (p->data_ < data){
if (p->leftThread)
break;
p = p->right_;
}
else if (p->data_ > data){
if (p->rightThread)
break;
p = p->left_;
}
}
Node* tmp = new Node();
tmp->data_ = data;
tmp->rightThread = tmp->leftThread = true;
if (p->data_ < data){
tmp->right_ = p->right_;
tmp->left_ = p;
p->right_ = tmp;
p->rightThread = false;
return iterator(p->right_);
}
else{
tmp->right_ = p;
tmp->left_ = p->left_;
p->left_ = tmp;
p->leftThread = false;
return iterator(p->left_);
}
}
//Takes const reference of type T and finds it in table,if not found returns nullptr
iterator find(const T& data) const{
Node *tmp = root_->left_;
for (;;){
if (tmp->data_ > data){
if (tmp->rightThread)
return nullptr;
tmp = tmp->right_;
}
else if (tmp->data_ < data){
if (tmp->leftThread)
return nullptr;
tmp = tmp->left_;
}
else{
return iterator(tmp);
}
}
}
//Takes no arguments and returns leftmost Node in Tree as iterator
iterator begin(){
Node* curr = root_;
if (curr->right_ == nullptr && curr->left_ == nullptr) {
return nullptr;
}
if (curr != nullptr) {
while(curr->left_!=nullptr){
curr = curr->left_;
}
}
return iterator(curr);
}
//Takes no arguments and returns rightmost Node in Tree as iterator
iterator end(){
return nullptr;
}
//Takes no arguments and returns leftmost Node in Tree as const_iterator
const_iterator begin() const{
Node* curr = root_;
if (curr->right_ == nullptr && curr->left_ == nullptr) {
return nullptr;
}
if (curr != nullptr) {
while(curr->left_!=nullptr){
curr = curr->left_;
}
}
return const_iterator(curr);
}
//Takes no arguments and returns rightmost Node in Tree as iterator
const_iterator end() const{
return nullptr;
}
//Destructor that destroys tree
~ThreadedTree(){
cleanup(root_);
}
};
Richard
Nov 28, 2016, 4:32:08 PM11/28/16
to
[Please do not mail me a copy of your followup]
xerofoify <xero...@gmail.com> spake the secret code
<7c67fe32-313c-49c7...@googlegroups.com> thusly:
>Seems the tree is now segfaulting and can't figure out why.
Use a debugger and examine the cause of the segfault. Step through
the code in the debugger leading up the to segfault after you've
discovered the cause.
Write unit tests on your code to verify all control paths as you
develop them.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
xerofoify <xero...@gmail.com> spake the secret code
<7c67fe32-313c-49c7...@googlegroups.com> thusly:
>Seems the tree is now segfaulting and can't figure out why.
the code in the debugger leading up the to segfault after you've
discovered the cause.
Write unit tests on your code to verify all control paths as you
develop them.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
xerofoify
Nov 28, 2016, 4:47:38 PM11/28/16
to
if (p->data_ < data){
before crashing even through roots data is properly set here:
Node(const T& data = T{}, Node* left = nullptr, Node* right = nullptr){
so can to explain how T{} is not setting the data.
Richard
Nov 28, 2016, 5:22:26 PM11/28/16
to
<87cc736d-8416-4138...@googlegroups.com> thusly:
>On Monday, November 28, 2016 at 4:32:08 PM UTC-5, Richard wrote:
>> [Please do not mail me a copy of your followup]
>>
>> xerofoify <xero...@gmail.com> spake the secret code
>> <7c67fe32-313c-49c7...@googlegroups.com> thusly:
>>
>> >Seems the tree is now segfaulting and can't figure out why.
>>
>> Use a debugger and examine the cause of the segfault. Step through
>> the code in the debugger leading up the to segfault after you've
>> discovered the cause.
>>
>> Write unit tests on your code to verify all control paths as you
>> develop them.
>On Monday, November 28, 2016 at 4:32:08 PM UTC-5, Richard wrote:
>> [Please do not mail me a copy of your followup]
>>
>> xerofoify <xero...@gmail.com> spake the secret code
>> <7c67fe32-313c-49c7...@googlegroups.com> thusly:
>>
>> >Seems the tree is now segfaulting and can't figure out why.
>>
>> Use a debugger and examine the cause of the segfault. Step through
>> the code in the debugger leading up the to segfault after you've
>> discovered the cause.
>>
>> Write unit tests on your code to verify all control paths as you
>> develop them.
>I have tried that everything.
Upload your source and unit tests to a github repo and post the link.
Paavo Helde
Nov 28, 2016, 5:27:09 PM11/28/16
to
On 28.11.2016 23:47, xerofoify wrote:
> On Monday, November 28, 2016 at 4:32:08 PM UTC-5, Richard wrote:
>> [Please do not mail me a copy of your followup]
>>
>> xerofoify <xero...@gmail.com> spake the secret code
>> <7c67fe32-313c-49c7...@googlegroups.com> thusly:
>>
>>> Seems the tree is now segfaulting and can't figure out why.
>>
>> Use a debugger and examine the cause of the segfault. Step through
>> the code in the debugger leading up the to segfault after you've
>> discovered the cause.
>>
>> Write unit tests on your code to verify all control paths as you
>> develop them.
>> --
>> "The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
>> The Terminals Wiki <http://terminals-wiki.org>
>> The Computer Graphics Museum <http://computergraphicsmuseum.org>
>> Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
> I have tried that everything. I even drew it up hand. I don't get how it's not working. Nothing about that code doesn't make sense to me. I really have no idea how it doesn't as in a debugger it hits:
>
> if (p->data_ < data){
> before crashing even through roots data is properly set here:
What debugger does not show you that p is null at that point? You are
> On Monday, November 28, 2016 at 4:32:08 PM UTC-5, Richard wrote:
>> [Please do not mail me a copy of your followup]
>>
>> xerofoify <xero...@gmail.com> spake the secret code
>> <7c67fe32-313c-49c7...@googlegroups.com> thusly:
>>
>>> Seems the tree is now segfaulting and can't figure out why.
>>
>> Use a debugger and examine the cause of the segfault. Step through
>> the code in the debugger leading up the to segfault after you've
>> discovered the cause.
>>
>> Write unit tests on your code to verify all control paths as you
>> develop them.
>> --
>> "The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
>> The Terminals Wiki <http://terminals-wiki.org>
>> The Computer Graphics Museum <http://computergraphicsmuseum.org>
>> Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
> I have tried that everything. I even drew it up hand. I don't get how it's not working. Nothing about that code doesn't make sense to me. I really have no idea how it doesn't as in a debugger it hits:
>
> if (p->data_ < data){
> before crashing even through roots data is properly set here:
happily updating p in this loop, without ever checking if it becomes
null or not:
Node* p = root_;
for (;;) {
if (p->data_ < data) {
if (p->leftThread)
break;
p = p->right_;
} else if (p->data_ > data) {
if (p->rightThread)
break;
p = p->left_;
}
}
xerofoify
Nov 28, 2016, 5:51:07 PM11/28/16
to
iterator begin(){
Node* curr = root_;
if (curr->right_ == nullptr && curr->left_ == nullptr) {
return nullptr;
}
if (curr != nullptr) {
while(curr->left_!=nullptr){
curr = curr->left_;
}
}
return iterator(curr);
}
Look I have tried this for at least a few things now and ran through a debugger many times guys. Something is not clicking in my understanding so asking me to run through it with a debugger does not help.
Node* curr = root_;
if (curr->right_ == nullptr && curr->left_ == nullptr) {
return nullptr;
}
if (curr != nullptr) {
while(curr->left_!=nullptr){
curr = curr->left_;
}
}
return iterator(curr);
}
Paavo Helde
Nov 29, 2016, 3:29:47 AM11/29/16
to
flow? From afar, it looks like you are using some kind of Monte Carlo
programming style - writing down a random sequence of tokens, hoping
that this somehow works and does whatever is needed. This is bound to be
a very tedious method and certainly does not work in C++ where a program
might appear to work correctly and still exhibit Undefined Behavior.
Maybe you should first try a simpler program involving pointers?
Anyway, if stepping through debugger does not help you, write down the
state on the paper (values for the memory slots occupied by p, data,
etc) and step through the code on paper.
> Also does changing begin to this do anything:
> iterator begin(){
> Node* curr = root_;
> if (curr->right_ == nullptr && curr->left_ == nullptr) {
> return nullptr;
> }
> if (curr != nullptr) {
Either the check is in the wrong place or it is not needed.
> while(curr->left_!=nullptr){
> curr = curr->left_;
> }
> }
> return iterator(curr);
> }
> Look I have tried this for at least a few things now and ran through a debugger many times guys. Something is not clicking in my understanding so asking me to run through it with a debugger does not help.
>
were apparently needed in the previous version. I have no idea what this
function should do, so I do not know if they are needed or not, but it
sure looks suspicious.
hth
Paavo
xerofoify
Nov 30, 2016, 11:56:33 AM11/30/16
to
//Takes const reference of type T and inserts it into tree, returns iterator to inserted Node
iterator insert(const T& data){
if (root_ == nullptr){
iterator insert(const T& data){
root_ = new Node(data);
root_->leftThread = true;
root_->rightThread = false;
return iterator(root_);
}
Node* p = root_;
while(p) {
if (p->data_ < data){
if (p->leftThread)
break;
p = p->right_;
}
else if (p->data_ > data){
if (p->rightThread)
break;
p = p->left_;
}
}
Node* tmp = new Node();
tmp->data_ = data;
tmp->rightThread = tmp->leftThread = true;
if (p->data_ < data){
tmp->right_ = p->right_;
tmp->left_ = p;
p->right_ = tmp;
p->rightThread = false;
return iterator(p->right_);
}
else{
tmp->right_ = p;
tmp->left_ = p->left_;
p->left_ = tmp;
p->leftThread = false;
return iterator(p->left_);
}
}
I was wondering how to rewrite the insert part to avoid a nullptr deference and insert correctly as currently I can't see a way.
if (p->leftThread)
break;
p = p->right_;
}
else if (p->data_ > data){
if (p->rightThread)
break;
p = p->left_;
}
}
Node* tmp = new Node();
tmp->data_ = data;
tmp->rightThread = tmp->leftThread = true;
if (p->data_ < data){
tmp->right_ = p->right_;
tmp->left_ = p;
p->right_ = tmp;
p->rightThread = false;
return iterator(p->right_);
}
else{
tmp->right_ = p;
tmp->left_ = p->left_;
p->left_ = tmp;
p->leftThread = false;
return iterator(p->left_);
}
}
Öö Tiib
Nov 30, 2016, 1:34:37 PM11/30/16
to
On Wednesday, 30 November 2016 18:56:33 UTC+2, xerofoify wrote:
>
> I was wondering how to rewrite the insert part to avoid a nullptr
> deference and insert correctly as currently I can't see a way.
Who knows. Your threaded three algorithm seems badly broken. For
>
> I was wondering how to rewrite the insert part to avoid a nullptr
> deference and insert correctly as currently I can't see a way.
example lets take from very first lines of insert:
if (root_ == nullptr) // so lets say the three is empty and go into if
{
root_ = new Node(data);
// here root_->data_ is data
// root_->left_ and root_->right_ are nullptr
// and the values of leftThread and rightThread are uninitialized
// because Node has such a dreaded constructor.
root_->leftThread = true;
// huh? to where that nullptr supposedly threads?
root_->rightThread = false;
// but that nullptr does not thread anywhere?
return iterator(root_);
}
So on. The code does and tells things on every step that seem wrong.
Even that seems unclear if node with smaller data is left or right.
My suggestion is to first make clear what thing that threaded binary
tree is. Then write plan how you implement it and what any thing
means in your data.
xerofoify
Nov 30, 2016, 4:19:47 PM11/30/16
to
answer.
Alf P. Steinbach
Nov 30, 2016, 4:48:08 PM11/30/16
to
On 28.11.2016 22:11, xerofoify wrote:
> Greetings All, Seems the tree is now segfaulting and can't figure out
> why. I am getting very annoyed with and have no idea why. I have
> tried everything I can think of to no result, I will post the code
> again. But can someone show me a complete working insert and
> constructor as I have no idea why this doesn't work. #include
> <iostream> using namespace std; //Threaded Binary Tree Class that is
> templated to hold Node pointers with data type T template <class T>
> class ThreadedTree{
Well I'd like to help but that's just a wall of code to me. Unless I
> Greetings All, Seems the tree is now segfaulting and can't figure out
> why. I am getting very annoyed with and have no idea why. I have
> tried everything I can think of to no result, I will post the code
> again. But can someone show me a complete working insert and
> constructor as I have no idea why this doesn't work. #include
> <iostream> using namespace std; //Threaded Binary Tree Class that is
> templated to hold Node pointers with data type T template <class T>
> class ThreadedTree{
spend (too much) time delving into it. Which I'm not going to do.
I can think of 2 meanings of “threaded (binary) three”:
• A binary tree with extra pointers to support iterative traversal, e.g.
for iterators.
• A binary tree supporting or implemented with concurrent threads.
I did not see extra pointers in your code but I did see a function that
apparently had to do with iterators, but with just a dummy body.
Can you explain what you mean by “threaded tree”?
Cheers!,
- Alf
Jerry Stuckle
Nov 30, 2016, 5:52:07 PM11/30/16
to
--
==================
Remove the "x" from my email address
Jerry Stuckle
jstu...@attglobal.net
==================
xerofoify
Nov 30, 2016, 9:12:45 PM11/30/16
to
Alf P. Steinbach
Nov 30, 2016, 9:32:29 PM11/30/16
to
“Algorithm + Data Structures = Programs” book. I may be wrong, maybe he
was just describing balancing, but the book is worth reading anyway. :)
The Oberon (programming language) version, as opposed to the original
Pascal version, is available as a legal free PDF download, somewhere.
Anyway, the extra pointer(s) you need depend on the order you want to
visit the nodes in.
For an ordinary in-order traversal (left sub-tree, then root, then right
sub-tree) an upward parent pointer in each node suffices, in addition to
the downward left and right pointers. It works because in an in-order
traversal, when you're about to process the data in a node X, you have
already processed the left sub-tree. It's a little tricky, but drawing a
figure and doing this by hand should pave the way. :)
I suggest you start by making a non-threaded binary tree and simply use
“fat” iterators, iterators that remember the path down the tree,
essentially the stack of nodes that one needs back up through to go
logically forward. `std::stack` comes to mind as useful for that.
I am not entirely /sure/ but I think that approach will give you
insights that will ease the implementation of threaded tree.
Cheers & hth.,
_ Alf
xerofoify
Nov 30, 2016, 9:58:51 PM11/30/16
to
Jerry Stuckle
Dec 1, 2016, 12:03:43 AM12/1/16
to
one to the parent node. All the rest is done in the iterator.
It takes a bit more work to maintain the parent pointer, but not that
much. Get the rest of your binary tree working first, then add the
parent pointer. Finally you can write an iterator class for it.
Öö Tiib
Dec 1, 2016, 2:51:48 AM12/1/16
to
how to program it:
http://algorithms.tutorialhorizon.com/double-threaded-binary-tree-complete-implementation/
Unfortunately it is written in Java there, but the idea in C++ is same.
In C++ we just have to manage lifetime of discarded nodes and that part
is not needed in Java that has garbage collection.
Öö Tiib
Dec 1, 2016, 4:57:00 AM12/1/16
to
describe where nodes have parent_, left_ and right_ pointers.
I think such binary tree is among best performant.
However there is "threaded binary tree" that does not use parent_
pointers but instead reuses the left_ and right_ pointers of leafs for
additional back traversal. It is rare tree design so I am not sure in what
situations it is better. OP asked about that tree.
Gareth Owen
Dec 1, 2016, 11:48:13 AM12/1/16
to
Öö Tiib <oot...@hot.ee> writes:
> Then tell that you need explanation and tutorial. Here is link to
> tutorial how to program it:
You quoted 400 lines of code to say that?
> Then tell that you need explanation and tutorial. Here is link to
> tutorial how to program it:
Stuart Redmann
Dec 1, 2016, 12:21:19 PM12/1/16
to
I'm reading this on a cell phone, so it's a PITA to scroll through pages of
unnecessary quoted text. In general, I would not bother, but a posting from
you, Öö Tiib, is usually worth reading.
Regards,
Stuart
Richard
Dec 1, 2016, 12:25:16 PM12/1/16
to
[Please do not mail me a copy of your followup]
"Alf P. Steinbach" <alf.p.stein...@gmail.com> spake the secret code
<o1nhc3$pp0$1...@dont-email.me> thusly:
>On 28.11.2016 22:11, xerofoify wrote:
>> Greetings All, Seems the tree is now segfaulting and can't figure out
>> why. I am getting very annoyed with and have no idea why. I have
>> tried everything I can think of to no result, I will post the code
>> again. But can someone show me a complete working insert and
>> constructor as I have no idea why this doesn't work. #include
>> <iostream> using namespace std; //Threaded Binary Tree Class that is
>> templated to hold Node pointers with data type T template <class T>
>> class ThreadedTree{
>
>Well I'd like to help but that's just a wall of code to me. Unless I
>spend (too much) time delving into it. Which I'm not going to do.
code. Will someone debug it for me?"
When I asked the OP if they had written unit tests to probe all the
control paths of their implementation, they said yes they did that,
but I've never seen any indication that any unit tests were written.
Jerry Stuckle
Dec 1, 2016, 1:37:50 PM12/1/16
to
just means the tree can be transversed in both directions. If you do
not have a parent pointer, this is normally done through recursion.
It's a bit easier to code (if you understand recursion, anyway) because
you don't need to maintain the parent pointers.
But it's tougher if you are just passed a node and need to find its
parent. That typically means starting from the base of the tree and
going down until you find your node, then working your way back up.
Parent pointers solve this problem.
So, advantages and disadvantages to both ways.
Popping mad
Dec 5, 2016, 7:29:11 PM12/5/16
to
On Wed, 30 Nov 2016 13:19:37 -0800, xerofoify wrote:
> The more you just tell me my code doesn't work does not help, I am
> looking for either proper documentation on how to do this or an example
> that actually works not a this doesn't work and draw it out answer.
Your gonna fail that class
> The more you just tell me my code doesn't work does not help, I am
> looking for either proper documentation on how to do this or an example
> that actually works not a this doesn't work and draw it out answer.
0 new messages