爪哇2博客
爪哇2博客

O(Sqrt(height))中的K元树的LCA

如果您想练习数据结构和算法程序,可以通过 100多种数据结构和算法程序.

在本文中,我们将介绍如何在O(Sqrt(height))中找到K元树的最低公祖。 O(n)中的n元树的LCA 复杂。


问题

给定一棵Kary树及其两个竞彩篮球分析。在O(sqrt(height))中有效地计算给定树中竞彩篮球分析的最低公共祖先。
最低共同祖先 是两个竞彩篮球分析的共同祖先,这两个竞彩篮球分析最接近它们,或者可以说它们离根最远。

输入格式:-
在第一行中,给定n个竞彩篮球分析数,随后n-1行包含两个整数,第一个表示父级,第二个表示子级。
之后,给定两个整数,将找到其LCA。

 生命周期评价 一元树

输入 :
61
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
4 10
5 11
6 12
7 13
7 14
8 15
9 16
10 17
11 18
11 19
12 20
14 21
14 22
16 23
16 24
17 25
18 26
19 27
20 28
20 29
22 30
22 31
24 32
25 33
25 34
27 35
27 36
29 37
30 38
32 39
32 40
34 41
35 42
35 43
36 44
37 45
37 46
39 47
39 48
39 49
43 50
43 51
46 52
49 53
49 54
51 55
51 56
52 57
53 58
53 59
53 60
53 61
23 61
输出值 :
16

天真的方法 要找出两个竞彩篮球分析的LCA,将保持两个指针(即每个竞彩篮球分析一个),并继续跳转到两个当前竞彩篮球分析的直接父竞彩篮球分析,并到达两个指针相遇的点,该竞彩篮球分析肯定是我们的LCA 。

但这肯定要花一些时间 O(身高).

但是我们绝对可以在以下方面更有效地实现解决方案 O(√(高度)) 时间。
与其一次跳过一个竞彩篮球分析,我们可以跳过更多对我们没有用的竞彩篮球分析,并最终到达两个竞彩篮球分析​​相遇的所需位置。
现在我们如何实现这一目标?

  • 我们将树分成不同的块 平方尺(小时)尺寸 即每个块将具有Sqrt(height)高度。
  • 现在如果总高度‘h’那棵树是一个完美的正方形,那么我们知道 块总数将为sqrt(h),
    如果树的高度不是完美的正方形怎么办? 仍然块大小将保持sqrt(h),但 块数将在范围内变化 [sqrt(h),sqrt(h)+2] 可以用数学方法观察到。
  • 因此,现在我们将跳过sqrt(h)竞彩篮球分析,而不是跳一个竞彩篮球分析,这将有助于我们实现 sqrt (h)的最坏时间复杂度 尺寸。

怎么样 ?

  • 我们在预处理本身时为每个竞彩篮球分析设置了父级,更重要的是设置了块级父级。每当要求我们找到两个竞彩篮球分析的LCA时, 如果它们属于不同的块,我们首先使它们的块父相同,以便它们至少位于同一块中,因此,要实现使较深的竞彩篮球分析跳到其块父直到两个竞彩篮球分析的块相同。现在,在最坏的情况下,一个竞彩篮球分析将跳过所有块,最大可能为sqrt(h),因此此过程花费的总时间为sqrt(h)。
  • 现在,在两个竞彩篮球分析的块相同之后,我们跳到它们的直接父竞彩篮球分析,直到竞彩篮球分析最终会合,并且该交汇点将是给定竞彩篮球分析的LCA。现在,最大数量的竞彩篮球分析可以跳过其块中的所有竞彩篮球分析,最大数量为sqrt(h)。
  • 因此,该算法的总时间复杂度为:Sqrt(h)+ Sqrt(h)
    = 2 *平方尺(h)
    = O(平方(h))

