这个crate命名为ABtree，但这并不意味着它是一个新颖的数据结构。它只是AVL树和B树。对于B树，它与众不同的地方在于这个B树可以接受任何作为内部节点最大数量的数字，只要这个数字大于或等于3。

1.AVL

1.1 创建一个空的 AVL 树

use ABtree::AVL;

let t = AVL::<i32, i32>::new();

1.2 插入键值对

use ABtree::AVL;
let mut t = AVL::<i32, i32>::new();
t.insert(2, 3);
assert_eq!(t.len(), 1);

1.3 更新值

如果键不存在，它将把键值对添加到树中

use ABtree::AVL;
let mut t = AVL::<i32, i32>::new();
t.set(2, 2);
t.set(2, 31);
assert_eq!(t.get(&2), Some(&31));

1.4 获取长度

use ABtree::AVL;
let mut t = AVL::<i32, i32>::new();
t.insert(2, 2);
t.insert(3, 3);
assert_eq!(t.len(), 2);

1.5 为 AVL 创建迭代器

注意 next() 和 next_back() 是两个独立的操作，这意味着一个节点可以通过两种方法进行遍历

use ABtree::AVL;

let t = AVL::<i32, i32>::new();

1.6 包含

use ABtree::AVL;

let mut t: AVL<u32, u32> = AVL::new();

t.insert(0, 0);
t.insert(1, 1);
t.insert(2, 2);
assert!(t.contains(&1));

1.7 删除

use ABtree::AVL;

let mut t: AVL<u32, u32> = AVL::new();

t.insert(0, 0);
t.insert(1, 1);
t.insert(2, 2);
assert_eq!(t.remove(&1), Some(1));
assert_eq!(t.len(), 2);

1.8 查看根节点

use ABtree::AVL;

let mut t: AVL<u32, u32> = AVL::new();

t.insert(0, 0);
t.insert(1, 1);
t.insert(2, 2);
assert_eq!(t.peek_root(), Some((&1, &1)));

1.9 是否为空？

use ABtree::AVL;

let mut t: AVL<u32, u32> = AVL::new();

t.insert(0, 0);
t.insert(1, 1);
t.insert(2, 2);
assert_eq!(t.is_empty(), false);

1.10 清除 AVL 树实例

use ABtree::AVL;

let mut t: AVL<u32, u32> = AVL::new();

t.insert(0, 0);
t.insert(1, 1);
t.insert(2, 2);
t.clear();
assert_eq!(t.len(), 0);

1.11 获取方法

use ABtree::AVL;

let mut t: AVL<u32, u32> = AVL::new();

t.insert(0, 0);
t.insert(1, 1);
t.insert(2, 2);
assert_eq!(t.get(&1), Some(&1));

1.12 from_iter

use std::iter::FromIterator;
use ABtree::AVL;

let data = vec![
    (12, 1),
    (8, 1),
    (17, 1),
];
let a = AVL::from_iter(data);

1.13 into_iter

use std::iter::FromIterator;
use ABtree::AVL;

let data = vec![
    (12, 1),
    (8, 1),
    (17, 1),
];
let a = AVL::from_iter(data);
let iter = a.into_iter();

2.Btree

2.1 创建一个空的 b-tree

选择任何数字作为内部节点的最大数量，只要这个数字大于或等于3

use ABtree::BTree;
let mut b: BTree<i32, i32> = BTree::new(4);
b.insert(1, 1);

2.2 插入

use ABtree::BTree;
let mut b: BTree<i32, i32> = BTree::new(4);
b.insert(1, 1);

2.3 获取

use ABtree::BTree;
let mut b: BTree<i32, i32> = BTree::new(4);
let data = [(1, 1), (2, 2), (3, 3)];
for (k, v) in data {
    b.insert(k, v)
}
assert_eq!(b.get(&2), Some(&2));

2.4 设置

use ABtree::BTree;
let mut b: BTree<i32, i32> = BTree::new(3);
let data = [(1, 1), (2, 2), (3, 3)];
for (k, v) in data {
    b.insert(k, v)
}
b.set(2, 200);

2.5 包含

use ABtree::BTree;
let mut b: BTree<i32, i32> = BTree::new(4);
let data = [(1, 1), (2, 2), (3, 3)];
for (k, v) in data {
    b.insert(k, v)
}
assert!(b.contains(&2));

2.6 删除

use ABtree::BTree;
let mut b: BTree<i32, i32> = BTree::new(4);
let data = [(1, 1), (2, 2), (3, 3)];
for (k, v) in data {
    b.insert(k, v)
}
assert_eq!(b.remove(&2), Some(2));

2.7 迭代

use ABtree::BTree;
let mut b: BTree<i32, i32> = BTree::new(4);
let data = [(1, 1), (2, 2), (3, 3)];
for (k, v) in data {
    b.insert(k, v)
}
assert_eq!(b.remove(&2), Some(2));

2.8 获取长度

use ABtree::BTree;
let mut b: BTree<i32, i32> = BTree::new(4);
let data = [(1, 1), (2, 2), (3, 3)];
for (k, v) in data {
    b.insert(k, v)
}
assert_eq!(b.len(), 3);

2.9 是否为空？

use ABtree::BTree;
let mut b: BTree<i32, i32> = BTree::new(4);
let data = [(1, 1), (2, 2), (3, 3)];
for (k, v) in data {
    b.insert(k, v)
}
assert!(!b.is_empty());

2.10 清除

use ABtree::BTree;
let mut b: BTree<i32, i32> = BTree::new(4);
let data = [(1, 1), (2, 2), (3, 3)];
for (k, v) in data {
    b.insert(k, v)
}
b.clear();
assert_eq!(b.len(), 0);

2.11 from_iter

如果使用 from_iter() 创建 b-tree，则内部节点大小的最大数量为 3，这使得它成为一个 2-3 树

use std::iter::FromIterator;
use ABtree::BTree;
let data1 = vec![
    (12, 1),
    (8, 1),
    (17, 1),
];
let b = BTree::from_iter(data1);
b.iter().for_each(|n| println!("{}", n.0));

2.12 into_iter

use std::iter::FromIterator;
use ABtree::BTree;
let data1 = vec![
    (12, 1),
    (8, 1),
    (17, 1),
];
let b = BTree::from_iter(data1);
b.into_iter().for_each(|n| println!("{}", n.0));