1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
use crate::avl_tree_node_with_key_value_size_box_recurse::Node;
#[derive(Debug)]
pub struct AVLTree<K, V> {
root: Option<Box<Node<K, V>>>,
}
impl<K: PartialOrd, V> AVLTree<K, V> {
pub fn new() -> Self {
Self { root: None }
}
pub fn size(&self) -> usize {
Node::get_size(self.root.as_ref())
}
pub fn insert(
&mut self,
key: K,
value: V,
) {
self.root = Some(Node::insert(self.root.take(), Node::new(key, value)));
}
pub fn remove(
&mut self,
key: &K,
) {
self.root = Node::remove(self.root.take(), &key);
}
pub fn get_kth_key(
&self,
k: usize,
) -> Option<&K> {
if let Some(node) = Node::get_kth_node(self.root.as_ref(), k) {
Some(&node.key)
} else {
None
}
}
pub fn lower_bound(
&self,
key: &K,
) -> usize {
Node::lower_bound(self.root.as_ref(), key)
}
pub fn upper_bound(
&self,
key: &K,
) -> usize {
Node::upper_bound(self.root.as_ref(), key)
}
pub fn contains(
&self,
key: &K,
) -> bool {
Node::find(self.root.as_ref(), key).is_some()
}
}
#[cfg(test)]
mod tests {
#[test]
fn test() {
let mut tree = super::AVLTree::<&str, isize>::new();
tree.insert("kagemeka", 1);
tree.insert("kagemeka", 2);
println!("{:?}", tree);
}
}
// impl<K, V> Iterator<Item = &'a Box<Self>> for Node<K, V> {
// fn next(&mut self) -> Option<Self::Item> {
// if self.left.is_some() {
// return self.left.take().unwrap().next();
// }
// if self.right.is_some() {
// return self.right.take().unwrap().next();
// }
// None
// }
// }
// def iterate(root: typing.Optional[Node[K, V]]) ->
// typing.Iterator[Node[K, V]]: def dfs(root:
// typing.Optional[Node[K, V]]) -> typing.Iterator[Node[K, V]]:
// if root is None:
// return
// for node in dfs(root.left):
// yield node
// yield root
// for node in dfs(root.right):
// yield node
// return dfs(root)