fork download
copy 
  1. using System;
  2. using System.Diagnostics;
  3.  
  4. namespace SampleNamespace
  5. {
  6.   public class Node
  7.     {
  8.       public Node parent, left, right;
  9.       public int key;
  10.       public int accum;
  11.     }
  12.  
  13.     public class SampleClass
  14.     {
  15.       static Node treeMinimum(Node x)
  16.       {
  17.         while (x.left != null)
  18.           x = x.left;
  19.         return x;
  20.       }
  21.  
  22.         static Node treeSuccessor(Node x)
  23.         {
  24.           if (x.right != null)
  25.             return treeMinimum(x.right);
  26.  
  27.           Node y = x.parent;
  28.           while ((y != null) && (x == y.right))
  29.           {
  30.             x = y;
  31.             y = y.parent;
  32.           }
  33.           return y;          
  34.         }
  35.  
  36.         static Node accumDelete(ref Node tree, Node z)
  37.           {
  38.             Node y = (z.left == null || z.right == null) ? z : treeSuccessor(z);
  39.             Node x = (y.left != null) ? y.left : y.right;
  40.  
  41.             if (x != null)
  42.               x.parent = y.parent;
  43.  
  44.             if (y.parent == null)
  45.               tree = x;
  46.             else if (y == y.parent.left)
  47.               y.parent.left = x;
  48.             else
  49.               y.parent.right = x;
  50.  
  51.               if (y != z)
  52.                 z.key = y.key;
  53.  
  54.               return y;
  55.           }
  56.  
  57.          static bool accumVerify(Node x, int lb, int ub, int c)
  58.          {
  59.            int k = x.key + c;
  60.            return x == null || (k > lb && k < ub &&
  61.                                 accumVerify(x.left, lb, k, c + x.accum) &&
  62.                                 accumVerify(x.right, k, ub, c + x.accum));
  63.          }
  64.  
  65.         public static void Main()
  66.         {
  67.           Node
  68.             root = new Node { key = 5, accum = 100 },
  69.               a = new Node { parent = root, key = 6, accum = 300 },
  70.                 b = new Node { parent = root, key = 7, accum = 400 },
  71.                   c = new Node { parent = a, key = 10, accum = 50000 };
  72.           root.left = a;
  73.           root.right = b;
  74.           a.left = c;
  75.  
  76.           Console.WriteLine("Verify: {0}", accumVerify(root, int.MinValue, int.MaxValue, 0));
  77.  
  78.  
  79.         } // End of Main function (program statup)
  80.     } // End of SampleClass
  81. } // End of SampleNamespace
  82.  
  83.  
Success #stdin #stdout 0.03s 37928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Verify: False
https://ideone.com/qaZgc
language:
C# (gmcs 5.20.1)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!