R*****i
发帖数: 2126 | 1 这个题目建议用红黑树做可能最快捷有效。红黑树每一次插入，删除都是log(k),求平
均值非常简单，就是根部的那个节点。所以总的计算量是O(nlog(k))。
以下是c/c++代码（需要修改数组，以便一个一个输入）。
#include
#include
#include
#define INDENT_STEP 4
enum rbtree_node_color {RED, BLACK};
typedef struct rbtree_node_t {
int value;
struct rbtree_node_t* left;
struct rbtree_node_t* right;
struct rbtree_node_t* parent;
enum rbtree_node_color color;
} *rbtree_node;
typedef rbtree_node node;
typedef enum rbtree_node_color color;
typedef struct... 阅读全帖 |
|
y*********e
发帖数: 518 | 2 来自主题: JobHunting版 - 一道算法题 按照顺序也可以用Balanced BST，比如RBTree。Java里面的TreeMap是一个RBTree。 |
|
s*********n
发帖数: 35 | 3 好吧。。。不好意思 我理解错了，你意思是参考top实现吧
你说用到了rbtree也make sense, map本身就是rbtree，linux用纯c没有stl只能自己实
现了 |
|
r****t
发帖数: 10904 | 4 我是有这个worry. 如果他改了很多那应该还可以把。这样实现的RBTree 不好直接用在
自己程序里。Python 有个 RBTree module, 如果一定要用我会用那个。
俺贴一个这种比较贴看看，先找一下去。 |
|
w***x
发帖数: 105 | 5 越说越离谱了。。
使用语言本身, 没有难度可言，语言实现的难度确实很不同，c++的compiler要比c的难
n倍。
不同工具构造不同应用。c++哪有那么难使用？stl/boost api哪有那么复杂？api的实
现和使用是两个难度级别。使用rbtree有难度么？分分钟的事情，但如果自己实现bug
free的rbtree呢？恐怕就要几天了。
应用的具体复杂程度，取决于你要实现的目标，这直接决定了语言工具的选择。如果你
非要用java打造unreal4 engine，到最后你会发现你不得不重新实现一个更高性能的
java vm，所以更明智的做法是直接用c++，这是工程上的最优选择。
一些高性能的应用，最后优化阶段会把很多计算步骤优化到microsecond甚至
nanosecond级别，c/c++/asm做起来在自然不过了，不过即使如此，语言本身并不会帮
做太多，对算法的优化，硬件和os架构的理解才是根本，c/c++只不过能保障你的实现
会近似1：1的映射到实际硬件指令上去，java/python这类语言显然并不擅长做这种工
作。
c比c++简单多了，但这并不意味着linux kerne... 阅读全帖 |
|
H*M
发帖数: 1268 | 6 那一般关于augmented data structure的题，就只能嘴上说说了
反正我不记哪些RBTree的functions. |
|
f****4
发帖数: 1359 | 7 sgi stl
the rbtree has parent pointer... |
|
|
j*****4
发帖数: 292 | 9 stl里associative container是用rbtree实现的 |
|
s*****y
发帖数: 897 | 10 linux
freebsd kernel
memory management also use rbtree too. |
|
M********u
发帖数: 42 | 11 avl更加平衡，所以需要更多的cost去maintain tree structure，一般用rbtree |
|
e*********l
发帖数: 136 | 12 stl的map是bst，更精确点是RBTree |
|
G**********s
发帖数: 70 | 13 有没有人在 A/M/G onsite 时候，遇到过以下知识点相关的题呢？
234tree
RBtree
splayTree
nWayMergeSort(External sort)
犹豫是否要花时间把这些也复习。xiexie! |
|
|
d**u
发帖数: 1065 | 15 怎么没关系？！stl的map就是用rbtree实现的。 |
|
d**u
发帖数: 1065 | 16 OK.是我说的不准确。应该说hashtable和rbtree都是dictionary的实现方法。
hashtable的确和tree无关。 |
|
|
h**********c
发帖数: 4120 | 18 top in linux不就是按cpu usage 列topN吗
还有一个老中contributor 呢，不能现身来讲讲有什么高深算法吗？
一开头看见个 #include 'rbtree.h'，心里疙瘩一下，听说过没用过 |
|
l********6
发帖数: 129 | 19 虽然没做过 但是目测复杂度也就是降到nlogn吧 不知道有没有大神能想出线性的解法
nlogn的话就从后往前遍历 用一个set存之前的那些数 然后拿到下一个数的时候 在set
里面找upperbound 然后得出upperbound前面有多少个数 再把这个数插到upperbound之
前 整体上相当于维护一颗bst（实际上是rbtree）
[在 lalo (lalo) 的大作中提到：]
：给一个数组，比如【5，2，6，1】
：对于5，它的右边有两个数字比它小；对于2，它的右边有一个比小；6的右边有1个比
它小；1的右边0个比它小.
：........... |
|
z*********n
发帖数: 1451 | 20 来自主题: JobHunting版 - G一个新题
这题确实应该是kd tree一个典型应用，但是如果自己对如何实现kd tree不熟，不敢乱
说啊，万一让实现一个，搞不出来就挂了。
我以前有个同学就是面试时扯了一下平衡二叉树，然后人家就问你知道哪些平衡二叉树
，他就说了AVL和RBTree，然后对面说，那你随便实现一个我看看吧，然后。。就没有
然后了。。 |
|
|
