借人气问问，C++二叉树 - 未名空间MITBBS历史存档

r*82014-07-09 07:07

1 楼

我在看C++，看到二叉树，谷歌一下，发现是个很基础的东西。对搜索、索引、添加数
据都很有用。
既然这么有用，这么重要，别的语言怎么没有呢？
我以前学过一些别的语言，例如，Basic、PHP、Python、R、MySQL、MATLAB、FORTRAN
、JAVA Script、、等等，为啥都不要二叉树，照样搜索，照样存储。
C++一定要用二叉树吗？
谢谢各位高人指点。

M*a2014-07-09 07:07

2 楼

哈哈。顶一下。高人来解释。

d*12014-07-09 07:07

3 楼

有，但是实现起来效率不高且麻烦。
C/C++的优点之一就是运行的速度和算法效率，所以有相当一部分人用C++就是为了算法
和速度，用算法的人多了，所以愿意讨论和实现的人就多了。
Basic PHP Python ...的和C++比起来，特点是入门容易，开发速度快，管理起来（相
对）简单。所以同时要用到这些语言和二叉树检索的机会太少了，用的少，基本也就没
人讨论了。

FORTRAN

【在 r*****8 的大作中提到】

: 我在看C++，看到二叉树，谷歌一下，发现是个很基础的东西。对搜索、索引、添加数
: 据都很有用。
: 既然这么有用，这么重要，别的语言怎么没有呢？
: 我以前学过一些别的语言，例如，Basic、PHP、Python、R、MySQL、MATLAB、FORTRAN
: 、JAVA Script、、等等，为啥都不要二叉树，照样搜索，照样存储。
: C++一定要用二叉树吗？
: 谢谢各位高人指点。

c*72014-07-09 07:07

4 楼

二叉树是算法吧，这个跟语言没关系。

z*a2014-07-09 07:07

5 楼

二叉树是一种数据结构，理论上任何编程语言都可以实现，只不过c/c++的指针实现起
来效率高

FORTRAN

【在 r*****8 的大作中提到】

: 我在看C++，看到二叉树，谷歌一下，发现是个很基础的东西。对搜索、索引、添加数
: 据都很有用。
: 既然这么有用，这么重要，别的语言怎么没有呢？
: 我以前学过一些别的语言，例如，Basic、PHP、Python、R、MySQL、MATLAB、FORTRAN
: 、JAVA Script、、等等，为啥都不要二叉树，照样搜索，照样存储。
: C++一定要用二叉树吗？
: 谢谢各位高人指点。

c*z2014-07-09 07:07

6 楼

不发葵花版是怕被拍死么？

FORTRAN

【在 r*****8 的大作中提到】

: 我在看C++，看到二叉树，谷歌一下，发现是个很基础的东西。对搜索、索引、添加数
: 据都很有用。
: 既然这么有用，这么重要，别的语言怎么没有呢？
: 我以前学过一些别的语言，例如，Basic、PHP、Python、R、MySQL、MATLAB、FORTRAN
: 、JAVA Script、、等等，为啥都不要二叉树，照样搜索，照样存储。
: C++一定要用二叉树吗？
: 谢谢各位高人指点。

r*82014-07-09 07:07

7 楼

不管计算机发展多快，总有更大的计算要求，所以速度和效率都很重要。
但是，比如，R用来算大数据的，也用不着什么二叉树啊。
MySQL，数据库专门用来存储和搜索的，也用不着二叉树。
是不是C++/C太原始了，别的语言里二叉树已经是语言的一部分了。

【在 d**********1 的大作中提到】

: 有，但是实现起来效率不高且麻烦。
: C/C++的优点之一就是运行的速度和算法效率，所以有相当一部分人用C++就是为了算法
: 和速度，用算法的人多了，所以愿意讨论和实现的人就多了。
: Basic PHP Python ...的和C++比起来，特点是入门容易，开发速度快，管理起来（相
: 对）简单。所以同时要用到这些语言和二叉树检索的机会太少了，用的少，基本也就没
: 人讨论了。
:
: FORTRAN

