有没有更好的方法来找到最低的共同祖先?
发布时间:2020-12-16 09:30:36 所属栏目:百科 来源:网络整理
导读:我之前已经问过类似的问题,但我认为我的解决方案要简单得多.特别是与 Wikipedia相比. 请证明我错了! 如果您的树具有具有给定数据结构的节点: struct node{ node * left; node * right; node * parent; int key;} 你可以写一个这样的函数: node* LCA(node*
我之前已经问过类似的问题,但我认为我的解决方案要简单得多.特别是与
Wikipedia相比.
请证明我错了! 如果您的树具有具有给定数据结构的节点: struct node { node * left; node * right; node * parent; int key; } 你可以写一个这样的函数: node* LCA(node* m,node* n) { // determine which of the nodes is the leftmost node* left = null; node* right = null; if (m->key < n->key) { left = m; right = n; } else { left = n; right = m; } // start at the leftmost of the two nodes,// keep moving up the tree until the parent is greater than the right key while (left->parent && left->parent->key < right->key) { left = left->parent; } return left; } 这段代码非常简单,最坏的情况是O(n),平均情况可能是O(logn),特别是如果树是平衡的(其中n是树中的节点数). 解决方法
你的算法看起来没问题,至少我想不出更好的东西.请注意,您不需要父指针;相反,您可以从根目录开始沿着树向下,找到第一个节点,其键位于两个初始键之间.
但是,你的问题与Tarjan解决的问题无关.首先,你考虑二元树,他考虑n-ary树;但这可能是一个细节.更重要的是,你考虑搜索树,而Tarjan考虑一般树(没有按键排序).您的问题要简单得多,因为根据密钥,您可以猜测某个节点必须在树中的位置. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |