---

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

struct Node {
    string key;
    Node* left;
    Node* right;
    int height;
    Node(string k) : key(k), left(nullptr), right(nullptr), height(1) {}
};

int height(Node* n) { return n ? n->height : 0; }
int bfactor(Node* n) { return n ? height(n->left) - height(n->right) : 0; }
void fixHeight(Node* n) {
    if (n) n->height = 1 + max(height(n->left), height(n->right));
}

Node* rotateRight(Node* p) {
    Node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixHeight(p);
    fixHeight(q);
    return q;
}

Node* rotateLeft(Node* p) {
    Node* q = p->right;
    p->right = q->left;
    q->left = p;
    fixHeight(p);
    fixHeight(q);
    return q;
}

Node* balance(Node* p) {
    fixHeight(p);
    if (bfactor(p) == 2) {
        if (bfactor(p->left) < 0) p->left = rotateLeft(p->left);
        return rotateRight(p);
    }
    if (bfactor(p) == -2) {
        if (bfactor(p->right) > 0) p->right = rotateRight(p->right);
        return rotateLeft(p);
    }
    return p;
}

Node* insert(Node* p, string key) {
    if (!p) return new Node(key);
    if (key < p->key) p->left = insert(p->left, key);
    else if (key > p->key) p->right = insert(p->right, key);
    else return p;
    return balance(p);
}

void deleteTree(Node* p) {
    if (!p) return;
    deleteTree(p->left);
    deleteTree(p->right);
    delete p;
}

// Прямой обход (корень, левый, правый)
void preorder(Node* p) {
    if (!p) return;
    cout << p->key << " ";
    preorder(p->left);
    preorder(p->right);
}

// Обратный обход (левый, правый, корень)
void postorder(Node* p) {
    if (!p) return;
    postorder(p->left);
    postorder(p->right);
    cout << p->key << " ";
}

// Обход в порядке возрастания (симметричный)
void inorder(Node* p) {
    if (!p) return;
    inorder(p->left);
    cout << p->key << " ";
    inorder(p->right);
}

// Задание 11: подсчёт записей, начинающихся с определённой буквы
int countStartingWith(Node* p, char letter) {
    if (!p) return 0;
    int count = 0;
    if (!p->key.empty() && p->key[0] == letter) {
        count = 1;
    }
    return count + countStartingWith(p->left, letter) + countStartingWith(p->right, letter);
}

// Генерация случайной строки из 3-6 строчных букв
string randomString() {
    int len = rand() % 4 + 3; // 3-6 букв
    string result = "";
    for (int i = 0; i < len; i++) {
        result += 'a' + rand() % 26;
    }
    return result;
}

int main() {
    srand(time(0));
    Node* root = nullptr;

    // Создаём дерево из 15 случайных строк
    cout << "Создание дерева из случайных строк (3-6 букв, a-z):" << endl;
    for (int i = 0; i < 15; i++) {
        string val = randomString();
        root = insert(root, val);
    }

    cout << "\nПрямой обход: ";
    preorder(root);
    cout << endl;

    cout << "Обратный обход: ";
    postorder(root);
    cout << endl;

    cout << "Обход в порядке возрастания: ";
    inorder(root);
    cout << endl;

    char letter;
    cout << "\nВведите букву (a-z) для подсчёта записей, начинающихся с неё: ";
    cin >> letter;

    int result = countStartingWith(root, letter);
    cout << "Количество записей, начинающихся с буквы '" << letter << "': " << result << endl;

    deleteTree(root);
    return 0;
}