算法:

  • 在第一个DFS中,我们设置父级,深度,更重要的是找到高度,这有助于我们定义每个块的大小。
  • 找到树的高度后,我们定义树的块大小。
  • 现在,一旦定义了块大小,我们就可以设置树中每个竞彩篮球分析的块父级。
    在设置块父对象时,请记住两点:

    • (i)如果一个竞彩篮球分析和该竞彩篮球分析的父竞彩篮球分析位于相同的块编号中,则它们具有相同的块父竞彩篮球分析,即竞彩篮球分析的块父竞彩篮球分析=父竞彩篮球分析的块父竞彩篮球分析。
    • (ii)如果一个竞彩篮球分析和该竞彩篮球分析的父级位于不同的块号中,则node的块级父级是该竞彩篮球分析的实际父级,即node的块级父级= 父母。
  • 一旦设置了块父级,我们就完成了预处理,剩下的就是处理查询。

如何处理查询?

  1. 如果竞彩篮球分析位于不同的块中,则使更深的竞彩篮球分析跳到其块父竞彩篮球分析,直到它们位于相同的块编号中。
  2. 如果两个竞彩篮球分析的块数相同,则使更深的竞彩篮球分析跳到其直接父竞彩篮球分析,直到它们实际相遇为止。两个竞彩篮球分析实际相遇的这个竞彩篮球分析是LCA。

生命周期评价 sqrtdecomp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
 
组织 .Arpit.爪哇2blog;
 
进口 爪哇.实用程序 .数组列表;
进口 爪哇.实用程序 .扫描器;
 
