Shulou(Shulou.com)06/03 Report--

Recently, in reviewing the data structure, I encountered a problem when I saw BST, that is, when deleting or adding nodes in the tree, it is required to ensure a high balance of rows in the tree, that is, to make BST an AVL.

Later, I read a lot of materials, saying that LL, RR, LR, RL and so on, did not understand. Later, after studying with my classmates, I found a feature, that is, offending node has a size relationship with the two nearest points on its backtracking path.

As shown above, an empty BST tree, insert 16 into the tree, because it is an empty tree, then 16 as the root node. Enter 3 after that. 3 is smaller than 16, put it on the left side of 16 as the left child node, and then enter 7 focus 7 smaller than 16, go to one side of the left subtree, and then compare 7 with 3, 7 to 3, go to the right subtree of 3. But as shown in the figure above, this is not an AVL tree, because the height of the left subtree of 16 is 2, the height of the right subtree is 0, and the absolute value of the height difference between left and right is 2, which exceeds the condition of AVL: the absolute difference between left and right height.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.