r*82014-07-09 07:07

8 楼

是怕被拍死。

【在 c*****z 的大作中提到】

: 不发葵花版是怕被拍死么？
:
: FORTRAN

f*p2014-07-09 07:07

9 楼

那儿专门管爆菊。

【在 r*****8 的大作中提到】

: 是怕被拍死。

c*p2014-07-09 07:07

10 楼

你说的应该是二叉搜索树BST。
有些数据结构的底层实现实际上是用BST及其变种实现的，你没有直观地看到BST而已。
就我所知，C++里面的set是用红黑树（平衡BST）实现的。

FORTRAN

【在 r*****8 的大作中提到】

: 我在看C++，看到二叉树，谷歌一下，发现是个很基础的东西。对搜索、索引、添加数
: 据都很有用。
: 既然这么有用，这么重要，别的语言怎么没有呢？
: 我以前学过一些别的语言，例如，Basic、PHP、Python、R、MySQL、MATLAB、FORTRAN
: 、JAVA Script、、等等，为啥都不要二叉树，照样搜索，照样存储。
: C++一定要用二叉树吗？
: 谢谢各位高人指点。

D*t2014-07-09 07:07

11 楼

re

FORTRAN

【在 r*****8 的大作中提到】

: 我在看C++，看到二叉树，谷歌一下，发现是个很基础的东西。对搜索、索引、添加数
: 据都很有用。
: 既然这么有用，这么重要，别的语言怎么没有呢？
: 我以前学过一些别的语言，例如，Basic、PHP、Python、R、MySQL、MATLAB、FORTRAN
: 、JAVA Script、、等等，为啥都不要二叉树，照样搜索，照样存储。
: C++一定要用二叉树吗？
: 谢谢各位高人指点。

z*62014-07-09 07:07

12 楼

感觉你还是要好好提高一下姿势水平。
首先，二叉树是一种数据结构，与语言本身无关，与算法也没有直接关系。
其次，二叉树只是树型结构中最基本的一种，其扩展还有二叉平衡术，红黑树，B树等
等，这些数据结构广泛用于文件系统，数据库等领域。
另外，关于搜索，无论你用什么语言，你都可以选择高效算法，也都可以选择低效算法
。你所说的其他语言没有用，可能性有两个：第一，你没有用；第二，你没有显示的用
，但是事实上你所用的函数已经帮你完成了这些工作。比如你用python里面的map来存
储和搜索，你自己没有显示的用到任何树结构，但是python内部在实现的时候有可能就
是用了某些树的结构。这一点在C++也一样。你可以选择自己从头实现，也可以选择直
接使用各类函数。
最后，希望你能继续努力学习C++。语言学习不在数量，在于质量。能够精通一门比泛
泛学习多门语言更有意义，也更见功力。

j*w2014-07-09 07:07

13 楼

Binary tree is a data structure.
C/C++ is a programming language.
Both are related but not completely the same.
English is a language.
England is part of UK.
Both are related, but not the same thing.

【在 r*****8 的大作中提到】

: 不管计算机发展多快，总有更大的计算要求，所以速度和效率都很重要。
: 但是，比如，R用来算大数据的，也用不着什么二叉树啊。
: MySQL，数据库专门用来存储和搜索的，也用不着二叉树。
: 是不是C++/C太原始了，别的语言里二叉树已经是语言的一部分了。

t*v2014-07-09 07:07

14 楼

LZ应该看看《数据结构》

Z*42014-07-09 07:07

15 楼

还好卤煮只是被轻拍。。
卤煮没关系，there is no stupid questions!
Ask anything if you want.

d*82014-07-09 07:07

16 楼

好的数据结构基本都是在底层上实现，比如数据库搜索，页面搜索。MySQL的数据结构
是类似于二叉树的B-tree,B+tree，当然还有其他的结构像Hash。C++就是为了实现这些
底层的结构和算法的，所以C++很让人痛苦。网络编程就基本不用C++。

FORTRAN

【在 r*****8 的大作中提到】

