1. C# / Говнокод #16190

    +138

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    67. 67
    68. 68
    69. 69
    70. 70
    71. 71
    72. 72
    73. 73
    74. 74
    75. 75
    76. 76
    77. 77
    78. 78
    79. 79
    80. 80
    81. 81
    82. 82
    83. 83
    84. 84
    85. 85
    86. 86
    87. 87
    88. 88
    89. 89
    90. 90
    91. 91
    92. 92
    93. 93
    bool ExcludeCase4(int iDepth)
        {
            MyNodeType pN = mPath[iDepth];
            if (pN != null)
                if (pN.AuxField.bRed) return false;

            MyNodeType pP = mPath[iDepth - 1];
                if (!pP.AuxField.bRed) return false;

            MyNodeType pS;

            if (LeftSon(iDepth))
                pS = pP.pRight;
            else
                pS = pP.pLeft;

            if (pS == null)
            {
                pP.AuxField.bRed = false;
                iDepthBad = -1;
                return true;
            }

            if (pS.AuxField.bRed) return false;

            MyNodeType pSL = pS.pLeft;
            if (pSL != null)
                if (pSL.AuxField.bRed) return false;

            MyNodeType pSR = pS.pRight;
            if (pSR != null)
                if (pSR.AuxField.bRed) return false;

            pS.AuxField.bRed = true;
            pP.AuxField.bRed = false;

            iDepthBad = -1;
            
            return true;
// Дерево стало хорошим. Корректировать больше не надо.
        }

        bool ExcludeCase6(int iDepth)
        {
            MyNodeType pN, pP, pS;
            bool bLeft, bRedP;

            pN = mPath[iDepth];
            if (pN != null)
            if (pN.AuxField.bRed) return false;

            pP = mPath[iDepth - 1];
            bRedP = pP.AuxField.bRed;

            bLeft = LeftSon(iDepth);

            if (bLeft)
                pS = pP.pRight;
            else
                pS = pP.pLeft;

            if (pS == null) return false;
            if (pS.AuxField.bRed) return false;

            MyNodeType pSL, pSR, p2, p3;

            pSL = pS.pLeft;
            pSR = pS.pRight;

            if (bLeft)
            {
                if (pSR == null || pSR != null && !pSR.AuxField.bRed)
                {
                    if (pSL == null) return false;
                    if (!pSL.AuxField.bRed) return false;
// Сюда попали => это Случай 5.

                    p2 = pSL.pRight;
                    pSL.pRight = pS;
                    pS.pLeft = p2;
                    pSL.AuxField.bRed = false;
                    pS.AuxField.bRed = true;

                    pP.pRight = pSL;
                    pSR = pS;
                    pS = pSL;
                }
                else
                if (!pSR.AuxField.bRed) return false;

// Сюда попали => это Случай 6.

           ,......}

    кусочек красно-черного дерева, необходимый, но не достаточный

    Запостил: lavrov, 18 Июня 2014

    Комментарии (4) RSS

    • ava wvxvw 18.06.2014 23:48 # 0

      Если это удаление, то может так и надо. Разбираться лень, но по памяти, там что-то такое и получается, разве что названия переменных херовые, а так может так и надо.
      Ответить

      • ava bormand 19.06.2014 05:51 # 0

        Ну да, красно-черное дерево - это задачка не для слабонервных ;)

        Но, емнип, нормальная реализация не настолько длинная, т.к. там повороты узлов выносят в отдельные функции, и все 6(?) случаев не рассматривают по-отдельности.
        Ответить

        • ava kegdan 19.06.2014 11:21 # 0

          >>Ну да, красно-черное дерево - это задачка не для слабонервных ;)

          Простая задачка. Мы на 2 курсе делали на выбор красно-черное или АВЛ дерево. Я делал АВЛ, поэтому КЧ помню не очень
          Ответить

          • ava bormand 19.06.2014 12:15 # 0

            > Простая задачка.
            А я пишу, что сложная? Она просто муторная и требующая много внимательности и хорошего покрытия тестами. Лишний раз не хочется такое писать. Благо есть std::map, который, емнип, через красно-черное дерево и запилен.

            P.S. AVL вроде бы чуть проще реализуется.
            Ответить

    Добавить комментарий