上市 生命周期评价 sqrtdecomp {
 
    静态的 数组列表<整数>[] ;
    静态的 整型 [] 父母;
    静态的 整型 [] 深度;
    静态的 整型 [] 家长;
    静态的 整型 高度;
    静态的 整型 块大小;
 
    上市 静态的 虚空 主要([] args) {
        扫描器 scn = 扫描器(系统.);
 
         整型 竞彩篮球分析 = scn .nextInt();
         整型 边缘 = 竞彩篮球分析 - 1;
 
         = 数组列表[竞彩篮球分析 + 1];
 
        // 父母 arr存储第i个竞彩篮球分析的父竞彩篮球分析。
        父母 = 整型 [竞彩篮球分析 + 1];
 
        // 家长 arr存储第i个竞彩篮球分析的块父级。
        家长 = 整型 [竞彩篮球分析 + 1];
 
        //深度以存储当前竞彩篮球分析的高度
        深度 = 整型 [竞彩篮球分析 + 1];
        高度 = -1;
 
         对于 ( 整型 i = 0; i < .长度; i ++ ) {
            [i] = 数组列表<>();
        }
 
         对于 ( 整型 i = 0; i < 边缘; i ++ ) {
             整型 父母 = scn .nextInt();
             整型 儿童 = scn .nextInt();
 
            //在父竞彩篮球分析的索引处,我们要添加其子竞彩篮球分析
            [父母].(儿童);
        }
 
        / *此dfs用于设置父级,深度,
          主要是找到
          给出的树,以便我们可以计算我们的
          块大小将为sqrt(height)。
        */
         dfs (1, 0, 0);
 
        / *将高度增加一,因为
        我们计算的高度开始考虑
        根竞彩篮球分析处于第0级,但当然根竞彩篮球分析也
        有助于树的总高度。
         */
        块大小 = ( 整型 ) 数学 . sqrt ( ++ 高度);
 
        / *这又是我们所处的一种DFS
        为每个竞彩篮球分析设置块父级。我们可以
        不像以前那样没有在以前的dfs中做
        我们的高度已预先计算出来,以查找块大小
         */
        setBP(1);
 
        系统..打印(“输出:”+getLCA( scn .nextInt(), scn .nextInt()));
 
    }
 
    上市 静态的 虚空 dfs ( 整型 竞彩篮球分析, 整型 父母, 整型 currDepth) {
        //设置当前竞彩篮球分析的父级和深度。
        父母[竞彩篮球分析] = 父母;
        深度[竞彩篮球分析] = currDepth;
        //向下移动时始终更新最大高度
        //在树中使用顺序遍历。
        高度 = 数学 . 最高 (高度, currDepth);
 
         对于 ( 整型 儿童 : [竞彩篮球分析]) {
            //对所有子竞彩篮球分析重复
            //当前竞彩篮球分析将充当父竞彩篮球分析。
             dfs (儿童, 竞彩篮球分析, currDepth + 1);
        }
 
    }
 
    上市 静态的 虚空 setBP( 整型 竞彩篮球分析) {
 
         整型 父母 = 父母[竞彩篮球分析];
 
        / *查找当前竞彩篮球分析的块号,并
        其父级通过按块大小潜水深度。
        */
         整型 竞彩篮球分析Block = 深度[竞彩篮球分析] / 块大小;
         整型 父母Block = 深度[父母] / 块大小;
 
        / *如果当前竞彩篮球分析和上一个竞彩篮球分析都位于
        同一块,然后位于同一块,那么这意味着
        两个竞彩篮球分析的块大小必须是同一竞彩篮球分析,并且
        因为我们已经计算出parent的块parent,所以
        当前竞彩篮球分析的块父对象将是
        当前竞彩篮球分析的父级。
         */
 
         如果 (竞彩篮球分析Block == 父母Block) {
            家长[竞彩篮球分析] = 家长[父母];
        } 其他 {
            / *如果当前竞彩篮球分析及其父竞彩篮球分析的块为  
            那么这意味着直系父母  
            当前竞彩篮球分析的恰好位于前一个
            块,因此实际   当前的父级
                          竞彩篮球分析也是其块父级。
             */
            家长[竞彩篮球分析] = 父母[竞彩篮球分析];
        }
 
         对于 ( 整型 儿童 : [竞彩篮球分析]) {
            / *对于子竞彩篮球分析重复出现,我们并不是真的
              需要在呼叫中发送家长,我们有
               already calculated  并将它们存储在上一个
                           dfs .
            */
            setBP(儿童);
        }
 
    }
 
    上市 静态的 整型 getLCA( 整型 竞彩篮球分析1, 整型 竞彩篮球分析2) {
 
        / *这是我们减少所有复杂性的部分
        *发生,我们直接跳而不是一对一
        *跳sqrt(height)大小。如果是父代
        两个竞彩篮球分析的*不同,那么我们跳转到
        *阻止DEEPER竞彩篮球分析的父级。我们继续做
        *相同,直到两个竞彩篮球分析的块父级相等。
         */
         (家长[竞彩篮球分析1] != 家长[竞彩篮球分析2]) {
             / *
            *此检查会确保我们使竞彩篮球分析更深
            *如果未进行此检查,则跳转到其块父级
            *那里可能存在两个竞彩篮球分析的情况
            *最终到达根竞彩篮球分析的块父级
             */
             如果 (深度[竞彩篮球分析1] > 深度[竞彩篮球分析2]) {
                竞彩篮球分析1 = 家长[竞彩篮球分析1];
            } 其他 {
                竞彩篮球分析2 = 家长[竞彩篮球分析2];
            }
        }
 
         / *
        *一旦两个竞彩篮球分析的块相同,则此
        *表示两个竞彩篮球分析的LCA必须位于
        *同一块,因此我们现在继续跳到
        *竞彩篮球分析的直接父竞彩篮球分析,直到竞彩篮球分析实际
        *见面,他们见面的时间就是我们的LCA
         */
         (竞彩篮球分析1 != 竞彩篮球分析2) {
 
             如果 (深度[竞彩篮球分析1] > 深度[竞彩篮球分析2]) {
                竞彩篮球分析1 = 父母[竞彩篮球分析1];
            } 其他 {
                竞彩篮球分析2 = 父母[竞彩篮球分析2];
            }
        }
 
        //最终返回两个竞彩篮球分析的LCA
        返回 竞彩篮球分析1;
    }
 
}  
 

那’关于如何在O(Sqrt(height))中查找K元树的最低公共祖先(LCA)。

分享这个

作者

关注作者

相关文章

发表评论

您的电子邮件地址不会被公开。 必需的地方已做标记 *

订阅我们的新闻

获取质量教程到您的收件箱。现在订阅。


成为朋友

©2020 爪哇2博客