Tree of Java data structures and algorithms (power node Java College)

Why use trees:

The tree combines the advantages of the two data structures: one is the ordered array, and the speed of the tree in finding data items is as fast as that in the ordered array; The other is the linked list. The speed of inserting data and deleting data items in the tree is the same as that in the linked list. In that case, we should study hard (the main discussion is the binary search tree in the binary tree, that is, the key value of the left child node of a node is less than this node, and the key value of the right child node is greater than this node)

Thinking before design:

Tree - > element (node)

Insert data:

Traverse the tree:

Find a node:

Maximum and minimum values of keywords in the lookup tree:

Maximum: keep looking for the right child node

Minimum: constantly looking for the left child node

Delete a node:

reflection:

1). Find the node to delete first:

2). After analysis, there are three cases: leaf node, node with one node and node with two nodes

A). If you are deleting a leaf node, you can delete it directly

B). If the deleted node has one node, there are two cases: the deleted node has only one left child node or only one right child node

c). If the deleted node has two nodes:

This situation is more complex. You need to find a node to replace the node to be deleted. What node should this node be?

According to the book, the most appropriate node is the successor node, that is, the node with the second highest key value than the node to be deleted is its successor node.

To put it simply, the successor node is the minimum value in the node set that is larger than the key value of the node to be deleted.

Taking the above example, when the successor node of 40 is 74 and the successor node of 10 is 13 and 19, 26

The following is the code for finding successor nodes:

After finding the successor node, we will discuss how to use the successor node to replace the deleted node

a) If the successor node is just the right child node of the node to be deleted (at this time, you can know that the right child node has no left child node. If so, the right child node should not be the successor node)

b) If the successor node is the left descendant of the right child node of the node to be deleted:

Note: the first and second steps are completed in the final if statement of the getsuccess () method

The following is the code of the deleted node with multiple nodes:

Based on the above, the code of delete () method is given:

Further consideration:

Deletion is so complicated, is deletion necessary? We can define a flag for each node. This flag is used to record whether the node has been deleted. When displaying the tree, we first judge whether the node has been deleted. If not, it will be displayed.

As a result, nodes are not deleted, which obviously evades responsibility. This is also a good method when there are not so many deletion operations in the tree, for example:

The files of resigned employees shall be permanently saved in the employee's records.

The above is the tree of Java data structures and algorithms introduced by Xiaobian to you (organized by the power node Java College). I hope it will be helpful to you. If you have any questions, please leave me a message and Xiaobian will reply to you in time. Thank you very much for your support for the programming tips website!