문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. <source lang="rust"> #[derive(Debug)] enum Node<T: Sized> { Terminal { key: u32, data: T, }, Nonterminal { left: Box<Node<T>>, right: Box<Node<T>>, }, None, } #[derive(Debug)] struct Tree<T: Sized> { root: Node<T>, } #[inline] fn radix_bit(num: u32, radix: u8) -> bool { num & (1 << (32 - radix)) != 0 } impl<T: Sized> Node<T> { fn terminal(key: u32, data: T) -> Self { Node::Terminal { key: key, data: data, } } fn nonterminal(left: Self, right: Self) -> Self { Node::Nonterminal { left: Box::new(left), right: Box::new(right), } } fn none() -> Self { Node::None } fn insert(&mut self, index: u8, key: u32, data: T)->Option<T> { //println!("insert {}",index); match *self { Node::None => { let n = if radix_bit(key, index) { Node::nonterminal(Node::none(), Node::terminal(key, data)) } else { Node::nonterminal(Node::terminal(key, data), Node::none()) }; *self = n; None } Node::Nonterminal { ref mut left, ref mut right, } => { let next = if radix_bit(key, index) { right.as_mut() } else { left.as_mut() }; next.insert(index + 1, key, data) //next } Node::Terminal { key: self_key, data:ref mut self_data, } => { if self_key == key{ return Some(std::mem::replace(self_data, data)); } let s = std::mem::replace(self, Node::None); let res; //eprintln!("{:?}", self); *self = match (radix_bit(self_key, index), radix_bit(key, index)) { (true, true) => { let mut node = Node::nonterminal(Node::None, s); res = node.insert(index, key, data); node } (false, false) => { let mut node = Node::nonterminal(s, Node::None); res = node.insert(index, key, data); node } (true, false) => { //eprintln!("{:?}", self); res = None; Node::nonterminal( Node::terminal(key, data), s, ) } (false, true) => { //eprintln!("{:?}", self); res = None; Node::nonterminal( s, Node::terminal(key, data), ) } }; res } } } } impl<T: Sized> Tree<T> { fn new() -> Self { Self { root: Node::none() } } fn insert(&mut self, key: u32, data: T) { self.root.insert(1, key, data); } fn find(&self, key: &u32) -> Option<&T> { let mut node = &self.root; let mut radix = 0u8; loop { //eprintln!("{}, {:?}",radix, node); radix += 1; //println!("find radix: {} {:?}",radix, node); match node { Node::Terminal { key: termial_key, data, } if termial_key == key => break Some(data), Node::Nonterminal { left, right } => { node = match radix_bit(*key, radix) { true => right.as_ref(), false => left.as_ref(), } } _ => break None, } } } } fn main(){ //let mut tree = Tree::new(); let mut tree:Tree<[u8; 4096]> = Tree::new(); } </source> 기수 탐색 트라이 문서로 돌아갑니다.