binary tree: how did you learn it?

[Jeremy Murphy]

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]

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]

On 2019-03-10, Jeremy Murphy <jeremy.wil...@gmail.com> wrote:
>
> 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?

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;
}


#endif
(I always mix left/right ;)

> 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. :)

I first programmed them in C++, then in other languages.

>
> Thanks, and I'll post a link to the presentation after it happens.

You got complete implementation of Treap search tree.
>
> Cheers.
>
> Jeremy


--
press any key to continue or any other to quit...

[Alf P. Steinbach]

For me that was early 1980's, but same book and language.

Worth noting that the free version of the book uses the Oberon language,
successor to Modula-2 which was a successor to Pascal, all by Niklaus
Wirth. Well, except to the degree that Kathleen Jensen was involved with
Pascal. I never got that history, but she co-wrote the user manual.

When or if C++ finally gets modules the circle will be ~completed. :)

---

Sillyfact about Wirth and Oberon: Wirth was visiting Xerox PARC (the
place where they invented the Ethernet, bitmapped displays, bitblt,
workstations, object orientation, all nice things, but later on also
RFID tags, cross-cutting concerns, and other more evil stuff), and was
impressed by the What You See Is What You Get approach; bitmapped fonts!
So he went back to Switzerland to build /hardware to support a
programming language/. Namely the Lilith machine, to support Modula 2.

Of course some decades later hardware support for Java emerged.

But I think that shows how far in front and yet at the same time how far
out on the impractical fringes Wirth was. Really remarkable. Sorry, I
couldn't resist mentioning it.


Cheers!,

- Alf

[Jorgen Grahn]

On Sun, 2019-03-10, Jeremy Murphy wrote:
>
> 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?

I never did.

I learned about various balanced trees in the algorithms course at
university circa 1992. I suppose we implemented them, in Standard ML
(which is more or less Haskell).

In C++ I've never needed anything that the standard containers
couldn't give me, e.g. the features of a search tree exposed by
std::map, or the std::make_heap stuff if that counts.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Paavo Helde]

On 10.03.2019 5:13, Jeremy Murphy wrote:
>
> 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!

I was never taught binary trees (instead I was taught things like path
integrals and Grassmann algebras).

I have some vague memory of reading something about red and black trees
in some brochures, but I have never had a need or interest to implement
such a thing. I have implemented several non-binary tree data structures
though.

> Secondly, if you use a (general) binary tree occasionally now, which implementation do you use?

I guess std::map and std::set would qualify.

[Jeremy Murphy]

Interestingly enough, I have two copies of that book--the one in Pascal, and the one in Modula-2--but I hadn't thought to look in it with respect to this question. Thanks for the reminder!

Cheers.

Jeremy

[Jeremy Murphy]

Hey thanks everyone for the quick responses! It's exactly what I was hoping for. And I love historical anecdotes, thank you!

Cheers.

Jeremy

[Melzzzzz]

On 2019-03-10, Jorgen Grahn <grahn...@snipabacken.se> wrote:
> On Sun, 2019-03-10, Jeremy Murphy wrote:
>>
>> 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?
>
> I never did.
>
> I learned about various balanced trees in the algorithms course at
> university circa 1992. I suppose we implemented them, in Standard ML
> (which is more or less Haskell).
>
> In C++ I've never needed anything that the standard containers
> couldn't give me, e.g. the features of a search tree exposed by
> std::map, or the std::make_heap stuff if that counts.

Standard containers does not provide btree which is much more efficent
on modern CPUs then red black tree.
>
> /Jorgen

[Christian Gollwitzer]

Am 10.03.19 um 07:37 schrieb Stefan Ram:
> I do not associate the concept of a binary tree with a
> specific implementation language. I cannot remember having
> learned it "in a programming language". To me,
>
> tree := pair | leave.
> leave := atom.
> pair :=( tree, tree ).
>
> So, this, in a sense is the language I associate with
> trees. A language that allows to define data structures
> using operations like »:=«, »|« and »(·,·)«.
>
> Another approach might define two functions, »left« and
> »right« on trees:
>
> type( left( tree )):= tree | atom.
> type( right( tree )):= tree | atom.
>
> Well, I have no experiene in Haskell or Prolog at all,
> but I guess that these two approaches might be expressed
> in Haskell or Prolog quite easily.

It is indeed. Haskell includes algebraic data types, so it allows you to
write:

data Tree atom = Nil | Node atom (Tree atom) (Tree atom)

and that is all it takes to construct binary trees!

Christian

[Bart]

Any script language should be able to construct a binary tree like this:

(((10,20), 30), (40, (50,60)))

without defining any special data structure. And a function to traverse
it in order is trivial.

