树

我们的树几乎所有的方法都使用递归策略。递归策略大大提高了代码的可读性和简单性，但代价是可能会在递归太多的情况下出现栈溢出。因此，我们的树的生长深度将存在理论上的限制（取决于您的计算机栈的大小）。请注意，插入/删除操作不使用递归策略，但获取高度或打印树这样的支持方法则使用它。通过调用构造函数初始化树，这将最初提供一个空树。从这里，用户可以通过使用 insert() 方法将数字插入到树中。重新着色和重构将自动处理。其他用户可以运行的方法包括 insert()、delete_node()、get_num_leaves()、get_height()、print_nodes_in_order()、is_empty() 和 print_tree()。下面将展示每个方法及其功能的详细描述。

红黑树

insert() 方法将接受一个 u32 数字作为输入，然后将其值插入到树中。这意味着它将首先将值插入到树中，就像它是一个二叉树一样，然后在适当的时候进行旋转和重新着色。所有旋转和重新着色的用例都可以在这里找到：[红黑树](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree)。

delete() 方法将接受一个 u32 数字作为输入，然后从树中删除节点。接着将进行旋转和重新着色。如上所述，所有旋转和重新着色的用例都可以在这里找到：[红黑树](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree)。

get_num_leaves() 方法将返回树中叶子节点的数量。叶子节点定义为没有左右子节点的节点。因此，只有一个根节点的树也将被认为有一个叶子节点。

get_height() 方法将返回树的最大高度。最大高度定义为从根节点到其一个叶子节点所需遍历的节点最大数量。

print_nodes_in_order() 方法将按升序打印出每个节点的键。

is_empty() 方法将返回 True，如果树没有根节点，否则返回 False。

print_tree() 方法将以 <根/左子树/右子树> 的格式完全打印出树，并打印出 null 节点，以清楚地显示终止点。

AVL树

insert() 方法将接受一个数字作为输入，然后将该值插入到树中。这意味着它将首先将值插入到看似二叉树中，然后根据需要进行旋转。所有旋转和重新着色的情况都可以在这里找到：https://www.geeksforgeeks.org/avl-tree-set-1-insertion/。

delete_node() 方法将接受一个数字作为输入，然后从树中删除该节点。接下来将进行旋转。如上所述，所有旋转和重新着色的情况都可以在这里找到：https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

get_num_leaves() 方法将返回树中叶子节点的数量。叶子节点定义为没有左右子节点的节点。因此，只有一个根节点的树也将被认为有一个叶子节点。

get_height() 方法将返回树的最大高度。最大高度定义为从根节点到其一个叶子节点所需遍历的节点最大数量。

print_nodes_in_order() 方法将按升序打印出每个节点。

is_empty() 方法将返回 True，如果树没有根节点，否则返回 False。

print_tree() 方法将以 <根/左子树/右子树> 的格式完全打印出树，并打印出 null 节点，以清楚地显示终止点。