commit 9d429e8bcb81ce02fee8e911d1bf875858d573e7
parent 581be8e5f037443d2ffe5f21fed769a4399e55ae
Author: Plat <plat@stellar-nexus.ru>
Date: Wed, 5 Nov 2025 18:29:10 +0000
Added rb.c
Diffstat:
7 files changed, 216 insertions(+), 10 deletions(-)
diff --git a/latest_solution.cpp b/avl.cxx
diff --git a/libs/libtree/rb.h b/libs/libtree/rb.h
@@ -0,0 +1,8 @@
+#define BLACK 0
+#define RED 1
+
+#define FCOLOR(n) (((n)->val) & 1)
+#define COLOR(n) ((n) && FCOLOR(n))
+#define SET_COLOR(n,c) ((n)->val = (((n)->val) & ~1) | ((c) & 1))
+#define VALUE(n) ((n)->val >> 1)
+#define SET_VALUE(n,v) ((n)->val = ((v)<<1) | (((n)->val) & 1))
diff --git a/libs/libtree/tree.h b/libs/libtree/tree.h
@@ -0,0 +1,16 @@
+typedef struct Node {
+ int val;
+ struct Node *left, *right;
+} Node;
+
+Node* init(int);
+Node* add(int, Node*);
+Node* parse_pre(Node*);
+Node* parse_post(Node*);
+Node* parse_inf(Node*);
+int get_height(Node*);
+Node* balance(Node*);
+Node* balance2(Node*);
+Node* left_turn(Node*);
+Node* right_turn(Node*);
+Node* search(Node*, int);
diff --git a/libutil/ealloc.c b/libs/libutil/ealloc.c
diff --git a/libutil/eprintf.c b/libs/libutil/eprintf.c
diff --git a/libutil/tree.h b/libutil/tree.h
@@ -1,10 +0,0 @@
-typedef struct Node {
- int val;
- struct Node *left, *right;
-} Node;
-
-Node *init(int val);
-void add(int val, Node *root);
-Node *parse_pre(unsigned int *index, Node *root);
-Node *parse_post(unsigned int *index, Node *root);
-Node *parse_inf(unsigned int *index, Node *root);
diff --git a/rb.c b/rb.c
@@ -0,0 +1,192 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "libs/libutil/ealloc.h"
+#include "libs/libtree/tree.h"
+#include "libs/libtree/rb.h"
+
+unsigned int steps;
+
+static inline Node *
+init(int val)
+{
+ Node *root = emalloc(sizeof(Node));
+
+ SET_COLOR(root, RED);
+ SET_VALUE(root, val);
+ root->left = NULL;
+ root->right = NULL;
+
+ return root;
+}
+
+Node *
+add(Node *root, int val)
+{
+ if (!root)
+ return init(val);
+
+ if (val < VALUE(root))
+ root->left = add(root->left, val);
+ else if (val > VALUE(root))
+ root->right = add(root->right, val);
+
+ return balance(root);
+}
+
+
+Node *
+parse_pre(Node *root)
+{
+ int val = VALUE(root);
+
+ // do smth with val
+
+ if (root->left) parse_pre(root->left);
+ if (root->right) parse_pre(root->right);
+
+ return NULL;
+}
+
+
+Node *
+parse_post(Node *root)
+{
+ if (root->left) parse_post(root->left);
+ if (root->right) parse_post(root->right);
+
+ int val = VALUE(root);
+
+ // do smth with val
+
+ return NULL;
+}
+
+
+Node *
+parse_inf(Node *root)
+{
+ if (root->left) parse_inf(root->left);
+
+ int val = VALUE(root);
+
+ // do smth with val
+
+ if (root->right) parse_inf(root->right);
+
+ return NULL;
+}
+
+
+int
+get_height(Node *root)
+{
+ int r, l;
+
+ if (!root)
+ return 0;
+
+ l = get_height(root->left) + 1;
+ r = get_height(root->right) + 1;
+
+ if (l > r) {
+ return l;
+ }
+
+ return r;
+}
+
+inline int
+get_balance_factor(Node *root)
+{
+ if (!root)
+ return 0;
+
+ return get_height(root->left) - get_height(root->right);
+}
+
+
+Node *
+right_turn(Node *root)
+{
+ if (!root || !root->left)
+ return root;
+
+ Node *buf = root->left;
+ root->left = buf->right;
+ buf->right = root;
+ return buf;
+}
+
+
+Node *
+left_turn(Node *root)
+{
+ if (!root || !root->right)
+ return root;
+
+ Node *buf = root->right;
+ root->right = buf->left;
+ buf->left = root;
+ return buf;
+}
+
+Node *
+balance(Node *root)
+{
+ if (COLOR(root->right) && !COLOR(root->left))
+ root = left_turn(root);
+
+ if (COLOR(root->left) && COLOR(root->left->left))
+ root = right_turn(root);
+
+ if (COLOR(root->left) && COLOR(root->right)) {
+ SET_COLOR(root, !COLOR(root));
+ SET_COLOR(root->left, BLACK);
+ SET_COLOR(root->right, BLACK);
+ }
+
+ return root;
+}
+
+
+Node *
+search(Node *root, int val)
+{
+ ++steps;
+
+ if (VALUE(root) == val)
+ return root;
+
+ if (VALUE(root) > val)
+ return search(root->left, val);
+
+ return search(root->right, val);
+}
+
+int
+main(void)
+{
+ Node *root = NULL;
+
+ int data_limit;
+ printf("Element count: ");
+ scanf("%d", &data_limit);
+
+ for (int k = 1; k <= data_limit; ++k) {
+ root = add(root, k);
+ SET_COLOR(root, BLACK);
+ }
+
+ int search_value, attempt;
+ for (search_value = attempt = 0; search_value < 1 || search_value > data_limit; ++attempt) {
+ if (attempt)
+ printf("Impossible value\n");
+ printf("Value: ");
+ scanf("%d", &search_value);
+ }
+
+ Node *s = search(root, search_value);
+
+ printf("Found value: %d\nStep amount: %u\n", VALUE(s), steps);
+}
