Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Start of an AVL implementation in Rust
use std::fmt;
struct Node<T: Ord + fmt::Show> {
pub data: T,
pub left: Option<Box<Node<T>>>,
pub right: Option<Box<Node<T>>>,
}
impl<T: Ord + fmt::Show> Node<T> {
fn new(d: T) -> Node<T> {
Node { data: d, left: None, right: None}
}
fn insert(&mut self, d: T) {
match d > self.data {
true => self.insert_right(d),
false => self.insert_left(d),
}
}
fn insert_right(&mut self, d: T) {
match self.right {
None => self.right = Some(box Node::new(d)),
Some(ref mut x) => x.insert(d)
}
}
fn insert_left(&mut self, d: T) {
match self.left {
None => self.left = Some(box Node::new(d)),
Some(ref mut x) => x.insert(d)
}
}
fn print_node(self, depth: int) {
let connector = match (self.right.is_some(), self.left.is_some()) {
(true, true) => "├",
(true, false) => "┘",
(false, false) => "",
(false, true) => "┐"
};
if self.right.is_some() {
self.right.unwrap().print_node(depth + 1)
};
for _ in range(0, depth) { print!(" ") }
println!{"{}{}", self.data, connector};
if self.left.is_some() {
self.left.unwrap().print_node(depth + 1)
};
}
fn depth(self) -> u64 {
return 1 + match (self.right, self.left) {
(Some(x),Some(y)) => x.depth() + y.depth(),
(_,Some(y)) => y.depth(),
(Some(x),_) => x.depth(),
(_,_) => 0,
};
}
}
impl<T: Ord + fmt::Show> PartialEq for Node<T> {
fn eq(&self, other: &Node<T>) -> bool {
self.data.eq(&other.data)
}
}
impl<T: Ord + fmt::Show> Eq for Node<T> { }
impl<T: Ord + fmt::Show> PartialOrd for Node<T> {
fn partial_cmp(&self, other: &Node<T>) -> Option<Ordering> {
self.data.partial_cmp(&other.data)
}
}
impl<T: Ord + fmt::Show> Ord for Node<T> {
fn cmp(&self, other: &Node<T>) -> Ordering {
self.data.cmp(&other.data)
}
}
struct Tree<T: Ord + fmt::Show> {
pub root: Option<Box<Node<T>>>,
}
impl<T: Ord + fmt::Show> Tree<T> {
fn new() -> Box<Tree<T>> {
box Tree { root: None }
}
fn insert(&mut self, d: T) {
match self.root {
None => {
self.root = Some(box Node::new(d));
},
Some(ref mut x) => {
x.insert(d);
}
}
}
fn print_tree(self) {
if self.root.is_some() {self.root.unwrap().print_node(0)}
}
fn rebalance() {
}
}
fn main() {
let mut t = Tree::<i32>::new();
for i in range(0i32, 25) {
t.insert(i);
}
t.print_tree();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.