add week 4

2 files changed, 93 insertions, 0 deletions

diff --git a/week4/AVLTree.cs b/week4/AVLTree.cs
new file mode 100644
index 0000000..fdc3a24
--- /dev/null
+++ b/week4/AVLTree.cs
@@ -0,0 +1,23 @@
+namespace ALGA {
+	public class AVLTree {
+		public Node root;
+
+		public void insert(int number) {
+			if (root == null) {
+				root = new Node(number);
+				return;
+			}
+			root = root.insert(number);
+		}
+
+		public bool isBalanced() {
+			if (root == null) return true;
+			return root.isBalanced();
+		}
+
+		public void prettyprint() {
+			return;
+		}
+	}
+}
+
diff --git a/week4/Node.cs b/week4/Node.cs
new file mode 100644
index 0000000..fc4acdd
--- /dev/null
+++ b/week4/Node.cs
@@ -0,0 +1,70 @@
+using System;
+
+namespace ALGA {
+	public class Node {
+		public int number;
+
+		public Node left, right;
+
+		public Node(int number) {
+			this.number = number;
+		}
+
+		public Node insert(int value) {
+			if (number == value) return this;
+
+			if (value > number) {
+				if (right != null)
+					right = right.insert(value);
+				else
+					right = new Node(value);
+			} else {
+				if (left != null)
+					left = left.insert(value);
+				else
+					left = new Node(value);
+			}
+
+			int balance = depth(left) - depth(right);
+
+			if (Math.Abs(balance) <= 1) return this;
+
+			if (balance > 0) {
+				if (value > left.number)
+					left = left.rotateLeft();
+				return rotateRight();
+			} else {
+				if (value < right.number)
+					right = right.rotateRight();
+				return rotateLeft();
+			}
+		}
+
+		public Node rotateLeft() {
+			if (right == null) return null;
+			Node pivot = right;
+			(right, right.left) = (right.left, this);
+			return pivot;
+		}
+
+		public Node rotateRight() {
+			if (left == null) return null;
+			Node pivot = left;
+			(left, left.right) = (left.right, this);
+			return pivot;
+		}
+
+		public bool isBalanced() {
+			if (Math.Abs(depth(left) - depth(right)) > 1) return false;
+			if (left != null && !left.isBalanced()) return false;
+			if (right != null && !right.isBalanced()) return false;
+			return true;
+		}
+
+		private int depth(Node here) {
+			if (here == null) return 0;
+			return 1 + Math.Max(depth(here.left), depth(here.right));
+		}
+	}
+}
+