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

T23_Insert (root, k, data)

1 root – корень 2-3 дерева

2 k –ключ

3 data - данные

4 lt ← Create_Leaf (k, data)

5 if root = nil

6 then root ← Create_Internal

7 son1[ root ] ← lt

8 son2[ root ] ← son3[ root ] ←nil

9 return TRUE

10 if son2[ root ] = nil

11 then if key[son1] < k

12 then son2[ root ] ← lt

13 low2[ root ]← k

14 return TRUE

15 else if key[son1] > k

16 then son2[ root ] ← son1[ root ]

17 low2[ root ] ←key[son1[ root ]]

18 son1[ root ] ← lt

19 return TRUE

20 else Delete_Leaf (lt)

21 return FALSE

22 inserted ← Insert1 (root, lt, tbk, lbk)

23 if inserted = TRUE

24 then if tbk ≠ nil

25 then temp ← root

26 root ← new Internal

27 son1[ root ] ← temp

28 son2[ root ] ← tbk

29 low2[ root ] ← lbk

30 son3[ root ] ← nil

31 return inserted

T23_Insert1(t, lt, tup, lup)

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

2 lt – новый узел - лист

3 tup - возвращаемый после расщепления адрес нового узла

4 lup – возвращаемый минимальный ключ в поддереве нового узла

5 tup ← nil

6 if₁ type[ t ] = LEAF

7 then₁ if₂ key[ t ] = key[ lt ]

8 then₂ return FALSE

9 else₂ tup ← lt

10 if₃ key[ t ] < key[ lt ]

11 then₃ lup ← key[ lt ]

12 else₃ lup ← key[ t ]

13 temp ₁ ← key[ t ]

14 key[ t ] ← key[ lt ]

15 key[ lt ] ← temp ₁

16 temp ₂ ← data[ t ]

17 data[ t ] ← data[ lt ]

18 data[ lt ] ← temp ₂

19 return TRUE

20 t – внутренний узел

21 if₄ key[ lt ] < low2[ t ]

22 then₄ child ← 1

23 w ← son1[ t ]

24 else₄ if₅ son3[ t ] = nil or (son3[ t ] ≠ nil and key[ lt ] < low3[ t ])

25 then₅ child ← 2

26 w ← son2[ t ]

27 else₅ child ← 3

28 w ← son3[ t ]

29 inserted ← T23_Insert1 (w, lt, tbk, lbk)

30 if₆ inserted = TRUE

31 then₆ if₇ tbk ≠ nil

32 then₇ if₈ son3[ t ] = nil узел имел 2-х сыновей

33 then₈ if₉ child = 2

34 then₉ son3[ t ] ← tbk

35 low3[ t ] ← lbk

36 else₉ son3[ t ] ← son2[ t ]

37 low3[ t ] ← low2[ t ]

38 son2[ t ] ← tbk

39 low2[ t ] ← lbk

40 else₈ узел имел 3-х сыновей

41 tup ← Create_Internal()

42 if₁₀ child = 3

43 then₁₀ выполнялась вставка в третье поддерево

44 son1[ tup ] ← son3[ t ]

45 son2[ tup ] ← tbk

46 son3[ tup ] ← nil

47 low2[ tup ] ← lbk

48 son3[ t ] ← nil

49 lup ← low3[ t ]

50 else₁₀ выполнялась вставка в 1-е или 2-е поддерево

51 son2[ tup ] ← son3[ t ]

52 low2[ tup ] ← low3[ t ]

53 son3[ tup ] ← nil

54 if₁₁ child = 2 выполнялась вставка во 2-е подд-во

55 then₁₁ son1[ tup ] ← tbk

56 lup ← lbk

57 if₁₂ child = 1 выполнялась вставка во 1-е подд-во

58 then₁₂ son1[ tup ] ← son2[ t ]

59 son2[ t ] ← tbk

60 lup ← low2[ t ]

61 low2[ t ] ← lbk

62 son3[ t ] ← nil

63 return inserted

---

Дата добавления: 2015-11-04