What's missing is being able to incrementally add elements to such a
tree while keeping it sorted (or whatever binary trees are used for, as
I can't remember the last time I used one, if ever).

It's not clear how your line of Haskell takes care of that. On-line
examples seem to require quite a bit of extra code.

[Jeremy Murphy]

You're right, the theoretical definition of a binary tree is very simple, which is why I'm interested to hear how people first learn to actually implement it in a language like C or C++, where there are many performance trade offs to make.

When I have time, I'll find or make some implementations in Haskell in order to compare benchmarks with C++ implementations.

Cheers.

Jeremy

[Melzzzzz]

You have to write code as well...
>
> Christian

[Melzzzzz]

It does not. You have to write code to insert and delete from tree...

[Melzzzzz]

On 2019-03-10, Jeremy Murphy <jeremy.wil...@gmail.com> wrote:

You have time couple of hours is all what it takes. You spend more
bubbling here ;)
>
> Cheers.
>
> Jeremy

[cda...@gmail.com]

On Saturday, March 9, 2019 at 7:13:11 PM UTC-8, Jeremy Murphy wrote:
> 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?

I learned about the them in an Intro to Computer Science class at UC Berkeley. But the university didn't use C++. Instead, the used a dialect of Lisp. Later on down the road we did trees again. But we implemented them in both C and C++ in order for us to see the different approaches and shortcomings to each approach.

> Also, was it a general binary tree, or a binary _search_ tree, that was taught?

Dunno, I was hungover at the time.

> 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!
>

Sorry, the PC with the code snippet is locked away in my parents attic.

> Secondly, if you use a (general) binary tree occasionally now, which implementation do you use?
>

The one given to me by a person whose IQ is 40 points higher than me.

> 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. :)
>

The only trade off is that we had to use this really ugly dummy inner class on trees. The person who was teaching the class at the time mentioned that trees didn't really seem to work in Java. Three years later that same diatribe landed him a software engineering job at Google. And the last time I checked, he is now a team lead at that joint.

> Thanks, and I'll post a link to the presentation after it happens.

Well, if I can hear the neighbor lady having really loud sex again at 5am, well, me reading the link might have to wait.

[Scott Lurndal]

Jeremy Murphy <jeremy.wil...@gmail.com> writes:
>
>Dear readers,
>

>I'm doing some informal research for a talk I'll be giving, and what I'm in=

>terested in is firstly: how did you learn to program a binary tree in C++?

From "Fundamentals of Data Structures" by Horowitz and Sahni long before
C++.

[Bonita Montero]

Check the code of an AVC-tree or a red-black-tree-implementation in
an easier language like Java and try to rewrite the code in C++ as
a generic implementation with templates.

[Tim Rentsch]

Jeremy Murphy <jeremy.wil...@gmail.com> writes:

> 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?

I first learned about binary trees, binary search trees, and
balancing binary trees, from Knuth volume 1, before the C
programming language existed. (In those days "Knuth" always
meant "The Art of Computer Programming".)

I have at various times implemented AVL trees, B trees, Red-Black
trees, 2-3 trees, and 2-3-4 trees. (If I remember right the B
trees were actually a slight variation, with a B tree structure
in the upper levels, but the bottom level was done with hash
tables.) All of these supported searching.

> Secondly, if you use a (general) binary tree occasionally now,
> which implementation do you use?

Depends on the context. In most cases if one were readily
available I would use that without caring which variation it is.
Also other factors sometimes make a big difference in choosing
one kind or another. For example, an imperative tree that is
updated in place might favor a different representation than a
functional tree that always makes a "new tree", where the new
tree isn't all new but reuses large parts of the existing tree
(ie, before the addition has been done). Scale also makes a big
difference - an in-memory structure of up to thousands or perhaps
tens of thousands of items is probably better done as a hash
table (for searching), whereas a longer-lived or much larger
structure (so it needs to be stored on disk) is more likely to
use something like a B tree.

> 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. :)

Knuth describes algorithms in what might be called an English
pseudo-code (and the Mix assembly language, which IMO is worse
than useless). So in my case the learning was pretty much
language agnostic. Since learning from Knuth I have programmed
different sorts of trees in C, C++, and functional languages of
the ML variety.

[Jorgen Grahn]

Fair enough: standard containers don't expose red-black trees either.

[cda...@gmail.com]

On Sunday, March 10, 2019 at 12:00:24 PM UTC-7, Tim Rentsch wrote:
> Jeremy Murphy <jeremy.wil...@gmail.com> writes:
>
> > 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?
>
> I first learned about binary trees, binary search trees, and
> balancing binary trees, from Knuth volume 1, before the C
> programming language existed. (In those days "Knuth" always
> meant "The Art of Computer Programming".)
>

Going off an a bit of a tangent. The thing that I remember from that book is that he uses what is known as logical implication. This of course is a really subtle but important point that a lot of books fail to address.

