diff options
| author | Mart Lubbers | 2015-04-16 21:22:20 +0200 |
|---|---|---|
| committer | Mart Lubbers | 2015-04-16 21:22:20 +0200 |
| commit | 6f604b19d3f5966e5c1d7c4fdf3703bd6ff0861c (patch) | |
| tree | 96d580507249f7f58368476d9113007d4afcd748 /fp1/week7/mart/BinSearchTree.icl | |
| parent | Added student numbers (diff) | |
update to fp2 yay, public and licence
Diffstat (limited to 'fp1/week7/mart/BinSearchTree.icl')
| -rw-r--r-- | fp1/week7/mart/BinSearchTree.icl | 141 |
1 files changed, 141 insertions, 0 deletions
diff --git a/fp1/week7/mart/BinSearchTree.icl b/fp1/week7/mart/BinSearchTree.icl new file mode 100644 index 0000000..8f9f05c --- /dev/null +++ b/fp1/week7/mart/BinSearchTree.icl @@ -0,0 +1,141 @@ +implementation module BinSearchTree
+
+import StdEnv
+import BinTree
+
+
+z0
+ Leaf
+z1
+ 50
+ |
+ ----------
+ | |
+ Leaf Leaf
+z2
+ 50
+ |
+ ----------
+ | |
+ 10 Leaf
+ |
+ ------
+ | |
+ Leaf Leaf
+z3
+ 50
+ |
+ ----------
+ | |
+ 10 75
+ | |
+ ------ ------
+ | | | |
+ Leaf Leaf Leaf Leaf
+z4
+ 50
+ |
+ ----------
+ | |
+ 10 75
+ | |
+ ------ ------
+ | | | |
+ Leaf Leaf Leaf 80
+ |
+ ------
+ | |
+ Leaf Leaf
+z5
+ 50
+ |
+ ----------
+ | |
+ 10 75
+ | |
+ ------ ------
+ | | | |
+ Leaf Leaf Leaf 77
+ |
+ ------
+ | |
+ Leaf 80
+ |
+ ------
+ | |
+ Leaf Leaf
+z6
+ 50
+ |
+ ----------
+ | |
+ 10 75
+ | |
+ ------ ------
+ | | | |
+ 10 Leaf Leaf 77
+ | |
+ ------ ------
+ | | | |
+Leaf Leaf Leaf 80
+ |
+ ------
+ | |
+ Leaf Leaf
+z7
+ 50
+ |
+ ----------
+ | |
+ 10 75
+ | |
+ ------ -----------
+ | | | |
+ 10 Leaf 75 77
+ | | |
+ ------ ------ ------
+ | | | | | |
+Leaf Leaf Leaf Leaf Leaf 80
+ |
+ ------
+ | |
+ Leaf Leaf
+z8
+
+// Uit het diktaat, blz. 73:
+insertTree :: a (Tree a) -> Tree a | Ord a
+insertTree e Leaf = Node e Leaf Leaf
+insertTree e (Node x le ri)
+| e <= x = Node x (insertTree e le) ri
+| e > x = Node x le (insertTree e ri)
+
+deleteTree :: a (Tree a) -> (Tree a) | Eq, Ord a
+deleteTree e Leaf = Leaf
+deleteTree e (Node x le ri)
+| e < x = Node x (deleteTree e le) ri
+| e == x = join le ri
+| e > x = Node x le (deleteTree e ri)
+where
+ join :: (Tree a) (Tree a) -> (Tree a)
+ join Leaf b2 = b2
+ join b1 b2 = Node x b1` b2
+ where
+ (x,b1`) = largest b1
+
+ largest :: (Tree a) -> (a,(Tree a))
+ largest (Node x b1 Leaf) = (x,b1)
+ largest (Node x b1 b2) = (y,Node x b1 b2`)
+ where
+ (y,b2`) = largest b2
+
+
+is_geordend :: // meest algemene type
+is_geordend ...
+
+Start = map is_geordend [t0,t1,t2,t3,t4,t5,t6,t7]
+
+
+is_gebalanceerd :: // meest algemene type
+is_gebalanceerd ...
+
+//Start = map is_gebalanceerd [t0,t1,t2,t3,t4,t5,t6,t7]
|