كيف يمكنني تنفيذ شجرة شبكية تؤدي عملية التعرج ، وليس أولاً؟

Question

بالنسبة لفئة خوارزميات هياكل البيانات الخاصة بي ، تم تكليفها بتنفيذ شجرة شباك في هاسكل. الخوارزمية الخاصة بي لعملية الرشوة هي كما يلي:

1. إذا كانت العقدة المراد تمييزها هي الجذر ، فسيتم إرجاع الشجرة غير المتغيرة.
2. إذا كانت العقدة المراد تمييزها هي مستوى واحد من الجذر ، فسيتم إجراء عملية متعرج وإرجاع الشجرة الناتجة.
3. إذا كانت العقدة المراد تمييزها هي مستويين أو أكثر من الجذر ، فسيتم إجراء عملية متعرجة أو متعرج على نتيجة تشويش الشجرة الفرعية بدءًا من تلك العقدة ، ويتم إرجاع الشجرة الناتجة.

هذا صحيح وفقا لمعلمي. لكن، وصف ويكيبيديا لشجرة شرب يقول الخطوة المتعرجة "ستتم فقط كخطوة أخيرة في عملية تطفو" ، بينما في خوارزمي ، فهي الخطوة الأولى في عملية تطفو.

أرغب في تنفيذ شجرة شبكية تؤدي عملية التعرج إلى الأمام بدلاً من أولاً ، لكنني لست متأكدًا من الطريقة التي سيتم بها القيام بذلك. يبدو لي أن مثل هذه الخوارزمية ستصبح أكثر تعقيدًا ، حيث ترى كيف يحتاج المرء إلى العثور على العقدة التي يتم تنشيطها قبل أن يتم تحديد ما إذا كان ينبغي إجراء عملية متعرجة أم لا.

كيف يمكنني تنفيذ هذا في Haskell (أو لغة وظيفية أخرى)؟

مثال

في هذا المثال ، نبحث عن القيمة 4 ، مما دفعنا إلى تنشيطها إلى أعلى الشجرة.

خوارزمية بلدي (متعرج كخطوة أولى)

1             1                   4
 \             \                 /
  2      zig    2    zig-zig    2
   \     -->     \   ------>   / \
    3             4           1   3
     \           /
      4         3

خوارزمية ويكيبيديا (تعرج كخطوة الأخيرة)

1                   1           4
 \                   \         /
  2      zig-zig      4  zig  1
   \     ------>     /   -->   \
    3               3           3
     \             /           /
      4           2           2

كلتا الشجرتين صالحة ، لكن لديهم هياكل مختلفة. أريد تنفيذ اللغة الثانية بلغة وظيفية ، ويفضل أن يكون هاسكل.

Answer 1

المفتاح هو بناء مسار إلى القيمة المراد انتشاره ، ثم إعادة بناء الشجرة من القاع ، مستويين في وقت ممكن إذا كان ذلك ممكنًا (بحيث يمكن إجراء تحديد التعرج مقابل التعرج):

data Tree a = Empty | Node a (Tree a) (Tree a)
    deriving (Eq, Show)

data Direction = LH | RH
    deriving (Eq, Show)


splay :: (Ord a) => a -> Tree a -> Tree a
splay a t = rebuild $ path a t [(undefined,t)]
    where path a Empty ps = ps
          path a n@(Node b l r) ps =
              case compare a b of
                  EQ -> ps
                  LT -> path a l $ (LH, l) : ps
                  GT -> path a r $ (RH, r) : ps

          rebuild :: (Ord a) => [(Direction,Tree a)] -> Tree a
          rebuild ((_,n):[]) = n
          rebuild ((LH,x):(_,p):[]) = zigL x p
          rebuild ((RH,x):(_,p):[]) = zigR x p
          rebuild ((LH,x):(LH,p):(z,g):ps) = rebuild $ (z, zigzigL x p g):ps
          rebuild ((RH,x):(RH,p):(z,g):ps) = rebuild $ (z, zigzigR x p g):ps
          rebuild ((RH,x):(LH,p):(z,g):ps) = rebuild $ (z, zigzagL x p g):ps
          rebuild ((LH,x):(RH,p):(z,g):ps) = rebuild $ (z, zigzagR x p g):ps

          zigL (Node x a b) (Node p _ c) = Node x a (Node p b c)
          zigR (Node x a b) (Node p c _) = Node x (Node p c a) b

          zigzigL (Node x a b) (Node p _ c) (Node g _ d) =
              Node x a (Node p b (Node g c d))

          zigzigR (Node x a b) (Node p c _) (Node g d _) =
              Node x (Node p (Node g d c) a) b

          zigzagL (Node x b c) (Node p a _) (Node g _ d) =
              Node x (Node p a b) (Node g c d)

          zigzagR (Node x b c) (Node p _ a) (Node g d _) =
              Node x (Node g d b) (Node p c a)

يمكنك العثور على هذا الرمز ، جنبا إلى جنب مع اختبارات الوحدة القابلة للتشغيل والفحوصات السريعة في بلدي الريبو.

Answer 2

هل أنت متأكد من أنك تقرأ وصف ويكيبيديا بشكل صحيح؟ هناك ثلاثة أنواع من الخطوات: "zig" ، "zig-zig" ، و "zig-zag". خطوة "التعرج" هي مُعرف أن يكون شيئًا يحدث فقط عندما x هو طفل الجذر. على الرغم من الأسماء ، فإن خطوات "Zig-Zig" و "Zig-Zag" لا تحتوي على خطوات "Zig" كمكون أول.

يبدو لي أن تنفيذك يتبع وصف ويكيبيديا في هذا الصدد.

Answer 3

يمكنك المرجع هذه الدورة, ، التي لديها مذكرة محاضرة جيدة للغاية مع كود في OCAML لشجرة splay.