[Vir Campestris]

On 10/03/2019 08:17, Jorgen Grahn wrote:
> On Sun, 2019-03-10, Jeremy Murphy wrote:
>>
>> 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?
>
> I never did.
>
> I learned about various balanced trees in the algorithms course at
> university circa 1992. I suppose we implemented them, in Standard ML
> (which is more or less Haskell).
>
> In C++ I've never needed anything that the standard containers
> couldn't give me, e.g. the features of a search tree exposed by
> std::map, or the std::make_heap stuff if that counts.
>

Much like me - I've never needed to write a tree that needed to grow.

I've done binary searches on a fixed dictionary. ISTR doing one in
Assembler as one of my first professional tasks - would have been around
1980.

I wrote a hashmap about 5 years back for something where there were no
runtime libraries available. And cursed that lack.

But red-back trees and the like? On the rare occasions I've needed one
there's been a run time library to do it for me.

Andy

[Ben Bacarisse]

r...@zedat.fu-berlin.de (Stefan Ram) writes:

> Jeremy Murphy <jeremy.wil...@gmail.com> writes:
>>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++?

<cut>

> I do not associate the concept of a binary tree with a
> specific implementation language. I cannot remember having
> learned it "in a programming language". To me,
>
> tree := pair | leave.
> leave := atom.
> pair :=( tree, tree ).

This definition does not appear to include the empty tree. Reading on,
you reference Lisp, so maybe the empty tree is represented by a special
atom. That works, of course, but it's not obvious from your notation.

> Of course, LISP is /the/ binary tree language par
> excellence, since its data structures: the atom and the
> dotted pair (or, "it's functions »CONS«, »CAR« and »CDR«")
> are exactly what is needed to create a binary tree.

You may be talking the OP rather too literally. I am pretty sure they
mean binary /search/ trees and for that, even in Lisp, you need to
decide how to represent a node. A plain tree of cons cells with atoms
at the leaves is not efficiently searchable.

--
Ben.

[Cholo Lennon]

Wow we learned from the same book :-) Interesting story about Dr. Wirth,
I didn't know it. Certainly Wirth is a great computer scientist, but I
never understood why he created 3 programming languages instead of
evolve Pascal :-O (well Oberon descends from Modula-2 and this from
Modula and Pascal, so in some sense there is an evolution here, but
fragmented).

[Jeremy Murphy]

On Monday, 11 March 2019 08:57:56 UTC+11, Ben Bacarisse wrote:
> (Stefan Ram) writes:
>

> > Jeremy Murphy writes:
> >>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++?
> <cut>
>

> > Of course, LISP is /the/ binary tree language par
> > excellence, since its data structures: the atom and the
> > dotted pair (or, "it's functions »CONS«, »CAR« and »CDR«")
> > are exactly what is needed to create a binary tree.
>
> You may be talking the OP rather too literally. I am pretty sure they
> mean binary /search/ trees and for that, even in Lisp, you need to
> decide how to represent a node. A plain tree of cons cells with atoms
> at the leaves is not efficiently searchable.

I didn't make a huge distinction in my original post, but when I say "binary tree" I do simply mean, for example, what Knuth defines in Volume 1.

A binary _search_ tree is the same structure with extra requirements and constraints, and it's an important case because it's what a lot of people associate with a binary tree.

Jeremy

[Ben Bacarisse]

Jeremy Murphy <jeremy.wil...@gmail.com> writes:

> On Monday, 11 March 2019 08:57:56 UTC+11, Ben Bacarisse wrote:
>> (Stefan Ram) writes:
>>
>> > Jeremy Murphy writes:
>> >>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++?
>> <cut>
>>
>> > Of course, LISP is /the/ binary tree language par
>> > excellence, since its data structures: the atom and the
>> > dotted pair (or, "it's functions »CONS«, »CAR« and »CDR«")
>> > are exactly what is needed to create a binary tree.
>>
>> You may be talking the OP rather too literally. I am pretty sure they
>> mean binary /search/ trees and for that, even in Lisp, you need to
>> decide how to represent a node. A plain tree of cons cells with atoms
>> at the leaves is not efficiently searchable.
>
> I didn't make a huge distinction in my original post, but when I say
> "binary tree" I do simply mean, for example, what Knuth defines in
> Volume 1.

I went back to your original post and you were clear that you were
talking about binary trees in general. It might have been a tad clearer
had you not specified binary because that can lead people to consider
specific uses. Knuth, of course, talks about trees in general with
binary trees as a particular case.

Anyway, I see my comment to Stefan Ram is wrong. It's not that he's
being overly literal but just too narrow. The trees in Knuth have data
at the nodes whether the nodes are leaf nodes or internal nodes. You
can model these in Lisp, but Lisp's plain S-expression built with CONS,
CAR and CDR are not binary trees in Knuth's more abstract sense.

