summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--.gitignore1
-rw-r--r--Cargo.lock7
-rw-r--r--Cargo.toml8
-rw-r--r--src/main.rs61
-rw-r--r--src/main_gen.rs45
5 files changed, 122 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..ea8c4bf
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+/target
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..94ca2df
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "avl-verification"
+version = "0.1.0"
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..6321c4f
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "avl-verification"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/src/main.rs b/src/main.rs
new file mode 100644
index 0000000..d5bb8f9
--- /dev/null
+++ b/src/main.rs
@@ -0,0 +1,61 @@
+use std::cmp::Ordering;
+
+trait Ord {
+ fn cmp(&self, other: &Self) -> Ordering;
+}
+
+struct AVLNode<T: Ord> {
+ value: T,
+ left: AVLTree<T>,
+ right: AVLTree<T>,
+}
+
+type AVLTree<T> = Option<Box<AVLNode<T>>>;
+
+struct AVLTreeSet<T: Ord> {
+ root: AVLTree<T>,
+}
+
+impl<T: Ord> AVLTreeSet<T> {
+ pub fn new() -> Self {
+ Self { root: None }
+ }
+
+ pub fn insert(&mut self, value: T) -> bool {
+ let mut current_tree = &mut self.root;
+
+ while let Some(current_node) = current_tree {
+ match current_node.value.cmp(&value) {
+ Ordering::Less => current_tree = &mut current_node.right,
+ Ordering::Equal => return false,
+ Ordering::Greater => current_tree = &mut current_node.left,
+ }
+ }
+
+ *current_tree = Some(Box::new(AVLNode {
+ value,
+ left: None,
+ right: None,
+ }));
+
+ true
+ }
+}
+
+impl Ord for u32 {
+ fn cmp(&self, other: &Self) -> Ordering {
+ if *self < *other {
+ Ordering::Less
+ } else if *self == *other {
+ Ordering::Equal
+ } else {
+ Ordering::Greater
+ }
+ }
+}
+
+fn main() {
+ let mut tree = AVLTreeSet::new();
+ tree.insert(3);
+ tree.insert(2);
+}
diff --git a/src/main_gen.rs b/src/main_gen.rs
new file mode 100644
index 0000000..b3f6add
--- /dev/null
+++ b/src/main_gen.rs
@@ -0,0 +1,45 @@
+use std::cmp::Ordering;
+
+struct AVLNode<T: Ord> {
+ value: T,
+ left: AVLTree<T>,
+ right: AVLTree<T>,
+}
+
+type AVLTree<T> = Option<Box<AVLNode<T>>>;
+
+struct AVLTreeSet<T: Ord> {
+ root: AVLTree<T>,
+}
+
+impl<T: Ord> AVLTreeSet<T> {
+ pub fn new() -> Self {
+ Self { root: None }
+ }
+
+ pub fn insert(&mut self, value: T) -> bool {
+ let mut current_tree = &mut self.root;
+
+ while let Some(current_node) = current_tree {
+ match current_node.value.cmp(&value) {
+ Ordering::Less => current_tree = &mut current_node.right,
+ Ordering::Equal => return false,
+ Ordering::Greater => current_tree = &mut current_node.left,
+ }
+ }
+
+ *current_tree = Some(Box::new(AVLNode {
+ value,
+ left: None,
+ right: None,
+ }));
+
+ true
+ }
+}
+
+fn main() {
+ let mut tree = AVLTreeSet::new();
+ tree.insert(3);
+ tree.insert(2);
+}