二叉排序树与平衡二叉排序树基本操作的实现 文本文档（Two fork sorting tree and balance two fork sort tree basic operation of the realization of text uments）

1、二叉排序树与平衡二叉排序树根本操作的实现 文本文档Two fork sorting tree and balance two fork sort tree basic operation of the realization of text documentsCourse design task book for undergraduate students of Panzhihua UniversityTitle two fork sorting tree and the realization of balanced two fork tree1, the purpose of curri

2、culum designIt can help students further understand and master the logical structure, storage structure and operation implementation algorithms of various abstract data types in the classroom, as well as how they are used in programs.Make students master the basic content and design methods of softw

3、are design, and cultivate students' ability to standardize software design.3) enable students to master the use of various computer materials and reference materials, improve the basic ability of students to program design.2, the content and requirements of curriculum design (including raw data,

4、 technical requirements, job requirements, etc.)(1) (1) take the carriage return ('n') as the input end flag, enter the sequence L, and generate a two fork sorting tree T;(2) do the inorder traversal of the two fork sort tree T, and output the result;(3) calculate the two fork sort tree T fi

5、nd the average search length of success, the output results;(4) input element x, find the two fork sorting tree T, if there is a node containing x, then delete the node, and make the order traversal (execution operation 2); otherwise the output information "NO x""(5) with the sequence

6、 of L, the two generation balanced binary sort tree BT: when inserting new elements, found that two of the current two binary sort tree binary sort tree BT is not balanced, then two binary sort tree it into a new balance BT;(6) calculate the average lookup length of the balanced two fork sorting tre

7、e BT, and output the result.3. Main references1 Liu Dayou, "data structure" (C language version), higher education press2 Yan Yumin et al., data structure (C Language Edition), Tsinghua University press3 William Ford, William Topp, "Data Structure with C+", Tsinghua University pr

8、ess4 Su Shihua et al. Data structure course design, Mechanical Industry Press4, curriculum design work scheduleFirst days to complete the program design and program block diagramSecond, third days to write program codeFourth day program debugging analysis and resultsFifth day course design report an

9、d summaryTeacher's (signature) date, month, dayTeaching and research section opinion:Specific dateStudent (signature):Time to accept tasks: month, month, dayNote: the task book is filled in by the tutor.Curriculum design (Thesis) Instructor achievement assessment formTitle two fork sorting tree

10、and balanced two fork tree implementationScoring items, score, score, evaluation connotationworkperformance20% 01 learning attitude 6 abide by the discipline, work hard, have a good scientific work attitude.02 scientific practice and research 7. Obtain materials related to curriculum design through

11、experiments, experiments, consulting literature, in-depth production practice and other channels.03 the workload of the project is 7. The tasks are fulfilled on schedule and the workload is full.abilitylevel35% 04 the ability to use knowledge comprehensively, 10 can use the knowledge and skills to f

12、ind and solve practical problems, can correctly deal with experimental data, can carry on the theoretical analysis of the subject, and draw valuable conclusions.05 the ability to apply literature 5 can independently access to the relevant literature and engage in other research; can put forward and

13、better discuss the implementation of the program; have the ability to collect, process all kinds of information and acquire new knowledge.06 design (Experiment) ability, the design ability of the program 5 can correctly design the experimental scheme, independent installation, debugging, operation a

14、nd other experimental work, the data is correct and reliable; research ideas clear and complete.07 computing and computer application ability 5, has strong data processing and processing ability; can use computer for data collection, processing, processing and auxiliary design, etc.08 the ability to

15、 analyze or calculate the experimental results (comprehensive analysis ability, technical and economic analysis ability) 10 has strong ability of data collection, analysis, processing and synthesis.Achievementsquality45%, 09 illustrations (or drawings) quality, length, design (Thesis) standardizatio

16、n degree of 5 in line with the relevant professional specifications or requirements; standardization conforms to the requirements of the fifth requirements of this document.10 the quality of the design manual (Thesis) 30, the summary is concise and complete, and has the view; the argument is correct

17、, the discussion is sufficient, the conclusion is rigorous and reasonable; the experiment is correct, the analysis and processing science.11 innovation 10, to improve or break through previous work, or have unique views.achievementAdvisor commentsTeacher's signature: day and monthAbstract and ke

18、y wordsThe data in this program uses "tree structure" as its data structure. Specifically, the "two fork sorting tree" is adopted".Two binary sort tree (also called two binary search tree): (1) if the left subtree is not empty, then the left sub tree of all nodes was less th

