1 #pragma once
2 #include <common/glib.h>
3 
4 struct bt_node_t
5 {
6     struct bt_node_t *left;
7     struct bt_node_t *right;
8     struct bt_node_t *parent;
9     void *value; // 数据
10 
11 } __attribute__((aligned(sizeof(long))));
12 
13 struct bt_root_t
14 {
15     struct bt_node_t *bt_node;
16     int32_t size;                 // 树中的元素个数
17     int (*cmp)(void *a, void *b); // 比较函数   a>b 返回1， a==b返回0, a<b返回-1
18     /**
19      * @brief 释放结点的value的函数
20      * @param value 结点的值
21      */
22     int (*release)(void *value);
23 };
24 
25 /**
26  * @brief 创建二叉搜索树
27  *
28  * @param node 根节点
29  * @param cmp 比较函数
30  * @param release 用来释放结点的value的函数
31  * @return struct bt_root_t* 树根结构体
32  */
33 struct bt_root_t *bt_create_tree(struct bt_node_t *node, int (*cmp)(void *a, void *b), int (*release)(void *value));
34 
35 /**
36  * @brief 创建结点
37  *
38  * @param left 左子节点
39  * @param right 右子节点
40  * @param value 当前节点的值
41  * @return struct bt_node_t*
42  */
43 struct bt_node_t *bt_create_node(struct bt_node_t *left, struct bt_node_t *right, struct bt_node_t *parent, void *value);
44 
45 /**
46  * @brief 插入结点
47  *
48  * @param root 树根结点
49  * @param value 待插入结点的值
50  * @return int 返回码
51  */
52 int bt_insert(struct bt_root_t *root, void *value);
53 
54 /**
55  * @brief 搜索值为value的结点
56  *
57  * @param root 树根结点
58  * @param value 值
59  * @param ret_addr 返回的结点基地址
60  * @return int 错误码
61  */
62 int bt_query(struct bt_root_t *root, void *value, uint64_t *ret_addr);
63 
64 /**
65  * @brief 删除结点
66  *
67  * @param root 树根
68  * @param value 待删除结点的值
69  * @return int 返回码
70  */
71 int bt_delete(struct bt_root_t *root, void *value);
72 
73 /**
74  * @brief 释放整个二叉搜索树
75  *
76  * @param root
77  * @return int
78  */
79 int bt_destroy_tree(struct bt_root_t *root);