首页 > 代码库 > 算法10---二叉搜索树存在重复数据插入的实现
算法10---二叉搜索树存在重复数据插入的实现
算法10---二叉搜索树存在重复数据插入的实现
当用TREE-INSERT将n个具有相同关键字的数据项插入到一棵初始为空的二叉查找树中时，该算法的渐近性能如何？
我们可以对TREE-INSERT做一些改进，即在第5行的前面测试key[z] = key[x]，在第11行的前面测试key[z] = key[y]。如果等式成立，我们对下列策略中的某一种加以实现。对每一种策略，请给出将n个具有相同关键字的数据插入一棵初始为空的二叉查找树中的渐近性能（以下的策略是针对第5行的，比较的是z和x的关键字。将x换成y即可用于第11行）。
b）在结点x处设一个布尔标志b[x]，并根据b[x]的不同值，置x为left[x]或right[x]。每当插入一个与x具有相同关键字的结点时，b[x]取TRUE或FALSE。
c）在结点x处设置一个列表，其中所有结点都具有与x相同的关键字，并将z插入到该列表中。
d）随机地将置为left[x]或right[x]
思考：
b）每次测试到等式成立时，若b[x]为FLASE，插入到左子树中，b[x]为TRUE时，插入到右子树中，然后将b[x]取反。
c）使用一个链表，所有具有相同关键字的结点组成一个链表，结点中的一个指针指向这个链表。
d）使用rand()%2随机地决定插入到左子树中还是右子树中。
代码实现如下；首先是b方法
1 //二叉查找树结点的结构 2 struct node 3 { 4 int key;//关键字 5 int data;//卫星数据 6 bool b; 7 node *left;//左孩子 8 node *right;//右孩子 9 node *p;//父结点10 node(int x):key(x),data(x),b(0),left(NULL),right(NULL),p(NULL){}; //初始化11 };12 //二叉查找树的结构13 struct tree14 {15 node *root;16 tree():root(NULL){}//都是初始化的方法17 };18 //二叉查找树的插入19 void Tree_Insert(tree *T, node *z)20 {21 //找到要插入的位置22 node *x = T->root, *y = NULL;23 //若x为空,x是要插入的位置，x的父是z->p24 while(x != NULL)25 {26 y = x;27 //等式成立时，由b决定插入到哪个子树28 if(z->key == x->key)29 {30 if(x->b == 0)31 x = x->left;32 else33 x = x->right;34 //对b取反35 x->b = !x->b;36 }37 else if(z->key < x->key)38 x = x->left;39 else40 x = x->right;41 }42 //修改指针，注意树为空的情况43 z->p = y;44 if(y == NULL)45 T->root = z;46 else if(z->key == y->key)47 {48 if(y->b == 0)49 y->left = z;50 else y->right = z;51 y->b = !y->b;52 }53 else if(z->key < y->key)54 y->left = z;55 else y->right = z;56 }
C方法代码实现如下
1 //二叉查找树结点的结构 2 struct node 3 { 4 int key;//关键字 5 int data;//卫星数据 6 node *next;//指向具体相同关键字的链表 7 node *left;//左孩子 8 node *right;//右孩子 9 node *p;//父结点10 node(int x):key(x),data(x),left(NULL),right(NULL),p(NULL),next(NULL){}11 };12 //二叉查找树的结构13 struct tree14 {15 node *root;16 tree():root(NULL){}17 };18 //二叉查找树的插入19 void Tree_Insert(tree *T, node *z)20 {21 //找到要插入的位置22 node *x = T->root, *y = NULL;23 //若x为空,x是要插入的位置，x的父是z->p24 while(x != NULL)25 {26 y = x;27 //等式成立时，不继续插入到子树中，而是链入链表中28 if(z->key == x->key)29 {30 z->next = x->next;31 x->next = z;32 return;33 }34 else if(z->key < x->key)35 x = x->left;36 else37 x = x->right;38 }39 //修改指针，注意树为空的情况40 z->p = y;41 if(y == NULL)42 T->root = z;43 //等式成立时，不是插入到子树中，而是链入链表中44 else if(z->key == y->key)45 {46 z->next = y->next;47 y->next = z;48 }49 else if(z->key < y->key)50 y->left = z;51 else y->right = z;52 }
d方法实现如下
1 //二叉查找树结点的结构 2 struct node 3 { 4 int key;//关键字 5 int data;//卫星数据 6 node *left;//左孩子 7 node *right;//右孩子 8 node *p;//父结点 9 node(int x):key(x),data(x),left(NULL),right(NULL),p(NULL){}10 };11 //二叉查找树的结构12 struct tree13 {14 node *root;15 tree():root(NULL){}16 };17 //二叉查找树的插入18 void Tree_Insert(tree *T, node *z)19 {20 //找到要插入的位置21 node *x = T->root, *y = NULL;22 //若x为空,x是要插入的位置，x的父是z->p23 while(x != NULL)24 {25 y = x;26 //若等式成立，随机地决定插入到哪个子树中27 if(z->key == x->key)28 {29 if(rand()%2 == 0)30 x = x->left;31 else32 x = x->right;33 }34 else if(z->key < x->key)35 x = x->left;36 else37 x = x->right;38 }39 //修改指针，注意树为空的情况40 z->p = y;41 if(y == NULL)42 T->root = z;43 else if(z->key == y->key)44 {45 if(rand()%2 == 0)46 x = x->left;47 else48 x = x->right;49 }50 else if(z->key < y->key)51 y->left = z;52 else y->right = z;53 }
算法10---二叉搜索树存在重复数据插入的实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。