Lines Matching refs:tree
37 * Simple implementation of a left-leaning red-black tree with 64-bit
49 struct rbtree *rb_search(struct rbtree *tree, uint64_t key)
53 while (tree) {
54 if (tree->key == key)
55 return tree;
56 else if (tree->key > key)
57 tree = tree->left;
59 best = tree;
60 tree = tree->right;
98 struct rbtree *rb_insert(struct rbtree *tree, struct rbtree *node)
103 if (!tree) {
108 if (is_red(tree->left) && is_red(tree->right))
109 color_flip(tree);
111 if (node->key < tree->key)
112 tree->left = rb_insert(tree->left, node);
114 tree->right = rb_insert(tree->right, node);
116 if (is_red(tree->right))
117 tree = rotate_left(tree);
119 if (is_red(tree->left) && is_red(tree->left->left))
120 tree = rotate_right(tree);
122 return tree;
125 void rb_destroy(struct rbtree *tree)
127 if (tree->left)
128 rb_destroy(tree->left);
129 if (tree->right)
130 rb_destroy(tree->right);
131 free(tree);