: 我在看C++，看到二叉树，谷歌一下，发现是个很基础的东西。对搜索、索引、添加数
: 据都很有用。
: 既然这么有用，这么重要，别的语言怎么没有呢？
: 我以前学过一些别的语言，例如，Basic、PHP、Python、R、MySQL、MATLAB、FORTRAN
: 、JAVA Script、、等等，为啥都不要二叉树，照样搜索，照样存储。
: C++一定要用二叉树吗？
: 谢谢各位高人指点。

b*b2014-07-09 07:07

17 楼

C++找到好的类库，也可以不用自己实现。
其他的语言也可以自己从头写一个二叉树。

s*i2014-07-09 07:07

18 楼

烫烫烫烫烫

i*q2014-07-09 07:07

19 楼

You have to keep the tree balanced, therefore, no one call their tree binar
search tree when they use it. They call them black red tree or AVL tree. The
benefit of Java or python is to not code your own tree, but call built-in
libs which have tree or hash implemented internally.

FORTRAN

【在 r*****8 的大作中提到】

: 我在看C++，看到二叉树，谷歌一下，发现是个很基础的东西。对搜索、索引、添加数
: 据都很有用。
: 既然这么有用，这么重要，别的语言怎么没有呢？
: 我以前学过一些别的语言，例如，Basic、PHP、Python、R、MySQL、MATLAB、FORTRAN
: 、JAVA Script、、等等，为啥都不要二叉树，照样搜索，照样存储。
: C++一定要用二叉树吗？
: 谢谢各位高人指点。

r*82014-07-09 07:07

20 楼

“最后，希望你能继续努力学习C++。语言学习不在数量，在于质量。能够精通一门比
泛泛学习多门语言更有意义，也更见功力。”
谢谢指点！
“语言学习不在数量，在于质量。”
这些语言都是被逼无奈才学的，工作需要，不同平台，不同环境，只好继续学。数据处
理完了，或者是达到目的了，就不用了。
“你所说的其他语言没有用，可能性有两个：第一，你没有用；第二，你没有显示的用
，但是事实上你所用的函数已经帮你完成了这些工作。”
我很同意，Python、R里面建立多维矩阵，数据量也很大，只是一个命令，没说怎么建
的。搜索多维矩阵，也只是一个函数，没显示怎么搜索。估计里面用到了二叉结构。

：最后，希望你能继续努力学习C++。语言学习不在数量，在于质量。能够精通一门比泛
：泛学习多门语言更有意义，也更见功力。

【在 z*******6 的大作中提到】

: 感觉你还是要好好提高一下姿势水平。
: 首先，二叉树是一种数据结构，与语言本身无关，与算法也没有直接关系。
: 其次，二叉树只是树型结构中最基本的一种，其扩展还有二叉平衡术，红黑树，B树等
: 等，这些数据结构广泛用于文件系统，数据库等领域。
: 另外，关于搜索，无论你用什么语言，你都可以选择高效算法，也都可以选择低效算法
: 。你所说的其他语言没有用，可能性有两个：第一，你没有用；第二，你没有显示的用
: ，但是事实上你所用的函数已经帮你完成了这些工作。比如你用python里面的map来存
: 储和搜索，你自己没有显示的用到任何树结构，但是python内部在实现的时候有可能就
: 是用了某些树的结构。这一点在C++也一样。你可以选择自己从头实现，也可以选择直
: 接使用各类函数。

z*e2014-07-09 07:07

21 楼

因为树结构对比hashcode为代表的索引方式
仅仅在需要删除的时候，才体现出起优势来
删除时候reorg的话，直接往上依次弹出就好
如果不需要删除，仅仅是插入，新增这些的话
效率不如hashtable，更不如后续的各种优化后的hashtable
还有就是前面说的各种db，底层也就是b-tree
不过现在已经发现这个结构有些老了
正在讨论如何优化，这就是newsql
tree的确是很老的结构了，类似牛顿
但是hashcode的发明，类似爱因斯坦

z*e2014-07-09 07:07

22 楼