Knuth's trees correspond more closely to this Haskell type:

Tree a = Node a [Tree a]

with the consequence that they can't be empty -- every tree has a root
node.

--
Ben.

[Öö Tiib]

On Sunday, 10 March 2019 05:13:11 UTC+2, Jeremy Murphy wrote:
> 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++?

About binary trees I read first from some Russian algorithm
textbook (possibly translation) for either Fortran or PL/I in
eighties. First binary tree that I wrote in C++ was AVL tree at
start of nineties in process of self-educating 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!

I have never used binary trees that were not binary search
trees. When there has been need for a tree that is not search
tree then it was not binary tree that was needed. Also for
searching the hash table is often worth considering as
alternative to binary search tree.

> Secondly, if you use a (general) binary tree occasionally now, which implementation do you use?

In C++ I have lately only used the trees from Boost.Intrusive.
These work fine in tests and are easy to switch between (for
comparing performance) and allow enough flexibility for whatever
usage of a raw binary tree.

> 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. :)

I don't think my career was anyhow typical.

[James Kuyper]

On 3/9/19 22:13, Jeremy Murphy wrote:
>
> 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++?

> And if you were never taught it, I'd still be interested to hear that!

I never did. I learned how to implement binary trees in C, and at a
later time I learned how write C++, and what I learned about C should
have continued to work in C++ - but I never put that assumption to the
test. That's because, in any context where I would want to use a binary
tree if I were working in C, I would normally use one of the standard
associative containers if I'm working in C++.

[Bonita Montero]

>> I learned how to implement binary trees in C,

> Since they say that every C program is a C++ program,
> I hope C is not too off-topic here.

Arrrrgh, Stefan, you're such a mega-idiot.
Since he only told how he did learn this and he not posted a non-c++
-conforming implementation of any type of binary tree this statement
absolutely isn't off-topic.
You're just trying to elevate your authority about his because you
have a low self-esteem.

> Ten years ago I was hired by a university to teach C
> to a scientist, and one of the things on the wishlist
> were binary trees.

I wish I will never get tought anything from a compulsive person like
you.

[Chris M. Thomasson]

On 3/9/2019 7:13 PM, Jeremy Murphy wrote:
>
> 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
>

Fwiw, the first binary tree I ever experienced was from an old Book
about Basic for my Atari. It used an 1d array to hold a binary tree. I
cannot remember the name of he book, but I do remember it was spiral
bound. Damn. That was fun: I was just a little kid. :^)

[James Kuyper]

On 3/11/19 10:38, Stefan Ram wrote:

> James Kuyper <james...@alumni.caltech.edu> writes:
>> I learned how to implement binary trees in C,
>

> Since they say that every C program is a C++ program,

Those who say that aren't quite correct. Almost every C program can,
usually with only minor modifications, be converted into a program that
has the same required behavior whether compiled as C code or as C++
code. This is proof that the languages share a common heritage which has
not yet disappeared, but I would not recommend actually writing code
that way. Those changes often involve code that is sub-optimal in one of
the two languages, and possibly in both.

> I hope C is not too off-topic here.

He explicitly said:
> 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

so mention of C code is entirely appropriate a response to his message.
However, if he's interested in those other languages as well, he should
have changed his question to be directly language independent, and he
should have either posted it in a language-independent forum, or
cross-posted it to all the languages he's interested in.

[Stuart Redmann]

Jeremy Murphy <jeremy.wil...@gmail.com> wrote:
>
> 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
>

I learned about binary search trees in an introductory course for CS at
university around '98 or '99. The course was largely based on Cormen,
Rivest and Lwhatshisname, "Algorithms and Datastructures", IIRC. Great
book, a definite recommendation. They used some Pascalish syntax in their
pseudo-code listings.

Later on I implemented an AVL tree in C++, just for fun (my first
template). The course also covered Red-Black-trees and B-trees, but I liked
AVL trees more. I have a vague recollection of my wife implementing an AVL
tree in Ada95 (she's a mathematician, and they get different CS courses, at
least in our university).

Regards,
Stuart

[Marcel Mueller]

Am 10.03.19 um 09:17 schrieb Jorgen Grahn:

>> 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?
>

> I never did.

Same here. I took a short look at the concept and decided that overhead
of /binary/ trees is by far too high and probably never used them
anymore. This applies to all kinds ob binary trees like R-B trees or AVL.

I prefer B-Trees, or for certain applications maybe a Trie.

> In C++ I've never needed anything that the standard containers
> couldn't give me, e.g. the features of a search tree exposed by
> std::map, or the std::make_heap stuff if that counts.

From my point of view a B-Tree is missing in C++ (and many other
languages). I closed this gap at least in C++, Java and C# projects.


Marcel