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

Today, I will talk to you about the meaning of the AVL tree in the data structure, which may not be well understood by many people. in order to make you understand better, the editor has summarized the following content for you. I hope you can get something according to this article.

1. Brief introduction of AVL tree

The AVL tree is essentially a binary search tree, also known as a highly balanced binary search tree. It can keep the height balance of the binary tree, reduce the height of the binary tree as much as possible, and reduce the average search length of the tree. For the introduction and implementation of binary search tree, you can check my last blog.

2. The characteristics of AVL tree.

1) itself is first of all a binary search tree.

2) with equilibrium condition: the absolute value (balance factor) of the height difference between the left and right subtrees of each node is at most 1.

3) every left and right subtree in the tree is an AVL tree.

4) each node has a balance factor, and the balance factor of any node is-1pr 0pl 1.

Note: balance factor of node = right subtree height-left subtree height

3. The efficiency of AVL tree

An AVL tree has N nodes, its height can be maintained in lgN, and the time complexity of insert / delete / search is also lgN.

The AVL tree is a whole order of magnitude more complex than the binary search tree-it's not hard to understand how it works, but it's a bit of a pain in the neck to implement it in code. Let's take a look at the interface implemented by the AVL tree, which implements the node through the trigeminal chain.

Templatestruct AVLTreeNode// trigeminal chain {AVLTreeNode* _ left; AVLTreeNode* _ right; AVLTreeNode* _ parent; K _ key; V _ value; int _ bf / / the height difference between the right subtree and the left subtree AVLTreeNode (const K & key = K (), const V & value = V ()) / / plus K () and V (). Default construction: _ left (NULL), _ right (NULL), _ parent (NULL), _ key (key), _ value (value), _ bf (0) {}; templateclass AVLTree {typedef AVLTreeNode Node Public: AVLTree (): _ root (NULL) {} void Insert (const K & key, const V & value); Node* Find (const K & key); int Height (); bool IsBalance (); void PrintAVLTree (); private: Node* _ Find (Node* root, const K& key); void _ RotateL (Node*& parent); void _ RotateR (Node*& parent); void _ RotateLR (Node*& parent); void _ RotateRL (Node*& parent); int _ Height (Node* root); Node* root _ Node* root (bool) Void _ PrintAVLTree (Node* root); protected: Node* _ root;}

The following is an element analysis of the insertion:

1) to determine whether the tree is empty, create a new root node.

2) find out whether the inserted key exists, exit the function if it exists, and execute 3 if it doesn't exist.

3) find the location where the key is inserted, and then insert the node cur.

4) update the balance factor: update the balance factor from the cur to its parent node, and rotate to adjust the balance factor if the balance factor of the node does not satisfy the AVL tree.

Templatevoid AVLTree::Insert (const K & key, const V & value) {if (_ root = = NULL) {_ root = new Node (key, value); return;} if (Find (key)) / / exists key {return;} Node* prev = NULL; Node* cur = _ root; while (cur) / / insert key location cur {if (key)

_ key) {prev = cur; cur = cur- > _ left;} else if (key > cur- > _ key) {prev = cur; cur = cur- > _ right;}} cur = new Node (key, value); / / insert node cur if (prev- > _ key > key) {prev- > _ left = cur; cur- > _ parent = prev;} else if (prev- > _ key)

_ right = cur; cur- > _ parent = prev;} / / prev is the last node of cur, that is, cur is the parent node of prev prev = cur; cur = prev- > _ parent; while (cur) {/ / update balance factor: update the balance factor cur- > _ bf = _ Height (cur- > _ right)-_ Height (cur- > _ left) upward from the inserted cur If (cur- > _ bf! =-1 & & cur- > _ bf! = 1 & & cur- > _ bf! = 0) / / does not satisfy the node of the AVL tree. When the balance factor {/ / balance factor is 2, there must be a right subtree. When the balance factor is-2, there must be a left subtree / / left single spin: 2 1 (balance factor) if (cur- > _ bf = = 2 & & cur- > _ right- > _ bf = = 1) {_ RotateL (cur); / / reference transfer} / / right spin:-2-1 else if (cur- > _ bf = =-2 & cur- > _ left- > _ bf = =-1) {_ RotateR (cur) } / / rotate:-2 1 else if (cur- > _ bf = =-2 & & cur- > _ left- > _ bf = = 1) {_ RotateLR (cur);} / / right and left: 2-1 else if (cur- > _ bf = 2 & & cur- > _ right- > _ bf = =-1) {_ RotateRL (cur);}} prev = cur; cur = cur- > _ parent;}}

