Рандомизированные пирамиды поиска

Задание на курсовую работу: Рандомизированные пирамиды поиска (Treaps)－ вставка. Демонстрация ...

....

Ключевая идея случайных БДП с рандомизацией состоит в чередовании обычной вставки в дерево поиска и вставки в корень. Чередование происходит случайным (рандомизированным) образом с использованием компьютерного генератора псевдослучайных чисел. Цель такого чередования – сохранить хорошие свойства случайного БДП в среднем и исключить (сделать маловероятным) появление «худшего случая» (поддеревьев большой высоты).
......

h#ifndef NODE_H#define NODE_Hclass node{public:int key;float prior;int size;node *left;node *right;node(int k,float p){key=k;prior=p;left=right=NULL;size=1;}};#endif // NODE_Hdrawbt.cpp#include "drawbt.h"#include <listpoint.h>#include <QPen>#include <QDebug>DrawBT::DrawBT(node *ROOT, int val,float prior_, QWidget *parent) : QWidget(parent){key=val;prior=prior_;Root=ROOT ;QPoint cord;Listpoint lt;int gap=0;int x,y;if(Root->left==NULL){x=size_strip;y=size_y;cord.setX(x);cord.setY(y);lt.curr.setX(x);lt.curr.setY(y);//prev по умолчанию заполнена нулямиlt.key=Root->key;lt.prior=Root->prior;list.push_back(lt);if(Root->right!=NULL){R_Arrive_Cord(Root->right,cord);}}if(Root->left!=NULL){gap = 2*(Root->left->size);//слева от новой вершины столбцов оставитьx Показать все =(gap+1)*size_strip;y=size_y;cord.setX(x);//запишем координату для передачи как предыдущуюcord.setY(y);//запишем координату для передачи как предыдущуюlt.curr.setX(x);//запись текущей координатыlt.curr.setY(y);lt.key=Root->key;lt.prior=Root->prior;list.push_back(lt);L_Arrive_Cord(Root->left,cord);}if(Root->right!=NULL && Root->left!=NULL){R_Arrive_Cord(Root->right,cord);}}void DrawBT::L_Arrive_Cord(node *root,QPoint pre_cord)// Идём по левой ветке, передаем точное значение предыдуще координаты{depth++;QPoint cord;Listpoint lt;int Lgap;int x,y;if(root->right!=NULL){Lgap = 2*(root->right->size+1);//справа от новой вершины столбцов оставить}else Lgap=2;x=pre_cord.x()- Lgap*size_strip;y=size_y*depth;cord.setX(x);//запишем координату для передачи как предыдущуюcord.setY(y);//запишем координату для передачи как предыдущуюlt.curr.setX(x);//запись текущей координатыlt.curr.setY(y);lt.key=root->key;lt.prior=root->prior;lt.prev.setX(pre_cord.x());//запись предыдущей координатыlt.prev.setY(pre_cord.y());list.push_back(lt);if(root->left!=NULL){L_Arrive_Cord(root->left,cord);}if(root->right!=NULL){R_Arrive_Cord(root->right,cord);}depth--;return;}void DrawBT::R_Arrive_Cord(node *root,QPoint pre_cord)// Идём по правой ветке, передаем точное значение предыдуще координаты{depth++;QPoint cord;Listpoint lt;int Rgap;int x,y;if(root->left!=NULL){Rgap = 2*(root->left->size+1);//слева от новой вершины столбцов оставить}else Rgap=2;x=pre_cord.x()+ Rgap*size_strip;y=size_y*depth;cord.setX(x);//запишем координату для передачи как предыдущуюcord.setY(y);//запишем координату для передачи как предыдущуюlt.curr.setX(x);//запись текущей координатыlt.curr.setY(y);lt.key=root->key;lt.prior=root->prior;lt.prev.setX(pre_cord.x());//запись предыдущей координатыlt.prev.setY(pre_cord.y());list.push_back(lt);if(root->left!=NULL){L_Arrive_Cord(root->left,cord);}if(root->right!=NULL){R_Arrive_Cord(root->right,cord);}depth--;return;}void DrawBT::paintEvent(QPaintEvent *event){Q_UNUSED(event);QPainter painter(this);QPoint st,fin;for(int i=0;i<list.size();i++){painter.setPen(QPen(Qt::black,1, Qt::SolidLine));int x1,y1,x2,y2;x1=list.at(i).prev.x();y1=list.at(i).prev.y();x2=list.at(i).curr.x();y2=list.at(i).curr.y();painter.drawEllipse(x2, y2, size_node, size_node);st.setX(x2+size_strip/4);st.setY(y2+size_strip/2);QFont font( "Arial Black",size_node/4 );painter.setFont(font);QString str;str.setNum(list.at(i).key);painter.drawText(st,str);str.setNum(list.at(i).prior);st.setX(x2+size_strip/4);st.setY(y2+(size_strip+32)/2);painter.setPen(Qt::red);painter.drawText(st,str);if(i){painter.setPen(QPen(Qt::black,2, Qt::SolidLine));st.setX(x1+size_strip/2);st.setY(y1+size_strip);fin.setX(x2+size_strip/2);fin.setY(y2);painter.drawLine(st,fin);}}}main.cpp#include "mainwindow.h"#include <QApplication>int main(int argc, char *argv[]){QApplication a(argc, argv);MainWindow w;w.show();return a.exec();}mainwindow.cpp#include "mainwindow.h"#include "ui_mainwindow.h"#include <QTime>MainWindow::MainWindow(QWidget *parent) :QMainWindow(parent),ui(new Ui::MainWindow){ui->setupUi(this);ui->scrollArea_->installEventFilter(this);QObject::connect(ui->buttonclose,SIGNAL(clicked()), this, SLOT(close()));QObject::connect(ui->research,SIGNAL(clicked()),this,SLOT(on_researchButton_clicked()));}MainWindow::~MainWindow(){delete ui;}node *MainWindow::insert (node *p, int k,float prior)// функция обычной вставки{if(p==NULL) return new node(k,prior);if (p->prior<prior)//rand() % (p->size+1)==0){return insertroot(p,k,prior);}else if(p->prior==prior){QMessageBox *message= new QMessageBox();message->setText("Дерево уже сожержит элемент с таким приоритетом!");message->show();}else {if(p->key>k && p->prior>prior){p->left=insert(p->left,k,prior);}else{p->right=insert(p->right,k,prior);}}return p;}int MainWindow::fixsize(node* n) { // Рекусивный пересчет весовif(!n)return 0;n->size = fixsize(n->left) + fixsize(n->right) + 1;return n->size;}node *MainWindow::rotation_right(node *p)// правый поворот{node *q=p->left;if(q==NULL) return p;p->left=q->right;q->right = p;++rightR;return q;}node *MainWindow::rotation_left(node *q)//левый поворот{node *p = q->right;if (p==NULL) return q;q->right = p->left;p->left= q;++leftR;return p;}node* MainWindow::insertroot(node *p, int k,float prior) // вставка в корень{if(p==NULL) return new node(k,prior);if (k < p->key && prior>p->prior){p->left=insertroot(p->left,k,prior);node *root = rotation_right(p);return root;}else{p->right= insertroot(p->right,k,prior);node *root = rotation_left(p);return root;}//}void MainWindow::on_addButton_clicked(){int SpinVal = ui->spinBox->value();int SpinnPrio = ui->spinBox2->value();ui->spinBox->clear();ui->spinBox2->clear();ui->textBrowser->clear();if(find(ROOT,SpinVal,SpinnPrio)==NULL){ROOT = insert(ROOT,SpinVal,SpinnPrio);fixsize(ROOT);QString str_l, str_r;str_l.setNum(leftR);str_r.setNum(rightR);ui->textBrowser->append("Левых поворотов: " + str_l);ui->textBrowser->append("Правых поворотов: " + str_r);leftR=0;rightR=0;DrawBT *widg_after2 = new DrawBT(ROOT,SpinVal,SpinnPrio);QVBoxLayout *layout= new QVBoxLayout();widg_after2->setLayout(layout);widg_after2->setMinimumHeight((ROOT->size*2+1)*size_strip);widg_after2->setMinimumWidth((ROOT->size*2+1)*size_strip);widg_after2->setSizePolicy(QSizePolicy::Minimum, QSizePolicy::Minimum);ui->scrollArea_->setWidget(widg_after2);ui->scrollArea_->setWidgetResizable(true);}else{QMessageBox *message= new QMessageBox();message->setText("Дерево уже сожержит добавляемый элемент!");message->show();}}node* MainWindow:: find(node* p, int key,float prior) // поиск ключа k в дереве p{if( !p ) return NULL; // в пустом дереве можно не искатьif( key == p->key )return p;if( key < p->key )return find(p->left,key,prior);elsereturn find(p->right,key,prior);}double MainWindow::rand(const int &acc){double priorRand = 0; priorRand = (qrand() % int (qPow(10,acc) + 1))/qPow(10, acc);return priorRand;}void MainWindow::on_researchButton_clicked(){int SpinVal = qrand()%1001;int SpinnPrio = 1*rand(2);count =0;ui->textBrowser_2->clear();if(find(ROOT,SpinVal,SpinnPrio)==NULL){count=ui->spinBox_2->text().toInt();QTime start=QTime::currentTime();start.