19、an the root node of its value; (2) if the right subtree is not empty, then the right subtree of all nodes are greater than the value of its root node; (3) the left and right subtrees are two binary sort tree.Two fork balance tree: if the tree is not empty, (1) the subtree is balanced two fork tree;

20、(2) the absolute value of the difference between the left and right subtree is not more than 1.This experiment is the use of two binary sort tree and the balanced binary tree to achieve the following goals: two (1) to enter ('n') for the input end of the symbol, the input sequence L, generat

21、e a binary sort tree T (two; 2) in the traversal of two binary sort tree T output; (3) calculation of two staggered sequence tree average search length T to find success, output results;(4) input elements x, find two binary sort tree T, if the presence of X node, the node is deleted, and in order tr

22、aversal (operation 2); otherwise, the output information of "NO x" (5) with the sequence of L, the two generation balanced binary sort tree when insert elements after BT: two, the current two binary sort tree binary sort tree BT is not balanced, then convert it into a new balance two binar

23、y sort tree BT; (6) the average search length calculation balance two binary sort tree BT, output results.Keywords: sequence L, node, two fork sorting tree, balanced two fork treeCatalogAbstract. Three1 introduction. Five1.1 the purpose of curriculum design. Five1.2. Related knowledge. FiveStorage s

24、tructure of 1.2.1 one bit array. Five1.2.2 establishes two fork sorting tree. FiveTwo traversing tree in 1.2.3. FiveAverage search length of 1.2.4. Six1.2.5 average two fork tree (AVL tree). Six1.2.6 equilibrium factor. SevenAdjustment method of 1.2.7 balanced two fork tree. Seven2 scheme design. Ei

25、ght2.1 module function. Eight3 algorithm design. EightFlow chart of 3.1 algorithm. Eight4 detailed design. TenFour1 main program. Ten4.2 define two fork tree structure. Eleven4.3 establish two fork tree. ElevenSearch of 4.3.1 two fork sort tree. ElevenInsertion of 4.3.2 two fork sort tree. Eleven4.4

26、 inorder traversal. Twelve4.5 average search length. Twelve4.6 delete nodes. Twelve4.7 judge the balance of two fork tree. Thirteen5 debugging analysis. FourteenAnalysis of 5.1 time complexity. Fourteen5.2 running results. Fourteen5.3 result analysis. Fifteen6 curriculum design summary. SixteenRefer

27、ences. Seventeen1 Introduction1.1 the purpose of curriculum design(1) enable students to further understand and master the logical structure, storage structure and operation implementation algorithms of various abstract data types in class, and their usage in the program.(2) enable students to maste

28、r the basic content and design methods of software design, and cultivate students' ability to standardize software design.(3) enable students to master the use of various computer materials and reference materials, improve the basic ability of students to program design.1.2. Related knowledgeSto

29、rage structure of 1.2.1 one-dimensional arrayThe establishment of the two insertion sort tree, first with a one-dimensional array to record the data read, then inserted into the side to find the corresponding data in all two binary tree corresponding to the location, the empty tree filled with "

30、;0".1.2.2 establishes two fork sorting treeThe two fork sorting tree is a dynamic tree table. Its characteristics are: tree structure is usually not generated once, but in the search process, when the tree does not exist when the keyword is equal to the given value of the node, then insert. The

31、 newly inserted node must be a newly added leaf node, and it is the left child or right child node of the last node accessed on the lookup path when it is unsuccessful.Insertion algorithm:First, the lookup algorithm is implemented to find the father node of the inserted node;The left and right son o

32、f the father whose node is inserted. Insert the inserted node as the leaf node;If the two tree is empty, then the first and only child is the root node.Note: the newly inserted node is always a leaf node.The framework of traversing the two fork tree algorithm is:If the two fork tree is empty, then e

33、mpty operation;Otherwise (1) inorder to traverse the left subtree (L);(2) access root node (V);(3) inorder traversing the right subtree (R).In order traversal binary tree two using a recursive function, a visit to the left sub tree 2I, then visit the root node of I, finally access the right subtree

34、2i+1. first left again at the back end, until all nodes have been visited.When calculating the average search length of two fork sorting tree, we use the recursive method similar to the order traversal, and use s to record the total search length,J records the search length of each node, and the ini