The balance factor is adjusted by rotation, which can be divided into four situations:

(1) left single rotation: the balance factor of cur is 2 and the balance factor of right is 1.

(2) right single spin: the equilibrium factor of cur is-2, and the balance factor of left is-1.

(3) left and right rotation: the balance factor of cur is-2 and the balance factor of left is 1.

(4) right and left rotation: the balance factor of cur is-2, and the balance factor of right is-1.

Left-right rotation and right-left rotation can be done by calling left and right single rotation. Note that the balance factor is reset at the end.

If you are not very clear, you can draw your own drawings and analyze them.

Left single spin:

Templatevoid AVLTree::_RotateL (Node*& parent) {Node* subR = parent- > _ right; Node* subRL = subR- > _ left; parent- > _ right = subRL;//1 subR- > _ parent = parent- > _ parent;//1 subR- > _ left = parent;//2 parent- > _ parent = subR;//2 if (subRL) / / Note is not empty, link subRL- > _ parent = parent; parent- > _ bf = subR- > _ bf = 0 / / if the link between the parent node of subR and subR if (subR- > _ parent = = NULL) / / is empty, parent is the root node, change the root node _ root = subR; else// is not empty, link {if (subR- > _ parent- > _ key > subR- > _ key) subR- > _ parent- > _ left = subR; else subR- > _ parent- > _ right = subR;} parent = subR;}

Right single spin:

Templatevoid AVLTree::_RotateR (Node*& parent) {Node* subL = parent- > _ left; Node* subLR = subL- > _ right;// cannot change the order parent- > _ left = subL- > _ right;//1 subL- > _ parent = parent- > _ parent;//1 subL- > _ right = parent;//2 parent- > _ parent = subL;//2 if (subLR) / / Note is not empty, link subLR- > _ parent = parent Parent- > _ bf = subL- > _ bf = 0; / / if the link between the parent node of subL and subL (subL- > _ parent = = NULL) / / is empty, parent is the root node, change the root node _ root = subL; else// is not empty, link {if (subL- > _ parent- > _ key > subL- > _ key) subL- > _ parent- > _ left = subL; else subL- > _ parent- > _ right = subL;} parent = subL;}

Rotate left and right:

Templatevoid AVLTree::_RotateLR (Node*& parent) {Node* pNode = parent;// needs to redefine parent. After rotation, the parent direction changes Node* subLNode = pNode- > _ left; Node* subLRNode = subLNode- > _ right; _ RotateL (parent- > _ left); _ RotateR (parent) / / in single rotation, the balance factor of parent and subL is 0, and errors will be made in left-right rotation and right-left rotation, so there are three cases of resetting the balance factor / / subLRNode: 0,-1, 1. The balance factor of subLRNode affects the balance factor if (subLRNode- > _ bf = = 1) {pNode- > _ bf = 1; subLNode- > _ bf = 0;} else if (subLRNode- > _ bf = =-1) {pNode- > _ bf = 0; subLNode- > _ bf =-1;} else {parent- > _ bf = 0; subLNode- > _ bf = 0;}

Rotate right and left:

Templatevoid AVLTree::_RotateRL (Node*& parent) {Node* pNode = parent; Node* subRNode = pNode- > _ right; Node* subRLNode = subRNode- > _ left; _ RotateR (parent- > _ right); _ RotateL (parent); if (subRLNode- > _ bf = = 1) {pNode- > _ bf =-1; subRNode- > _ bf = 0;} else if (subRLNode- > _ bf = =-1) {pNode- > _ bf = 0; subRNode- > _ bf = 1 } else {pNode- > _ bf = 0; subRNode- > _ bf = 0;}}

Test cases are as follows:

Void AVLTreeTest () {AVLTree avlt; / / int arr [10] = {16, 3, 7, 11, 9, 26, 18, 14, 15, 23}; int arr [10] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14}; for (int I = 0; I < 10; + + I) {avlt.Insert (arr [I], I); avlt.PrintAVLTree ();} cout

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.