Lab 21.1

using System;
using System.Linq;
using System.Text;
using Unit4.CollectionsLib;

namespace ConsoleApplication1
{
    class Program
    {
        private static Random num = new Random();

        //טענת כניסה: מקבלת מספר כלשהו איקס
        //טענת יציאה: מחזירה עץ בינארי רנדומלי בגובה איקס
        static BinTreeNode<int> BuildT(int x)
        {
            int a;
            if (x < 0) return null;
            if (x == 0) return new BinTreeNode<int>(num.Next(1, 21));
            if (x > 0)
            {
                a = num.Next(1, 4);
                if (a == 1)
                    return new BinTreeNode<int>(null, num.Next(1, 21), BuildT(x - 1));
                if (a == 2)
                    return new BinTreeNode<int>(BuildT(x - 1), num.Next(1, 21), null);
                if (a == 3)
                    return new BinTreeNode<int>(BuildT(x - 1), num.Next(1, 21), BuildT(x - 1));
            }
            return null;
        }

        //טענת כניסה: מקבלת עץ בינארי
        //טענת יציאה: מחזירה את מספר הרמות בעץ
        //סיבוכיות O(n)
        public static int Height(BinTreeNode<int> bt)
        {
            if (bt == null) //O(1)
                return -1; //O(1)
            return 1 + Math.Max(Height(bt.GetLeft()), Height(bt.GetRight())); //O(n)
        }

        //טענת כניסה: מקבלת עץ בינארי
        //טענת יציאה: מחזירה אמת אם העץ הוא עץ בינארי מאוזן אחרת מחזירה שקר
        //סיבוכיות O(n^2)
        public static bool Balanced(BinTreeNode<int> t)
        {
            if (t == null) //O(1)
                return true; //O(1)
            if (t.GetLeft() == t.GetRight()) //O(1)
                return true; //O(1)
            if (Math.Abs(Height(t.GetLeft()) - Height(t.GetRight())) > 1) //O(n) כי מזומנות פעולות שהסיבוכיות שלהן היא O(n)
                return false; //O(1)
            return Balanced(t.GetLeft()) && Balanced(t.GetRight()); //O(n^2)
        }

        static void Main(string[] args)
        {
            BinTreeNode<int> t = BuildT(3);
            Console.WriteLine(Balanced(t));
            BinTreeUtils.ShowTree(t);
        }
    }
}

///

using System;
using System.Linq;
using System.Text;
using Unit4.CollectionsLib;

namespace ConsoleApplication1
{
    public class Collec
    {
        private Stack<int> s;
        private int tail;


        public Collec()
        {
            this.s = new Stack<int>();
        }

        public Collec(int n)
        {
            this.s = new Stack<int>();
            this.s.Push(n);
            this.tail = n;
        }

        //טענת כניסה: מקבלת מספר n
        //טענת יציאה: בודקת אם אפשר להוסיף אותו לאוסף, מחזירה אמת אם אפשר אחרת מחזירה שקר. אם אפשר להוסיף אותו לאוסף היא מוסיפה
        //סיבוכיות O(1)
        public bool Add(int n)
        {
            if (this.s.IsEmpty()) //O(1)
            {
                this.tail = n; //O(1)
                this.s.Push(n); //O(1)
                return true; //O(1)
            }
            if (this.s.Top() > n) //O(1)
                return false; //O(1)
            this.s.Push(n); //O(1)
            return true; //O(1)
        }

        //טענת יציאה: מחזירה את האיבר הקטן ביותר באוסף
        //סיבוכיות O(1)
        public int Small()
        {
            return this.tail; //O(1)
        }

        //טענת כניסה: מקבלת עוד אוסף מסוג קולכ
        //טענת יציאה: מחזירה את האיבר הקטן ביותר בשני האוספים
        //סיבוכיות O(1)
        public int Smallest(Collec c)
        {
            return Math.Min(c.Small(), this.tail); //O(1) כי מזומנות פעולות שהסיבוכיות שלהן היא גם O(1)
        }
    }
}