35、tial value of S is 0. Finally, the total search length s is obtained by the way of accumulation. The average search length is equal to s/i (I is the total number of nodes in the tree).Hypothesis (n>=1) sequence with n keyword in the I keyword is less than the first keyword, n-i-1 keyword is great

36、er than the first keyword, the structure and the two binary sort tree in search is equal to the probability of n records under the condition, the average search length:ASL (n, I) =1+i* (P (I) +1) + (n-i-1) (P (n-i-1) +1)/nThe P (I) the average search length of two binary sort tree with I nodes, P (I

37、) +1 to search the left subtree in each keyword used when compared to the average number of P (n-i-1) +1 to find the right subtree in each keyword used when compared to the average number of. Also assume that the arrangement of the N keywords in the table is "random", that is, any keyword

38、in the sequence will be first, or second,. The probability of the upper form from I equals 0 to n-1 is the same as that of the first n. It will eventually be deduced:When n>=2, ASL (n) <=2 (1 + 1/n) ln (n)Thus, in the random case, the average search length and log (n) of the two fork sorting t

39、ree are equal orders of magnitude.In addition, the decision tree is not unique for a two fork sorting tree with n nodes. For a table with the same set of nodes, the shape and depth of the two fork sorting tree may be different due to the different order of node insertion.The average length of search

40、 and search in the two binary sort tree and binary tree of two forms: in the worst case, two binary sort tree is formed by an ordered list of N nodes are inserted, the two binary sort tree into a single tree depth n tree, the average search length and in order to find a single list on the same, also

41、 is (n+1) /2. In the best case, two binary sort tree in the process of generation, the shape of the tree is well balanced, the final decision tree is a tree shape with two points to find the similarity of two binary sort tree, the average length of it is about lgn. (3) the time complexity of inserti

42、on, deletion and lookup algorithms is O (LGN).1.2.5 balanced two fork tree (AVL tree)Binary Tree (Balanced) means that the height of the left and right subtrees of any node in the tree is approximately the same. (2) the height of the left and right subtrees of each node is the same (such as two tree

43、s), then the two branches are completely balanced. Generally, as long as the height of the two tree is O (1gn), it can be considered as a balanced one. The balanced two fork sorting tree is a balanced two fork tree satisfying the BST property. (4) the absolute difference between the height of the le

44、ft and right subtrees of any node in the AVL tree is not more than 1. In the worst case, the height of the AVL tree of the N node is about 1.44lgn. The fully balanced two fork tree height is about LGN, and the AVL tree is the closest to the optimum.1.2.6 equilibrium factorThe two fork tree took the

45、right subtree left sub tree depth minus one node depth is called the balance factor of the node, all nodes set the balance factor of two tree in only 0, 1 and -1.Two balanced binary sort tree in absolute value is equal to the equilibrium factor begins to adjust to the absolute value of 1 or 0 in 2,

46、the absolute value of balance factor is 2, two binary sort tree will appear four different situations of the tree, so the need to separately discuss to reduce the balance factor.Adjustment method of 1.2.7 balanced two fork treeThe balance of the two fork tree is in the process of constructing the tw

47、o binary sort tree, when inserting a new node, first check whether due to insert the new node and destroy the balance of the two binary sort tree if, find the minimum balance is not in the subtree, keep two binary sort tree characteristics under the premise. Adjust the minimum unbalanced links betwe

48、en every node in the subtree, the corresponding rotation, make it become the new balance tree. The concrete steps are as follows:(1) insert a new node every time,From the start node to calculate each node balance factor, namely the balance factor calculation node ancestor node, if the absolute value

49、 of the balance factor of the node the ancestor was less than 1, the balance of two tree without loss of balance, to insert nodes;(2) if the absolute value of the balance factor of an ancestor node of the inserted node is greater than 1, the root node of the least unbalanced subtree is found;(3) det

50、ermine the relationship between the newly inserted node and the root node of the minimum unbalanced subtree, and determine which type is the adjustment;(4) if it is LL or RR, only using a rotating pole principle, in the rotation process, if there is a conflict, using the rotating priority adjustment

51、 conflict; if it is LR or LR, for application principle of rotating two pole, the first time the minimum unbalanced root knot point tree first don't move, adjust the insertion node subtree, second re adjust the minimum unbalanced subtrees, in the rotation process, if there is a conflict, using the rotating priority principle of conflict adjustment;(5) the balance factor of each node to calculate the adjusted balance of the two binary tree, test whether the balance factor because of the rotation and damage to other nodes, whether the bala