精华内容
下载资源
问答
  • 二进制树搜索算法的实现步骤
    千次阅读
    2020-07-27 11:11:05

    二进制树型搜索算法

    Binary Search is applied on the sorted array or list of large size. It's time complexity of O(log n) makes it very fast as compared to other sorting algorithms. The only limitation is that the array or list of elements must be sorted for the binary search algorithm to work on it.

    二进制搜索应用于排序后的数组或大型列表。 O(log n)的时间复杂性使其与其他排序算法相比非常快。 唯一的限制是必须对元素的数组或列表进行排序,以便二进制搜索算法可以对其进行处理。

    实现二进制搜索算法 (Implementing Binary Search Algorithm)

    Following are the steps of implementation that we will be following:

    以下是我们将要执行的实现步骤:

    1. Start with the middle element:

      从中间元素开始:

      • target value is equal to the middle element of the array, then return the index of the middle element.目标值等于数组的中间元素,则返回中间元素的索引。
        • If the target value is greater than the number in the middle index, then pick the elements to the right of the middle index, and start with Step 1.
        • If the target value is less than the number in the middle index, then pick the elements to the left of the middle index, and start with Step 1.
    2. When a match is found, return the index of the element matched.

      找到匹配项后,返回匹配元素的索引。

    3. If no match is found, then return -1

      如果找不到匹配项,则返回-1

    /*
        function for carrying out binary search on given array
        - values[] => given sorted array
        - len => length of the array
        - target => value to be searched
    */
    int binarySearch(int values[], int len, int target)
    {
        int max = (len - 1);
        int min = 0;
        
        int guess;  // this will hold the index of middle elements
        int step = 0;  // to find out in how many steps we completed the search
        
        while(max >= min)
        {
            guess = (max + min) / 2;
            // we made the first guess, incrementing step by 1
            step++;
            
            if(values[guess] ==  target)
            {
                printf("Number of steps required for search: %d \n", step);
                return guess;
            }
            else if(values[guess] >  target) 
            {
                // target would be in the left half
                max = (guess - 1);
            }
            else
            {
                // target would be in the right half
                min = (guess + 1);
            }
        }
     
        // We reach here when element is not 
        // present in array
        return -1;
    }
     
    int main(void)
    {
        int values[] = {13, 21, 54, 81, 90};
        int n = sizeof(values) / sizeof(values[0]);
        int target = 81;
        int result = binarySearch(values, n, target);
        if(result == -1)
        {  
            printf("Element is not present in the given array.");
        }
        else
        {
            printf("Element is present at index: %d", result);
        }
        return 0;
    }

    We hope the above code is clear, if you have any confusion, post your question in our Q & A Forum.

    我们希望上面的代码清晰明了,如果您有任何疑问,请在我们的“ 问答论坛”中发布您的问题。

    Now let's try to understand, why is the time complexity of binary search O(log n) and how can we calculate the number of steps required to search an element from a given array using binary search without doing any calculations. It's super easy! Are you ready?

    现在让我们尝试理解,为什么二分查找的时间复杂度为O(log n),以及如何在不进行任何计算的情况下使用二分查找来计算从给定数组中搜索元素所需的步数。 超级容易! 你准备好了吗?

    二元搜索的时间复杂度O(log n) (Time Complexity of Binary Search O(log n))

    When we say the time complexity is log n, we actually mean log2 n, although the base of the log doesn't matter in asymptotic notations, but still to understand this better, we generally consider a base of 2.

    当我们说时间复杂度是log n ,我们实际上是指log 2 n ,尽管对数的底数在渐进表示法中并不重要,但是为了更好地理解这一点,我们通常考虑2的底数。

    Let's first understand what log2(n) means.

    首先让我们了解log 2 (n)含义。

    Expression: log2(n) - - - - - - - - - - - - - - - For n = 2: log2(21) = 1 Output = 1 - - - - - - - - - - - - - - - For n = 4 log2(22) = 2 Output = 2 - - - - - - - - - - - - - - - For n = 8 log2(23) = 3 Output = 3 - - - - - - - - - - - - - - - For n = 256 log2(28) = 8 Output = 8 - - - - - - - - - - - - - - - For n = 2048 log2(211) = 11 Output = 11

    表达式:log 2 (n)---------------对于n = 2:log 2 (2 1 )= 1输出= 1------------ ---对于n = 4 log 2 (2 2 )= 2输出= 2----------------对于n = 8 log 2 (2 3 )= 3输出= 3-- --------------对于n = 2048 log 2 (n = 256 log 2 (2 8 )= 8输出= 8---------------- 2 11 )= 11输出= 11

    Now that we know how log2(n) works with different values of n, it will be easier for us to relate it with the time complexity of the binary search algorithm and also to understand how we can find out the number of steps required to search any number using binary search for any value of n.

    现在我们知道如何log 2 (n)与不同价值观的作品n ,这将是我们更容易与二进制搜索算法的时间复杂度有关,同时还应了解我们如何能够找出需要的步数使用二进制搜索n任何值来搜索任何数字。

    计算步数 (Counting the Number of Steps)

    As we have already seen, that with every incorrect guess, binary search cuts down the list of elements into half. So if we start with 32 elements, after first unsuccessful guess, we will be left with 16 elements.

    正如我们已经看到的,每进行一次错误的guess ,二进制搜索就会将元素列表缩减为一半。 因此,如果我们从32个元素开始,则在第一次失败的猜测之后,我们将剩下16个元素。

    So consider an array with 8 elements, after the first unsuccessful, binary sort will cut down the list to half, leaving behind 4 elements, then 2 elements after the second unsuccessful guess, and finally only 1 element will be left, which will either be the target or not, checking that will involve one more step. So all in all binary search needed at most 4 guesses to search the target in an array with 8 elements.

    因此,考虑一个包含8个元素的数组,在第一个不成功的二进制排序之后,将列表减半,剩下4个元素,然后在第二个不成功的猜测之后保留2个元素,最后只剩下1个元素,或者是否达到target ,检查将涉及更多步骤。 因此,所有二进制搜索最多需要4个猜测才能在具有8个元素的数组中搜索target

    If the size of the list would have been 16, then after the first unsuccessful guess, we would have been left with 8 elements. And after that, as we know, we need atmost 4 guesses, add 1 guess to cut down the list from 16 to 8, that brings us to 5 guesses.

    如果列表的大小为16,则在第一次不成功的猜测之后,我们将剩下8个元素。 然后,据我们所知,我们最多需要4个猜测,再加上1个猜测就可以将列表从16个减少到8个,这使我们得到5个猜测。

    So we can say, as the number of elements are getting doubled, the number of guesses required to find the target increments by 1.

    因此,可以说,随着元素数量增加一倍,找到target所需的猜测数量将增加1

    Seeing the pattern, right?

    看到图案了吧?

    Generalizing this, we can say, for an array with n elements,

    概括地说,对于具有n元素的数组,

    n, until we get the value 1, plus one.n开始可以重复减半的次数,直到获得值1加1。

    And guess what, in mathematics, the function log2 n means exactly same. We have already seen how the log function works above, did you notice something there?

    并猜想在数学上,函数log 2 n含义是完全相同的。 我们已经在上面看到了log函数的工作方式,您在那儿注意到了吗?

    For n = 8, the output of log2 n comes out to be 3, which means the array can be halved 3 times maximum, hence the number of steps(at most) to find the target value will be (3 + 1) = 4.

    对于n = 8 ,对log 2 n的输出为3 ,这意味着该数组可以减半为最大3倍,因此(最多)查找目标值的步骤数将为(3 +1)= 4。

    Question for you: What will be the maximum number of guesses required by Binary Search, to search a number in a list of 2,097,152 elements?

    您的问题:二进制搜索要搜索2097152个元素列表中的数字,最大猜想数是多少?

    翻译自: https://www.studytonight.com/data-structures/binary-search-algorithm

    二进制树型搜索算法

    更多相关内容
  • 动态二进制树搜索算法 二进制搜索树 (Binary Search Tree) A binary search tree is a useful data structure for fast addition and removal of data. 二进制搜索树是用于快速添加和删除数据的有用数据结构。 It...

    动态二进制树搜索算法

    A binary search tree is a useful data structure for fast addition and removal of data.

    二进制搜索树是用于快速添加和删除数据的有用数据结构。

    It is composed of nodes, which stores data and also links to upto two other child nodes. It is the relationship between the leaves linked to and the linking leaf, also known as the parent node, which makes the binary tree such an efficient data structure.

    它由节点组成,节点存储数据并链接到最多两个其他子节点。 链接到的叶子与链接叶子(也称为父节点)之间的关系使二叉树成为一种高效的数据结构。

    For a binary tree to be a binary search tree, the data of all the nodes in the left sub-tree of the root node should be less than the data of the root. The data of all the nodes in the right subtree of the root node should be greater than equal to the data of the root. As a result, the leaves on the farthest left of the tree have the lowest values, whereas the leaves on the right of the tree have the greatest values.

    为了使二叉树成为二叉搜索树,根节点左子树中所有节点的数据应小于根节点的数据。 根节点右子树中所有节点的数据应大于等于根节点的数据。 结果,树最左边的叶子具有最低的值,而树右边的叶子具有最大的值。

    A representation of binary search tree looks like the following:

    二进制搜索树的表示形式如下所示:

    Binary Search Tree

    Consider the root node 20. All elements to the left of subtree(10, 5) are less than 20 and all elements to the right of subtree(25, 30, 35) are greater than 20.

    考虑根节点20。子树(10,5)左侧的所有元素都小于20,子树(25,30,35)右侧的所有元素都大于20。

    实施BST (Implementation of BST)

    First, define a struct as tree_node. It will store the data and pointers to left and right subtree.

    首先,将一个结构定义为tree_node 。 它将存储数据以及指向左和右子树的指针。

    struct tree_node
    {
    	int data;
    	tree_node *left, *right;
    };

    The node itself is very similar to the node in a linked list. A basic knowledge of the code for a linked list will be very helpful in understanding the techniques of binary trees.

    该节点本身与链表中的节点非常相似。 链表代码的基本知识将有助于理解二叉树的技术。

    It is most logical to create a binary search tree class to encapsulate the workings of the tree into a single area, and also making it reusable. The class will contain functions to insert data into the tree, search if the data is present and methods for traversing the tree.

    创建二进制搜索树类以将树的工作封装到单个区域中并使其可重用是最合乎逻辑的。 该类将包含将数据插入树中,搜索数据是否存在以及遍历树的方法的函数。

    class BST
    {
    	tree_node *root;
    	void insert(tree_node* , int );
    	bool search(int , tree_node* );
    	void inorder(tree_node* );
    	void preorder(tree_node* );
    	void postorder(tree_node* );
    
    	public:
    	BST()
    	{
    		root = NULL;
    	}
    	void insert(int );
    	bool search(int key);
        void inorder();
        void preorder();
        void postorder();
    };

    It is necessary to initialize root to NULL for the later functions to be able to recognize that it does not exist.

    必须将root初始化为NULL,以便以后的功能能够识别它不存在。

    All the public members of the class are designed to allow the user of the class to use the class without dealing with the underlying design. The functions which will be called recursively are the ones which are private, allowing them to travel down the tree.

    该类的所有公共成员都被设计为允许该类的用户使用该类,而无需处理基础设计。 将被递归调用的函数是私有的,从而使它们可以向下移动。

    插入BST (Insertion in a BST)

    To insert data into a binary tree involves a function searching for an unused node in the proper position in the tree in which to insert the key value. The insert function is generally a recursive function that continues moving down the levels of a binary tree until there is an unused leaf in a position which follows the following rules of placing nodes.

    将数据插入二叉树涉及到一个函数,该函数在树中要插入键值的适当位置中搜索未使用的节点。 插入函数通常是递归函数,它继续向下移动二叉树的级别,直到某个位置上有未使用的叶子为止,该叶子遵循以下放置节点的规则。

    • Compare data of the root node and element to be inserted.

      比较根节点和要插入的元素的数据。

    • If the data of the root node is greater, and if a left subtree exists, then repeat step 1 with root = root of left subtree. Else,

      如果根节点的数据更大,并且存在左子树,则使用root = left subtree的root重复步骤1。 其他,

    • Insert element as left child of current root.

      插入元素作为当前根的左子元素。

    • If the data of the root node is greater, and if a right subtree exists, then repeat step 1 with root = root of right subtree.

      如果根节点的数据更大,并且存在右子树,则使用root = right subtree的root重复步骤1。

    • Else, insert element as right child of current root.

      否则,将元素插入为当前根的右子元素。

    Binary Search Tree
    void BST :: insert(tree_node *node, int d)
    {
    	// element to be inserted is lesser than node’s data
    	if(d < node->data)
    	{
    		// if left subtree is present
    		if(node->left != NULL)
    			insert(node->left, d);
    		
    		// create new node
    		else
    		{
    			node->left = new tree_node;
    			node->left->data = d;
    			node->left->left = NULL;
    			node->left->right = NULL;
    		}
    	}
    
    	// element to be inserted is greater than node’s data
    	else if(d >= node->data)
    	{
    		// if left subtree is present
    		if(node->right != NULL)
    			insert(node->right, d);
    		
    		// create new node
    		else
    		{
    			node->right = new tree_node;
    			node->right->data = d;
    			node->right->left = NULL;
    			node->right->right = NULL;
    		}
    	}
    	
    }

    Since the root node is a private member, we also write a public member function which is available to non-members of the class. It calls the private recursive function to insert an element and also takes care of the case when root node is NULL.

    由于根节点是私有成员,因此我们还编写了一个公共成员函数,该函数可供该类的非成员使用。 它调用私有递归函数来插入元素,并且还要注意当根节点为NULL时的情况。

    void BST::insert(int d)
    {
    	if(root!=NULL)
                    insert(root, d);
    	else
        {
            root = new tree_node;
            root->data = d;
            root->left = NULL;
            root->right = NULL;
        }
    }

    在BST中搜索 (Searching in a BST)

    The search function works in a similar fashion as insert. It will check if the key value of the current node is the value to be searched. If not, it should check to see if the value to be searched for is less than the value of the node, in which case it should be recursively called on the left child node, or if it is greater than the value of the node, it should be recursively called on the right child node.

    搜索功能的工作方式与插入类似。 它将检查当前节点的键值是否为要搜索的值。 如果不是,则应检查要搜索的值是否小于节点的值,在这种情况下,应在左侧的子节点上递归调用该值,或者应大于节点的值,应该在正确的子节点上递归调用它。

    • Compare data of the root node and the value to be searched.

      比较根节点的数据和要搜索的值。

    • If the data of the root node is greater, and if a left subtree exists, then repeat step 1 with root = root of left subtree. Else,

      如果根节点的数据更大,并且存在左子树,则使用root = left subtree的root重复步骤1。 其他,

    • If the data of the root node is greater, and if a right subtree exists, then repeat step 1 with root = root of right subtree. Else,

      如果根节点的数据更大,并且存在右子树,则使用root = right subtree的root重复步骤1。 其他,

    • If the value to be searched is equal to the data of root node, return true.

      如果要搜索的值等于根节点的数据,则返回true。

    • Else, return false.

      否则,返回false。

    bool BST::search(int d, tree_node *node)
    {
    	bool ans = false;
    
    	// node is not present
      	if(node == NULL)
     		return false;
    	
    	// Node’s data is equal to value searched
        if(d == node->data)
          	return true;
    	
    	// Node’s data is greater than value searched
        else if(d < node->data)
           	ans = search(d, node->left);
    
    	// Node’s data is lesser than value searched
        else
           	ans = search(d, node->right);
      
        return ans;
    }

    Since the root node is a private member, we also write a public member function which is available to non-members of the class. It calls the private recursive function to search an element and also takes care of the case when root node is NULL.

    由于根节点是私有成员,因此我们还编写了一个公共成员函数,该函数可供该类的非成员使用。 它调用私有递归函数来搜索元素,并且还要注意根节点为NULL的情况。

    bool BST::search(int d)
    {
    	if(root ==  NULL)
    		return false;
    	else	
    		return  search(d, root);
    }

    在BST中遍历 (Traversing in a BST)

    There are mainly three types of tree traversals:

    树遍历主要有三种类型:

    1.预定遍历: (1. Pre-order Traversal:)

    In this technique, we do the following :

    在此技术中,我们执行以下操作:

    • Process data of root node.

      根节点的处理数据。

    • First, traverse left subtree completely.

      首先,完全遍历左子树。

    • Then, traverse right subtree.

      然后,遍历右子树。

    void BST :: preorder(tree_node *node)
    {
    	if(node !=  NULL)
        {
    		cout<<node->data<<endl;
           	preorder(node->left);
           	preorder(node->right);
        }
    }

    2.订单遍历 (2. Post-order Traversal)

    In this traversal technique we do the following:

    在这种遍历技术中,我们执行以下操作:

    • First traverse left subtree completely.

      完全遍历左子树。

    • Then, traverse right subtree completely.

      然后,完全遍历右子树。

    • Then, process data of node.

      然后,处理节点的数据。

    void BST :: postorder(tree_node *node)
    {
    	if(node !=  NULL)
       	{
            postorder(node->left);
            postorder(node->right);
    	    cout<<node->data<<endl;
       	}
    }

    3.有序遍历 (3. In-order Traversal)

    In in-order traversal, we do the following:

    在有序遍历中,我们执行以下操作:

    • First process left subtree.

      首先处理左子树。

    • Then, process current root node.

      然后,处理当前的根节点。

    • Then, process right subtree.

      然后,处理右子树。

    void BST :: inorder(tree_node *node)
    {
    	if(node !=  NULL)
       	{
            inorder(node->left);
    	    cout<<node->data<<endl;
            inorder(node->right);
       	}
    }

    The in-order traversal of a binary search tree gives a sorted ordering of the data elements that are present in the binary search tree. This is an important property of a binary search tree.

    二进制搜索树的有序遍历给出了二进制搜索树中存在的数据元素的排序顺序。 这是二进制搜索树的重要属性。

    Since the root node is a private member, we also write public member functions which is available to non-members of the class. It calls the private recursive function to traverse the tree and also takes care of the case when root node is NULL.

    由于根节点是私有成员,因此我们还编写了公共成员函数,该函数可供该类的非成员使用。 它调用私有递归函数遍历树,并且还照顾根节点为NULL的情况。

    void BST :: preorder()
    {
    	if(root ==  NULL)
    		cout<<"TREE IS  EMPTY\n";
    	else
           	preorder(root);
    }
    
    void BST :: postorder()
    {
    	if(root ==  NULL)
    		cout<<"TREE IS  EMPTY\n";
    	else
    	    postorder(root);
    }
    
    void BST :: inorder()
    {
    	if(root == NULL)
    		cout<<"TREE IS EMPTY\n";
    	else
    		inorder(root);
    }

    复杂度分析 (Complexity Analysis)

    Binary Search Tree

    The time complexity of search and insert rely on the height of the tree. On average, binary search trees with n nodes have O(log n) height. However in the worst case the tree can have a height of O(n) when the unbalanced tree resembles a linked list. For example in this case :

    搜索和插入的时间复杂度取决于树的高度。 平均而言,具有n个节点的二叉搜索树的高度为O(log n) 。 但是,在最坏的情况下,当不平衡树类似于链表时,树的高度可能为O(n) 。 例如在这种情况下:

    Binary Search Tree

    Traversal requires O(n) time, since every node must be visited.

    遍历需要O(n)时间,因为必须访问每个节点。

    翻译自: https://www.studytonight.com/data-structures/binary-search-tree

    动态二进制树搜索算法

    展开全文
  • (1)普通二进制树搜索: 设计一个1、11、21…标签数目 ①先设计一个GUI界面,得到8位二进制数的随机序列,分成256份。 ②先对每一次都找出碰撞的最高位; ③选择比碰撞位小的二进制数,然后继续进行第②步骤,直至...

    实现语言:python

    实验要求:
    (1)普通二进制树搜索:
    设计一个1、11、21…标签数目
    ①先设计一个GUI界面,得到8位二进制数的随机序列,分成256份。
    ②先对每一次都找出碰撞的最高位;
    ③选择比碰撞位小的二进制数,然后继续进行第②步骤,直至选择出最小的那一个;
    ④去除最小的那一行,在进行第二三四步的循环,并记下用时;
    ⑤画出每一次找到一个标签的运行用时曲线图。
    (2)二分支搜索…

    原理:

    1.普通二进制搜索算法
    二进制搜索技术以唯一的序列号来识别射频电子标签为基础。为了从一簇射频电子标签中选择其中之一,射频读写器发出一个读命令,将射频电子标签序列号传输时的数据碰撞引导到射频读写器,即由射频读写器判断是否有碰撞发生。如果有,则进一步搜索。在二进制算法的实现中,起决定作用的是射频读写器所使用的信号编码必须能够确定碰撞发生的准确位置。因此,一般使用可以进行位碰撞检测的曼彻斯特编码发送数据。

    前提,读写器并不知道各个标签各自的ID号,只能根据曼彻斯特编码判断有没有碰撞。
    在普通二进制算法中,根据所给标签数生成对应的唯一标签ID,并进行普通二进制搜索算法:选取标签的第1位字符,与所假定标签“11111111”的第一位字符进行匹配,如果匹配数为1,则读写器确定匹配,直接和这个标签进行通信,并将其从标签从数组中删去,将匹配字符串和索引index初始化,重新匹配;若匹配到的标签数为0,就将所假定标签“11111111”的第1(n)位取反,然后继续重新匹配;若匹配到的标签数为2,就将需要匹配的字符数+1(本来匹配前n位,现在匹配前n+1位),再次匹配;不断循环,直到标签集合中无标签为止。
    在这里插入图片描述
    流程图如下:
    在这里插入图片描述
    2.二分支搜索
    二分支搜索方法采用递归的工作方式,遇到碰撞就随机地进行分支,成为多个子集。在接下来的时隙中,主要解决信息包所发生的碰撞。如果再次发生碰撞,就继续随机地分为多个分支。然后依次进行查询,标签被分支后,由于响应的标签数量减少,再次发生碰撞的概率降低,通过不断的分支,减少响应标签的数量,直至分支内没有或仅有一个标签响应。

    在二分支搜索中,不可避免的每一次都要搜索0,1。如果返回的标签数大于2,就进一步递归,将前缀的字符串加上0、1两种方式分别再次递归搜索;如果等于1就被被选中,直接进行通信,如果等于0就直接返回不操作。
    在这里插入图片描述
    普通二进制搜索的python代码如下

    import math
    import random
    import time
    from tkinter import *
    
    #tkinter界面设计 
    root = Tk()
    Label(root,text='二进制树仿真').grid(row = 0, column = 1)
    Label(root,text = '显示n个标签的识别').grid(row = 1, column = 0, padx = 10, pady = 5)
    entry1= Entry(root)
    entry1.grid(row = 1, column = 1, padx = 10, pady = 5)
    
    #回调函数
    def callback():
        n = int(entry1.get())
        listbox1.delete(0,END)
        listbox2.delete(0,END)
        text1.delete(1.0,END)
        w.delete(ALL)
        #初始化
        tags=[]
        print(n)
        list1=random.sample(range(256),n) #使用sample产生一个不重复的数组
        for i in range(n):
            tags.append('{:08b}'.format( list1[i])) #'{:08b}'.format( list1[i])  08b将list1转化为二进制且高位补零
        for i in range(n):
            listbox1.insert(END,str(tags[i]))
        print(tags)
    
    
        react_num=0
        request = '11111111'
        index = 0
        #初始化结束
        def search(react_num,request,index):
            global a                                     #a 必须声明为全局变量,原因我也不太清楚
            global n
            for i in range(len(tags)):              #对每一个标签进行匹配
                if tags[i][0:index]==request[0:index]:
                    react_num += 1
                    a = i
            return react_num, a                       #这样可以返回多个值,保存于一个元组之中
    
        start = time.time()
        react_num = search(0, request, index)[0] #搜索到的响应个数
        b = search(0, request, index)[1] #搜索到的下标,由于request和 index都没有变,所以还是一样的结果
        while (len(tags)):  
            if react_num == 1:
                    print(tags[b])
                    listbox2.insert(END,str(tags[b])) #将其表现在框中
                    mid_end = time.time() #将其表现在画布上
                    w.create_oval((5*(n-len(tags))-1), (200-100*(mid_end - start)-1),\
                                  (5*(n-len(tags))+1), (200-100*(mid_end - start)+1), fill="red")
                    index = 0
                    del tags[b]          #如果为1,则将其输出,并从列表中删去
                    request = '11111111'
                    react_num = search(0, request, index)[0]
                    b = search(0, request, index)[1]
            elif react_num >1:
                    index += 1          #如果大于2个,就将索引加一重新查找
                    react_num = search(0, request, index)[0]
                    b = search(0, request, index)[1]
            elif react_num < 1:
                    temp = request[0:index-1]+str(1-int(request[index])) #如果react_num<1, 则无, 就要改变request
                    request = temp + request[index:]  #改变request
                    react_num = search(0, request, index)[0] 
                    b = search(0, request, index)[1]
    
        end = time.time()
        print(end - start)
        text1.insert(INSERT,str(end-start))
    
        
    B = Button(root,text = '确定', width=10, command = callback)
    B.grid(row = 1, column = 2, padx=10, pady=5)
    
    group1 = LabelFrame(root, text="标签")
    group2 = LabelFrame(root, text="识别后")
    group1.grid(row = 2, column = 0, padx=10, pady=5)
    group2.grid(row = 2, column = 2, padx=10, pady=5)
    scrollbar1 = Scrollbar(group1)
    scrollbar2 = Scrollbar(group2)
    scrollbar1.pack(side=RIGHT, fill=Y)
    scrollbar2.pack(side=RIGHT, fill=Y)
    listbox1 = Listbox(group1, yscrollcommand=scrollbar1.set)
    listbox1.pack(anchor = W)
    listbox2 = Listbox(group2, yscrollcommand=scrollbar2.set)
    listbox2.pack(anchor = W)
    scrollbar1.config(command=listbox1.yview)
    scrollbar2.config(command=listbox2.yview)
    Label(root,text = '程序运行时间 :').grid(row = 3, column = 0, padx = 10, pady = 5)
    text1 = Text(root, width=20, height=1)
    text1.grid(row = 3, column = 1, padx = 10, pady = 5)
    group3 = LabelFrame(root, text="曲线")
    group3.grid(row = 4, column = 0, columnspan = 3, padx = 10, pady = 5)
    w = Canvas(group3, width=400, height=200)
    w.pack()
    
    mainloop()
    

    实验结果图
    在这里插入图片描述
    由于能力有限,曲线是使用tkinter的canvas组件画的,后期也可以改成用matplotlib

    上图实验结果显示
    在最开始的时候,列表中有128个标签,要得到唯一的一个标签ID,需要迭代8次,时间比较长,可以看出,曲线刚开始的时候斜率较大,一个标签识别需要运行时间长(需要迭代八次);后来曲线的斜率较小,因为前面的标签找到后就从列表中删除了,列表小了,标签数少了,要找到一个唯一的标签时间变短了(需要迭代的次数少了)。
    二分支算法使用递归实现,做法类似

    最后实验结果:
    普通二进制搜索算法每一次查找都是从头开始,这就导致了效率的低下,为了从较大量的电子标签中发现一个单独的电子标签,需要重复操作。其平均次数L取决于读写器作用范围内电子标签总数N;当标签总数为32时,平均需要6次迭代才能找出唯一标签;当标签总数为64时,平均7次;当标签总数为128时,平均需要8次,效率较低。

    而二分支搜索算法由于每一次不需要从头开始,并且使用递归搜索,不计算递归所带来的资源成本的话,就吞吐量来说,该算法是比较优秀的,找到唯一的解所需的平均查找操作次数大约为4次,即使标签数目不断增大,二分支树的深度也不会超过16层,而由于不需要重复查找,吞吐量和效率就比较高。

    展开全文
  • 物联12:二进制树型搜索算法

    万次阅读 2015-04-15 10:43:49
    二进制防碰撞算法基于轮询的办法,按照二进制树模型和一定的顺序对所有的可能进行遍历,因此它不是基于概率的箅法,而是一种确定性的防碰撞算法,但该算法要将所有可能全部遍历,因此其应用起来比较慢。  二进制...

    二进制树型搜索算法

            纯ALOHA算法和时隙ALOHA算法的信道最佳利用率为18.4%和36.8%,随着标签数量的增加,其性能急剧恶化,因此人们提出了二进制搜索算法。二进制防碰撞算法基于轮询的办法,按照二进制树模型和一定的顺序对所有的可能进行遍历,因此它不是基于概率的箅法,而是一种确定性的防碰撞算法,但该算法要将所有可能全部遍历,因此其应用起来比较慢。

            二进制树型搜索算法由读写器控制,基本思想是不断的将导致碰撞的电子标签进行划分,缩小下一步搜索的标签数量,直到只有一个电子标签进行回应。

    二进制搜索算法的基本思路是,多个标签进入读写器工作场后,读写器发送带限制条件的询问命令,满足限制条件的标签回答,如果发生碰撞,则根据发生错误的位修改限制条件,再一次发送询问命令,直到找到一个正确的回答,并完成对该标签的读写操作。对剩余的标签重复以上操作,直到完成对所有标签的读写操作。      

            为了实现二进制搜索算法,就要选用曼彻斯特编码,因为这种编码可以检测出碰撞位。    为了实现这个算法,引入以下4种命令。

    1.冲突位检测

            实现该算法系统的必要前提是能够辨认出在读写器中数据冲突位的准确位置。为此,必须有合适的位编码法。如图对NRZ编码和曼彻斯特编码的冲突状况作一比较。

    1)NRZ编码

            如果两个电子标签之一发送了副载波信号,那么,这个信号由读写器译码为“高”电平,就被认定为逻辑“1”。但读写器不能确定读入的某位究竟是若干个电子标签发送的数据相互重叠的结果,还是某个电子标签单独发送的信号。

    2)曼彻斯特编码

           如果两个或多个电子标签同时发送的数位有不同值,则接收的上升沿和下降沿互相抵消,“没有变化”的状态是不允许的,将作为错误被识别。用这种方法可以按位追溯跟踪冲突的出现。

      

             结论:二进制搜索算法,要选用曼彻斯特编码。

    2.用于“二进制树搜索”算法命令

    1)REQUEST 请求系列号

        发送一序列号作为参数给区域内标签。序列号小于或者等于的标签,回送其序列号给阅读器。(缩小范围)

    2)SELECT  选择系列号

        用某个(事先确定的)序列号作为参数发送给标签。具有相同的序列号的标签将以此作为执行其他命令(读出和写入)的切入开关,即选择了标签。

    3)READDATA  读出数据

         选中的标签将存储的数据发送给阅读器。

    4)UNSELECT   退出选择

         取消一个事先选中的标签,标签进入无声状态,这样标签对REQUEST命令不作应答。

    3.二进制树型搜索算法过程

        基本思想是将处于冲突的标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,依次类推,直到识别出子集0中所有标签,再按此步骤查询子集1。

        因此,标签的序列号是处理碰撞的基础。

      

            具体实例,参照后一篇博文。

    展开全文
  • 二进制树型搜索算法由读写器控制。基本思想是不断将导致碰撞的电子标签进行划分,缩小下一步搜索的标签数量,直到只有一个电子标签进行回应,即没有碰撞发生。具体方法是将处于冲突的标签分为左右两个子集0和1,先...
  • 二进制树型搜索算法实现步骤如下:  (1)读写器广播发送最大序列号查询条件Q,其作用范围内的标签在同一时刻传输它们的序列号至读写器。  (2)读写器对收到的标签进行响应,如果出现不一致
  • 8-4 RFID系统二进制树搜索算法是如何解决碰撞的?简述其实现步骤。  将处于冲突的标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,依次类...
  • 二进制树型搜索算法由读写器控制,基本思想是不断的将导致碰撞的电子标签进行划分,缩小下一步搜索的标签数量,直到只有一个电子标签进行回应。  二进制搜索算法的基本思路是,多个标签进入读写器工作场后,读写...
  • 在RFID防碰撞算法中,二进制树算法是目前应用最广泛的一种。因为在算法执行过程中,读写器要多次发送命令给应答器,每次命令都把应答器分成两组,多次分组后最终得到唯一的一个应答器,在这个分组过程中,将对应的...
  • 二进制树搜索算法(如下图所示)的基本思想是将处于冲突的标签分成左右两个子集0和1,先查询子集0,如果没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,以此类推,直到识别出子集0中...
  • RFID二进制树搜索算法模拟实现C++

    千次阅读 2020-01-03 23:08:20
    二进制树搜索算法的基本思想是将处于冲突的标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,直到识别出子集0中的所有标签,再按此步骤查询...
  • 其具体实现步骤如下: 1、读写器广播发送最大序列号查询条件Q,其作用范围内的标签在同一时刻传输它们的序列号至读写器。 2、读写器对收到的标签进行响应,如果出现不一致的现象(有的序列号该位是0,有的该位...
  • 二进制搜索防碰撞算法中用的主要命令有: 1、Request(请求):阅读器向其识别区中的标签发送带有标签序列号的请求命令,标签接到命令后,其自身序列号小于或者等于该序列号的标签会将自己的序列号发送给阅读器,...
  •   二制树型搜索算法由读写器控制,基本思想是...二进制树型搜索算法的模型如图所示,其基本思想是将处于冲突的标签分成左 右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突 则再分
  • 8-4、RFID系统二进制树型算法是如何解决碰撞的?简述其实现步骤。...二进制树型搜索算法实现步骤为:  【1】读写器广播发送最大序列号查询条件Q,其作用范围内的标签在同一时刻传输,它们的序列号至读写器;
  • RFID系统二进制数树型搜索算法是如何解决碰撞的?简述其实现步骤。 答:二进制树型搜索算法有读写器控制,基本思想是不断的将导致碰撞的 电子标签进行划分,缩小下一步搜索的标签数量,直到只有一个电子标签进行...
  • 蒙特卡洛树搜索算法实现In the previous article, we covered the fundamental concepts of reinforcement learning and closed the article with these two key questions: 在上一篇文章中 ,我们介绍了强化学习的...
  • 《娜璋带你读论文》系列主要是督促自己阅读优秀论文及听取学术讲座,并分享给...这篇文章将带来USENIXSec21恶意代码分析的经典论文,DeepReflect,它通过二进制重构发现恶意功能,来自于佐治亚理工。希望对您有所帮助~
  • 起初,我是希望寻找一个工具能够对比二进制文件的相似度,通过搜索之后,定位到了ssdeep这个工具,对这个工具进行了实践,能够得到一些相应的结果。但在这个过程中发现了一个博客复现了大致是17/18年左右一篇顶会...
  •  也可叫做分查找。它不仅可以查找数据,还可以高效地插入、删除数据。  特点:每个节点的key值大于左子节点,小于右子节点。注意它不一定是完全的二叉树。  所以节点的key是唯一的,我们就是通过它来...
  • 下面会介绍编写遗传算法的整体流程(附代码与代码解读),同时会提出一些小问题,对于这些问题我自己给出的解答会在文章最后,也只是自己的一点思考。 欢迎大家一起讨论( •̀ ω •́ )✧
  • JavaScript中的数据结构和算法可视化数据结构和算法 数据结构大批哈希表链表单链表双链表堆使用链表使用数组队列使用链表使用堆栈二进制搜索树(BST) 演算法数组中的TwoPairsSum 反转字符串第一个重复出现的字符...
  • 二进制LDPC码的构造及译码算法

    万次阅读 2018-09-09 16:11:04
    构造好的LDPC码校验矩阵和设计性能优异的译码算法是LDPC码研究领域的重点。  常见的LDPC码一般分为两类,一类是随机LDPC码,一般由随机化方法构造;另一类是准循环LDPC码,一般由半随机方 法或者基于代数的结构化...
  • 来个例子吧,比如来了一个数据包,目的地址是192.168.10.23,来看一下怎么查找,将该地址写成二进制: 根据trie树根,得知pos=0/bits=3,因此知道应该去往根CheckNode的第7个孩子,于是到达CheckNode2,类似的,我们...
  • Merkle Tree(默克尔算法解析

    万次阅读 多人点赞 2017-01-20 17:52:14
    Merkle Tree,通常也被称作Hash Tree,顾名思义,就是存储hash值的一棵。Merkle的叶子是数据块(例如,文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。[1]1、HashHash是一个把任意长度的...
  • 遗传算法详解 附python代码实现

    千次阅读 2021-12-02 11:03:02
    遗传算法是用于解决最优化问题的一种搜索算法。从名字来看,遗传算法借用了生物学里达尔文的进化理论:“适者生存,不适者淘汰”,将该理论以算法的形式表现出来就是遗传算法的过程。 主要过程 初始化一个种群,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,446
精华内容 7,778
热门标签
关键字:

二进制树搜索算法的实现步骤