Алгоритм удаления элемента из рандомизированного дерева

RND_Delete(t, k, deleted)

1 t – корень дерева или поддерева

2 k – значение удаляемого ключа

3 deleted – возвращаемый признак удаления

4 if t = nil

5 then deleted ← FALSE

6 return t

7 if k < key[t]

8 then left[t] ← RND_Delete (left[t], k, del)

9 else if k > key[t]

10 then right[t] ← RND_Delete (right[t], k, del)

11 else if Rand()/(Rand_MAX/(n[left[t]]+ n[right[t]]+1)) < n[left[t]]

12 then x ← RND_Join (left[t], right[t])

13 else x ← RND_Join (right[t], left[t])

14 Delete_Node (t)

15 t ← x

16 del ← TRUE

17 deleted ← del

18 if deleted = TRUE

19 then Calc_n(t)

20 return t

RND_Join (a, b)

1 if a = 0

2 then return b

3 if b = 0

4 then return a

5 left ← left[a]

6 right ← right[a]

7 left[a] ← right[a] ← nil

8 n[b] ← n[b]+n[a]

9 n[a] ← 1

10 b ← Root_Insert (b, a)

11 left[b] ← RND_Join (left, left[b])

12 right[b] ← RND_Join (right, right[b])

13 return b

Алгоритм вставки элемента в avl-дерево

AVL_Insert(t, k, data, h, inserted)

1 t – корень дерева / поддерева

2 k –ключ нового элемента

3 data – данные нового элемента

3 iserted – возвращаемый признак вставки

4 h – возвращаемый признак увеличения высоты

5 h ← FALSE

6 if₁ k = key[t]

7 then₁ inserted ← FALSE

8 return t

9 if₂ t = nil

10 then₂ t ← Create_Node(k, data)

11 bal[t] ← 0

12 h ← TRUE

13 inserted ← TRUE

14 return t

15 if₃ k < key[t]

16 then₃ left[t] ← AVL_Insert(left[t], k, data, hh, ins)

17 if₄ hh = TRUE

18 then₄выросла левая ветвь

19 if₅ bal[t] = 1

20 then₅ bal[t] ← 0

21 else₅ if₆ bal[t] = 0

22 then₆ bal[t] ← -1

23 h ← TRUE

24 балансировка

25 else₆ if₇ bal[left[t]] = -1

26 then₇ t ← R (t)

27 else₇ t ← LR (t)

28 else₃ right[t] ← AVL_Insert(right[t], k, data, hh, ins)

29 if₈ hh = TRUE

30 then₈ выросла правая ветвь

31 if₉ bal[t] = -1

32 then₉ bal[t] ← 0

33 else₉ if₁₀ bal[t] = 0

34 then₁₀ bal[t] ← 1

35 h ← TRUE

36 балансировка

37 else₁₀ if₁₁ bal[right[t]] = 1

38 then₁₁ t ← L (t)

39 else₁₁ t ← RL (t)

40 inserted ← ins

41 return t

R (t)

1 x← left[t]

2 left[t] ← right[x]

3 right[x] ← t

4 bal[x] ← bal[t] ← 0

5 return x

LR (t)

1 x ← left[t]

2 y ← right[x]

3 right[x] ← left[y]

4 left[y] ← x

5 left[t] ← right[y]

6 right[y] ← t

7 if bal[y] =-1

8 then bal[t] ← 1

9 else bal[t] ← 0

10 if bal[y] = 1

11 then bal[x] ← -1

12 else bal[x] ← 0

13 bal[y] ← 0

14 return y