有哪些程序做的网站,做网站 内容越多越好,app应用下载网站源码,google推广技巧查找一般分为有序查找和无序查找#xff0c;这边在讲有序查找例二分查找二分查找就是在有序数组中#xff0c;通过mid(lowhigh)/2来判定中间值#xff0c;将中间值与待查找的值进行比较#xff0c;如果待查找的值大于中间值#xff0c;那么就将范围缩小#xff0c;查找右…查找一般分为有序查找和无序查找这边在讲有序查找例二分查找 二分查找就是在有序数组中通过mid(lowhigh)/2来判定中间值将中间值与待查找的值进行比较如果待查找的值大于中间值那么就将范围缩小查找右边如果待查找的值小于中间值那么查找左边如果待查找的值等于中间值查找成功。
int BinarySearch(int R[],int n, int K){
//在数组R中对半查找KR中关键词递增有序int low 1, high n, mid;while(low high){ //在Rlow…Rhigh之间查找Kmid(lowhigh)/2;if(KR[mid]) highmid-1; //在左半部分查找else if(KR[mid]) lowmid1; //在右半部分查找else return mid; //查找成功}return -1; //查找失败
} 在该算法中确定比较值是非常重要的一件事不同的比较值的确定可以决定不同的时间复杂度。所以还可以拓展出类似斐波那契查找插值查找之类的算法。二叉查找树例1.查找 其实二叉查找树在这边更像是一种结构就是结点的左孩子一定小于结点结点右孩子一定大于结点。查找到数据之后往往还要对数据进行处理在处理过后还要保持原有结构是比较困难的地方。
BSTnode* Search2(BSTnode* root, int K){ BSTnode* p root;while (p ! NULL) {if (K p-key) p p-left;else if (K p-key) p p-right;else return p;}return NULL;
}例2.插入就是找到对应的位置然后建立新的结点。
void Insert(BSTnode* root, int K){if (root NULL) root new BSTnode(K); else if (K root-key) Insert(root-left, K);else if (K root-key) Insert(root-right, K);
}例3.删除 这边的删除是在二叉树中一定有值等于k的结点的情况下否则要修改一些代码。
void remove(BSTnode* root, int K) {if(rootNULL) return;if(Kroot-key) remove(root-left, K); //在左子树删Kelse if(Kroot-key) remove(root-right, K); //在右子树删Kelse if(root-left!NULL root-right!NULL){BSTnode *sroot-right;while(s-left!NULL) ss-left;root-keys-key; //s为t右子树中根序列第一个结点remove(root-right, s-key);}else{ BSTnode* oldrootroot;root(root-left!NULL)? root-left:root-right;delete oldroot;}
}例4.高度平衡树 高度平衡树是二叉查找树中的一种它的左右孩子的高度差不会大于1它通过变形、旋转让树的结构变得相对“矮胖”方便后续处理缩小时间。但是这种结构就会对数据操作的过程提出很多额外的要求。 下面是关于旋转的一些基本操作。这边的代码都比较抽象适合配合图形理解。 以LL为例就是新插入的结点在A结点的左孩子的左子树上A结点是从下往上数第一个不平衡的点插入之后导致不再平衡。于是A结点的左孩子设为B结点的右孩子单独拎出来把右孩子变成A结点的左孩子然后将这个拎出的B结点作为新的结点它的右孩子连接到A结点上。
struct AVLnode {int key; //关键词int height; //以该结点为根的子树高度AVLnode *left, *right;AVLnode(int K){ keyK; height0; leftrightNULL; }
};
int Height(AVLnode *t){ return(tNULL)?-1:t-height; }
int max(int a, int b){ return (ab)? a:b; }
void UpdateHeight(AVLnode *t){t-height max(Height(t-left),Height(t-right))1;
}void LL(AVLnode* A) {AVLnode *B A-left;A-left B-right;B-right A;UpdateHeight(A);UpdateHeight(B);A B;
}void RR(AVLnode* A) {AVLnode *B A-right;A-right B-left;B-left A;UpdateHeight(A);UpdateHeight(B);A B;
}void RL(AVLnode* A){LL(A-right);RR(A);
}void LR(AVLnode* A) {RR(A-left);LL(A);
}AVL树插入算法的实现
void ReBalance(AVLnode* t) {if(tNULL) return;if(Height(t-left) - Height(t-right)2){ if(Height(t-left-left) Height(t-left-right)) LL(t);elseLR(t);}else if(Height(t-right) - Height(t-left)2){if(Height(t-right-right) Height(t-right-left)) RR(t);elseRL(t);}UpdateHeight(t);
}void Insert(AVLnode* root, int K) {if(rootNULL) rootnew AVLnode(K);else if(K root-key) //在左子树插入Insert(root-left, K);else if(K root-key) //在右子树插入Insert(root-right, K);ReBalance(root);
}AVL树删除算法的实现
void remove(AVLnode* root, int K) {if(rootNULL) return;if(Kroot-key) remove(root-left, K); //在左子树删Kelse if(Kroot-key) remove(root-right, K); //在右子树删Kelse if(root-left!NULL root-right!NULL){AVLnode *sroot-right;while(s-left!NULL) ss-left;root-keys-key; //s为t右子树中根序列第一个结点remove(root-right, s-key);}else{ AVLnode* oldrootroot;root(root-left!NULL)? root-left:root-right;delete oldroot;}ReBalance(root);
}所以其实比起怎么插入、删除更重要的是怎么保持原来的结构