r是高阶语言，哪里用来算什么大数据
用来表达一些idea还差不多
真正计算都是压给那些pkg，比如scipy或者hadoop这些
r全部load数据到内存，根本算不出来
mysql底层实现就用了b-tree
c主要用来写一些底层的软件，os, db还有jvm, r这些
其它语言相对c是一种高阶的存在
最后一句是对的
其它语言甚至都不是二叉树是语言的一部分
而是hashtable这种结构是语言的一部分了
全部都是key-value pair，所有语言，到底层都是c
只有一些相对类库比较全的语言，你才能容易找到树结构
比如java里面就有treemap，但是treemap使用次数比起hashmap来说
那不知道是要小多少倍，人类发展这么多年，树有些old了
前面有人说set，set也可以多种实现，treeset比起hashset来说
我估计很多人甚至都不知道有treeset这个类
类似的还有list，arraylist比起linkedlist来说，要常用太多

【在 r*****8 的大作中提到】

: 不管计算机发展多快，总有更大的计算要求，所以速度和效率都很重要。
: 但是，比如，R用来算大数据的，也用不着什么二叉树啊。
: MySQL，数据库专门用来存储和搜索的，也用不着二叉树。
: 是不是C++/C太原始了，别的语言里二叉树已经是语言的一部分了。

i*l2014-07-09 07:07

23 楼

你没想过查找吧，hashtable只能吃瘪了

【在 z****e 的大作中提到】

: 因为树结构对比hashcode为代表的索引方式
: 仅仅在需要删除的时候，才体现出起优势来
: 删除时候reorg的话，直接往上依次弹出就好
: 如果不需要删除，仅仅是插入，新增这些的话
: 效率不如hashtable，更不如后续的各种优化后的hashtable
: 还有就是前面说的各种db，底层也就是b-tree
: 不过现在已经发现这个结构有些老了
: 正在讨论如何优化，这就是newsql
: tree的确是很老的结构了，类似牛顿
: 但是hashcode的发明，类似爱因斯坦

z*e2014-07-09 07:07

24 楼

我没想过get方法？你确定吗？
点拨一下，看看会不会开窍
有个单词叫做amortized
hashtable对于tree的优化
跟
arraylist对于linkedlist的优化
是非常相似的

【在 i******l 的大作中提到】

: 你没想过查找吧，hashtable只能吃瘪了

o*e2014-07-09 07:07

25 楼

树结构可以实现有序的元素访问这一点hash不容易实现吧 : )
而且我觉得树对数据结构和算法而言最大的贡献在于它优化后的高度总是 log(n) 从
而在很多 (用树来实现的) 有意思的算法里引入了对数复杂度的概念比多项式复杂度
还是强很多

【在 z****e 的大作中提到】

: 我没想过get方法？你确定吗？
: 点拨一下，看看会不会开窍
: 有个单词叫做amortized
: hashtable对于tree的优化
: 跟
: arraylist对于linkedlist的优化
: 是非常相似的

r*p2014-07-09 07:07

26 楼

买买提上的马工可真多……

G*n2014-07-09 07:07

27 楼

二叉树是数据结构，很多语言library的container很多都是二叉树的结构，比如c++里
STL的Map，所以你要知道这个。

FORTRAN

【在 r*****8 的大作中提到】

: 我在看C++，看到二叉树，谷歌一下，发现是个很基础的东西。对搜索、索引、添加数
: 据都很有用。
: 既然这么有用，这么重要，别的语言怎么没有呢？
: 我以前学过一些别的语言，例如，Basic、PHP、Python、R、MySQL、MATLAB、FORTRAN
: 、JAVA Script、、等等，为啥都不要二叉树，照样搜索，照样存储。
: C++一定要用二叉树吗？
: 谢谢各位高人指点。

r*82014-07-09 07:07

28 楼

各位专家说得太好了，让我长见识了。
我不是真正的码工，只是工作中需要什么语言就学什么语言，用完就扔，所以学了那么
多语言，无一精通。
再弱弱的问一句，C/C++中的指针，是不是也是底层的东西？
指针用起来很不顺手，没有指针的语言也是一大把。

【在 r**p 的大作中提到】

: 买买提上的马工可真多……