Answer the corresponding questions written by the LORD before, click View here . I personally feel that the previous value is relatively high, and the search for names is much more important than the search for numbers. However, the balanced binary tree is mainly used here, which is a supplement to the previous one. It should be noted here. I think it is difficult to construct a balanced binary tree. It needs to be saved by multiple storage nodes. I need to be familiar with the pointer node and be able to understand it more deeply. However, I will explain the code of the four rotations here. I hope it will be helpful. Binary sort tree is too simple. Here we will directly talk about balanced binary tree.
Your third company is the biggest driving force of my creation!
Title Description:
1. Create a binary sort tree to realize the binary sort tree search algorithm.
2. Establish an ordered table to realize the half search algorithm.
3. Establish a hash table to realize the hash lookup algorithm.
balanced binary tree
First, give a brief description of the four rotations.
Methods: first, find the imbalance point. Starting from the imbalance point, after two steps of "searching", you will inevitably encounter two nodes. Plus the imbalance point, there are three nodes in total. Assume A, B and C, and specify A < B < C. Take out these three nodes separately. Taking the "median" B as the root node, A as the left subtree of B and C as the right subtree of B, A new balanced binary tree is constructed. And put the root B of the new tree on the original imbalance point. Among them, the subtrees of A and C do not move. This is the general method of four rotations.
In the code, the tree - > BF positive number is the left height, and the negative number is the right height. For example, a.bf = 2, b.bf = 1 is LL rotation.
For LL rotation, the core statement:
B=A->lchild; A->lchild=B->rchild; //What are these two steps doing? Simply put, point B to the left child of A, and then let the left child of A point to the right child of B B->rchild=A; A->bf=0;B->bf=0;
Other methods are similar, so I won't be wordy here. I'll put the complete code directly.
Balanced binary tree code:
#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct AVLTNode{
int key;
int bf;//Balance factor, positive L, negative R
int num;//Enter serial number
struct AVLTNode *lchild;
struct AVLTNode *rchild;
}AVLTNode,*AVLTree;
void InsertAVLTree(AVLTree &avlt,int k,int i){
AVLTree S;
AVLTree A,FA,p,fp,B,C;
//Insert k into the new node s first, assign k to s, and make the left and right subtrees of s NULL
S=new AVLTNode();
S->key=k;
S->num=i+1;
S->lchild=NULL;
S->rchild=NULL;
S->bf=0;
//If avlt is NULL, s is inserted directly
if(avlt==NULL){
avlt=S;
}
else{
/* First, find the insertion position fp of S, and record the position closest to the insertion position of S
For node A whose balance factor is not equal to 0 (equal to - 1 or 1), A is the possible imbalance node*/
A=avlt;
FA=NULL;
p=avlt;//p is now avlt,
fp=NULL;
while(p){
if(p->bf!=0){
A=p;//Record node A may be out of balance
FA=fp;
}
//When the factor of P is 0, (a factor of 0 does not mean a leaf, which means left-right balance), assign p to fp
fp=p;
//When k is less than the key of p, the left tree of p is traversed
if(k<p->key) p=p->lchild;
else p=p->rchild;
}
//Note that fp is the node inserted at this time
if(k<fp->key) fp->lchild=S;
else fp->rchild=S;
//A as the unbalance node
//Note that if a node is inserted at this time, the number of corresponding factors also needs to be increased, which is a key step
if(k<A->key){
B=A->lchild;
A->bf++;
}
//Note that in the definition at this time, it is specified that bf positive numbers are left high and negative numbers are right high. The following is a better judgment
else {
B=A->rchild;
A->bf--;
}
//At this time, B is the insertion node of A, and point the p node to B
p=B;
//Start to modify the node and rotate. Now you have found the unbalance node closest to the insertion point. Start four kinds of rotations
while(p!=S){
if(k<p->key){
p->bf=1;
p=p->lchild;
}
else{
p->bf=-1;
p=p->rchild;
}
//Determine the type of rotation
//LL type
//Here will be LL, the rest are the same
if(A->bf==2&&B->bf==1){
//Make node B point to the left child of A
B=A->lchild;
//Make the left child of A point to the right child of B
//Why do you do this? To put it bluntly, let A become the right child of B (all the previous efforts are storing the node information of A)
A->lchild=B->rchild;
B->rchild=A;
A->bf=0;
B->bf=0;
if(FA==NULL){
avlt=B;
}
else{
if(A==FA->lchild) FA->lchild=B;
else FA->rchild=B;
}
}
//LR type
else if(A->bf==2&&B->bf==-1){
B=A->lchild;
C=B->rchild;
B->rchild=C->lchild;
A->lchild=C->rchild;
C->lchild=B;
C->rchild=A;
if (S->key < C->key)
{
A->bf=-1;
B->bf=0;
C->bf=0;
}
else
if (S->key >C->key)
{
A->bf=0;
B->bf=1;
C->bf=0;
}
else
{
A->bf=0;
B->bf=0;
}
if (FA==NULL)
avlt=C;
else
if (A==FA->lchild)
FA->lchild=C;
else
FA->rchild=C;
}
//RL type
else if(A->bf==-1&&B->bf==1){
B=A->rchild;
C=B->lchild;
B->lchild=C->rchild;
A->rchild=C->lchild;
C->lchild=A;
C->rchild=B;
if (S->key <C->key) {
A->bf=0;
B->bf=-1;
C->bf=0;
}
else if (S->key >C->key){
A->bf=1;
B->bf=0;
C->bf=0;
}
else {
A->bf=0;
B->bf=0;
}
if (FA==NULL)
avlt=C;
else if (A==FA->lchild)
FA->lchild=C;
else
FA->rchild=C;
}
//RR type
else if (A->bf==-2 && B->bf==-1){
B=A->rchild;
A->rchild=B->lchild;
B->lchild=A;
A->bf=0;
B->bf=0;
if (FA==NULL) avlt=B;
else if (A==FA->lchild)
FA->lchild=B;
else
FA->rchild=B;
}
}
}
}
void CreateAVLT(AVLTree &bst,int a[],int N){
bst=NULL;
for(int i=0;i<N;i++){
InsertAVLTree(bst,a[i],i);
}
}
AVLTree Search(AVLTree bst,int k){
if(!bst) return NULL;
else if(bst->key==k) return bst;
else if(bst->key>k) return Search(bst->lchild,k);
else return Search(bst->rchild,k);
}
int main(){
AVLTree T,temp;
int N;
cout<<"Please enter the number of keywords:"<<endl;
cin>>N;
int a[N];
cout<<"Please enter keyword sequence:"<<endl;
for(int i=0;i<N;i++){
cin>>a[i];
}
CreateAVLT(T,a,N);
cout<<"Please enter the keyword you want to find:"<<endl;
int k;
cin>>k;
temp=Search(T,k);
cout<<"The position of the keyword is the first in the original sequence"<<temp->num<<"position"<<endl;
return 0;
}
Operation results:
Half search
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct{
int key;
}Stud;
typedef struct{
Stud a[100];//a[0] is the work unit
int length;
}RecordList;
bool cmp(Stud a,Stud b){
return a.key<b.key;
}
int BinSearch(RecordList l,int k){
int low=1,high=l.length;
int mid;
while(low<=high){
mid=(low+high)/2;
if(l.a[mid].key==k) return mid;
else if(l.a[mid].key>k) high=mid-1;
else low=mid+1;
}
return 0;
}
int main(){
RecordList l;
l.length=0;
int N;
cout<<"Please enter the number of keywords:"<<endl;
cin>>N;
cout<<"Please enter a sequence of keywords:"<<endl;
for(int i=1;i<=N;i++){
cin>>l.a[i].key;
l.length++;
}
sort(l.a+1,l.a+N+1,cmp);
cout<<"Sequence of positive order keywords:"<<endl;
for(int i=1;i<=N;i++){
cout<<l.a[i].key<<" ";
}
cout<<"\n Please enter the keyword you want to find:"<<endl;
int k;
cin>>k;
int tm=BinSearch(l,k);
if(tm!=0){
cout<<k<<"Appears on the second page of a positive order keyword"<<tm<<"position"<<endl;
}
else{
cout<<"No such element"<<endl;
}
return 0;
}
Operation results
Hash table
#include <iostream>
#include <cstdlib>
using namespace std;
const int Hashlength=41;
#define M 37
#define N 30
typedef struct{
int key;
}Stud;
typedef struct{
Stud a[100];//a[0] is the work unit
int length;
}RecordList;
typedef struct{
int key;
int sum;//Number of lookups
}HahList;
HahList hasha[Hashlength];
void CreatHash(RecordList l){
int i,count,adr,d;
//Initialize hash table
for(i=1;i<Hashlength;i++){
hasha[i].key=0;
hasha[i].sum=0;
}
for(i=1;i<=N;i++){
count=1;
adr=(l.a[i].key)%M;
d=adr;
if(hasha[adr].sum==0){
hasha[adr].key=l.a[i].key;
hasha[adr].sum=1;
}
else{
while(1){
d=(d+(l.a[i].key%10)+1)%M;
count++;
if(hasha[d].sum==0) break;
}
hasha[d].key=l.a[i].key;
hasha[d].sum=count;
}
}
}
void hashFind(int k){
int adr=k%M,d=adr,count=1;
if(hasha[adr].key==k) cout<<k<<"stay hash In the table is No"<<d<<"position,"<<"Found"<<count<<"second"<<endl;
else if(hasha[adr].key==0) cout<<"There is no such element"<<endl;
else{
while(1){
d=(d+(k%10)+1)%M;
count++;
if(hasha[d].key==k){
cout<<k<<"stay hash In the table is No"<<d<<"position,"<<"Found"<<count<<"second"<<endl;
break;
}
if(hasha[d].key==0){
cout<<"There is no such element"<<endl;
break;
}
}
}
}
int main(){
RecordList l;
cout<<"The following 30 elements are random numbers:"<<endl;
for(int i=1;i<=30;i++){
int t=rand()%100+1;
cout<<t<<" ";
l.a[i].key=t;
}
CreatHash(l);
cout<<"\n The following is Hash Table sequence diagram(Note that 0 means the position is empty):"<<endl;
for(int i=1;i<=Hashlength;i++){
cout<<hasha[i].key<<" ";
}
int k;
cout<<"\n Please enter the keyword you want to find:"<<endl;
cin>>k;
hashFind(k);
return 0;
}
The running result is that the hashlength needs to be long, and the number of times comes from the random number, and the range is 1-99;
