Форум программистов, компьютерный форум CyberForum.ru

Сбалансированное дерево - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Разбор кода: fscanf и форматная строка http://www.cyberforum.ru/cpp-beginners/thread1191640.html
Добрый день! Необходимо разобраться в коде, в нем есть такие строки: h = fscanf(baza, "%*s %d", &kod1); h = fscanf(baza, "%*c %d %*c %d %*c %d", &t.tm_mday, &t.tm_mon, &t.tm_year); j = fscanf(baza, "%*s %d", &min); Что означает * перед "s" и "с"? Зачем там нужны указатели? Строки в считываемом файле (baza) имеют следующий формат:
C++ Подскажите пожалуйста в чем ошибка?(С++,структуры,стек) Подскажите пожалуйста, в чем ошибка При считывании из файла единственной записи 5группа "Anokhin Viktor petrovich 4 5 3 http://www.cyberforum.ru/cpp-beginners/thread1191630.html
Класс TGoods, создающий тип – товар C++
Задание вот: Объявите класс TGoods, создающий тип – товар. Элементы – данные класса – наименование товара, год производства. Предусмотрите конструкторы класса: по умолчанию; получающий параметры; получающий параметр –ссылку на класс TGoods Напишите функции – методы класса: для ввода – вывода данных о товаре; определения, относится ли год производства товара к какому – либо, значение...
C++ Структура "Студент"
Помогите пожалуйста разобраться в программе Тест. // test.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <math.h> #include <windows.h> #include <cstdio>
C++ Разделение классовой функции из заголовка в .h + .cpp http://www.cyberforum.ru/cpp-beginners/thread1191582.html
Пытаюсь разобрать заголовок на IAI.h + IAI.cpp столкнулся с функцией которую тупо не знаю как разбить правильно. Помогитепожа! :D friend ostream& operator<<(ostream& os, const sto& sto) { os << sto.num; return os; }если что, это функция для дружбы кастумного типа (sto) с std:cout
C++ Случайные блуждания с переменным шагом не могу разобраться в задании, объясните матмоделью или алгоритмом, может кто то программой поможет Случайные блуждания с переменным шагом. Рассмотрите одномерное случайное блуждание со всеми допустимыми длинами прыжков. Вероятность того, что длина шага равна j, имеет вид P(j)=exp(-j). Определите удаление от начального положения после 10 шагов. подробнее

Показать сообщение отдельно
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
28.05.2014, 19:59     Сбалансированное дерево
Поймите, по сути сбалансированное дерево - это любое двоичное дерево, где для каждой вершины выполняется условие, что модуль разности высот поддеревьев с вершинами в ее сыне не превышает 1. Соответственно, строить его можно различными способами со своими плюсами и минусами. Самое распространенное - это красно-черное дерево(однако я не вижу смысла его писать, так как он уже есть в c++ под названием set). Помимо него есть еще например АВЛ или 2-3-4 деревья. Но все они для новичка очень сложные. Самым простым является дерамида.

Чтобы понять,как это работает, давайте для начала я расскажу как работает простое двоичное дерево.
Двоичное дерево поиска - это дерево, у каждой вершины которого левый сын мееньше ее, а првый сын - больше.Отсюда понятно, как в нем искать требуемый элемент. Просто пройдем рекурсией, и посмотрим, что если вершина равна искомому элементу, то она и ответ, если больше искомого, то пойдем в левого сына, иначе - в правого. Соответственно, понятно как добавлять вершины. Хранят его обычно при помощи рекурсивных структур, примерно так :

C++
1
2
3
4
5
struct edge
{
    long val;
    struct edge *l,*r,*p;
}
Ну это краткий ликбез, о том что такое двоичное дерево поиска.

Теперь должно примерно стать понятна суть этих статей
http://habrahabr.ru/post/101818/
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru