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

This article mainly introduces "how to achieve the AVL tree on C++". In daily operation, I believe many people have doubts about how to achieve the AVL tree in C++. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the doubts about "how to achieve the AVL tree in C++". Next, please follow the editor to study!

The concept of AVL Tree

Although the binary search tree can shorten the search efficiency, if the data is ordered or close to the ordered binary search tree, it will be degenerated into a single-branch tree, and the search element is equivalent to searching for elements in the sequential table, which is inefficient. Therefore, two Russian mathematicians G.M.Adelson-Velskii and E.M.Landis invented a method to solve the above problem in 1962: when a new node is inserted into the binary search tree, if the absolute value of the difference between the left and right subtree height of each node is not more than 1 (the nodes in the tree need to be adjusted), the height of the tree can be reduced, thus reducing the average search length.

An AVL tree is either an empty tree or a binary search tree with the following properties:

Its left and right subtrees are all AVL trees.

The absolute value of the difference between the height of the left and right subtrees (balance factor for short) does not exceed 1 (- 1-0-1)

The calculation of the balance factor is the result of the difference between the height of the right subtree and the height of the left subtree.

If a binary search tree is highly balanced, it is an AVL tree. If it has n nodes, its height can be maintained at O (log N), and the search time complexity is O (log N).

Definition of AVL Tree Node

Templatestruct AVLTreeNode {AVLTreeNode* _ left; / / left child AVLTreeNode* _ right; / / right child AVLTreeNode* _ parent; / / father node pair _ Kv; / / key value int _ bf / / balance factor / / Constructor AVLTreeNode (const pair& Kv): _ left (nullptr), _ right (nullptr), _ parent (nullptr), _ Kv (Kv), _ bf (0) {}}

Definition of AVL tree

Templateclass AVLTree {typedef AVLTreeNode Node;public: AVLTree (): _ root (nullptr) {} private: Node* _ root;}; insertion of AVL tree

The AVL tree introduces the balance factor based on the binary search tree, so the AVL tree can also be regarded as a binary search tree. So the insertion of AVL tree

The process can be divided into two steps:

Insert a new node according to the binary search tree

Compared with the root node, insert it to the right subtree if it is larger than the root, and to the left subtree if it is smaller than the root, until you get to the right position. Because this is a trigeminal chain, you need to deal with the relationship between nodes.

Bool Insert (const pair & kv) {if (! _ root) _ root = new Node (kv); / / initial root node Node* cur = _ root; Node* parent = _ root; while (cur) {K key = cur- > _ Kv.first If (key > kv.first) / / is lower than the key value of the root node, {parent = cur; cur = cur- > _ left;} else if (key)

< kv.first)//比根结点的key值大， { parent = cur; cur = cur->

_ right;} else {return false; / / insert failed}} / / start inserting cur = new Node (kv) Node* newNode = cur; if (parent- > _ Kv.first > newNode- > _ Kv.first) / / if the key value of the newly inserted node is smaller than the root node, it is inserted into the left subtree {parent- > _ left = newNode; newNode- > _ parent = parent. } else / / if the key value of the newly inserted node is larger than the root node, it will be inserted into the right subtree {parent- > _ right = newNode; newNode- > _ parent = parent;}}.

Adjust the balance factor of the node

When the height of the left and right subtrees changes, then the balance factors of all nodes on the father and ancestor path need to be adjusted.

/ / update the balance factor of all nodes in the ancestral path / * summarize five situations: 1. The new node appears on the left side of the parent node, and the balance factor minus 2. The new node appears on the right side of the parent node. If the balance factor is added 3, the father's balance factor is 0, the father's balance factor is 1 or-1, continue to adjust 5, If the balance factor of the parent node is 2 or-2, then rotate * / while (parent) {if (parent- > _ left = = cur) parent- > _ bf-- / / 1, if (parent- > _ right = = cur) parent++; / / 2, if (parent- > _ bf = = 0) break; / / 3, if (parent- > _ bf = =-1 | | parent- > _ bf = = 1) / / 4, {cur = parent Parent = parent- > _ parent } if (parent- > _ bf = =-2 | | parent- > _ bf = = 2) / / 5, {/ / rotate if (parent- > _ bf = =-2) {if (cur- > _ bf = =-1) RotateR (parent) / / left high, right single spin else RotateLR (parent); / / left and right double spin} else / / right parent- > _ bf = = 2 {if (cur- > _ bf = = 1) RotateL (parent) / / right high left single rotation else RotateRL (parent); / / right and left double rotation} break;}} four rotations of AVL trees

The principle of rotation is to follow the rules of the search tree and try to balance both sides.

If a new node is inserted into a balanced AVL tree, it may cause imbalance. At this time, the structure of the tree must be adjusted to balance it. Depending on where the node is inserted, the rotation of the AVL tree can be divided into four types:

Right-hand single rotation

The new node is inserted into the left side of the higher left subtree-left left: right single spin

No matter what kind of single spin it is, you have to consider two situations:

1. Local rotation. If parent is not the _ root node of the tree, then the relationship between subL and root node needs to be adjusted.

2. Rotate independently, and parent is the _ root node of the tree, so subL is the rotated root node.

3. SubLR may be null

/ / right-handed void RotateR (Node* parent) {Node* subL = parent- > _ left; Node* subLR = subL- > _ right; parent- > _ left = subLR; if (subLR) subLR- > _ parent = parent; / / prevent subLR from being nullptr subL- > _ right = parent; Node* parent_parent = parent- > _ parent; / / pointer backup parent- > _ parent = subL If (_ root = = parent) / / if parent is the root of the tree {_ root = subL; / / subL instead of parent_ root- > _ parent = nullptr;} else / / if parent is not the root of the tree {if (parent_parent- > _ left = = parent) parent- > _ left = subL Else parent_parent- > _ right = subL; subL- > _ parent = parent_parent; / / subL to be the child of parent_parent} / / adjust the balance factor subL- > _ bf = parent- > _ bf = 0;} left-handed

The new node is inserted into the right side of the higher right subtree-right right: left single spin

It's almost the same as right-hand single rotation.

1. Local rotation. If parent is not the _ root node of the tree, then the relationship between subL and root node needs to be adjusted.

2. Rotate independently, and parent is the _ root node of the tree, so subL is the rotated root node.

3. SubRL may be null

/ / left-handed void RotateL (Node* parent) {Node* subR = parent- > _ right; Node* subRL = subR- > _ left; parent- > _ right = subRL; if (subRL) subRL- > _ parent = parent; subR- > _ left = parent; Node* parent_parent = parent- > _ parent; parent- > _ parent = subR If (_ root = = parent) {_ root = subR; _ root- > _ parent = nullptr;} else {if (parent_parent- > _ left = = parent) parent_parent- > _ left = subR; else parent_parent- > _ right = subR SubR- > _ parent = parent_parent;} subR- > _ bf = parent- > _ bf = 0;} double spin left and right

The new node is inserted into the right side of the higher left subtree-left and right: first left and then right

1. Adding new nodes in b or c will affect the height of the left and right subtrees, thus causing double rotation.

H > 0 case 1:

H > 0, case 2:

H = = 0 case 3:

/ / rotate void RotateLR (Node* parent) {Node* subL = parent- > _ left; Node* subLR = subL- > _ right; int bf = subLR- > _ bf; RotateL (parent- > _ left); RotateR (parent) If (bf = =-1) / / h > 0. The new node is b {parent- > _ bf = 1; subLR- > _ bf = 0; subL- > _ bf = 0 } else if (bf = = 1) / / h > 0, the new node is c {subL- > _ bf =-1; subLR- > _ bf = 0; parent- > _ bf = 0 } else if (bf = = 0) / / h = 0 {parent- > _ bf = 0; subLR- > _ bf = 0; subL- > _ bf = 0;}} right and left double rotation

The situation of right and left double rotation is basically similar to that of left and right double rotation, so we will not enumerate many cases here.

The new node inserts the left-right left of the higher right subtree: first right single rotation and then left single rotation

/ / right and left rotate void RotateRL (Node* parent) {Node* subR = parent- > _ right; Node* subRL = subR- > _ left; int bf = subRL- > _ bf; RotateR (parent- > _ right); RotateL (parent) If (bf = =-1) / / h > 0. The new node is b {parent- > _ bf = 0; subR- > _ bf = 1; subRL- > _ bf = 0 } else if (bf = = 1) / / h > 0, the new node is c {parent- > _ bf =-1; subR- > _ bf = 0; subRL- > _ bf = 0 } else if (bf = = 0) / / h = 0 {subR- > _ bf = 0; subRL- > _ bf = 0; parent- > _ bf = 0 }} find Node* Find (const K & key) {Node* cur = _ root; while (cur) {if (key > cur- > _ Kv.first) cur = cur- > _ right; / / left subtree else if (key)

< cur->

_ Kv.first) cur = cur- > _ left; / / right subtree else return cur;}} other interfaces

Judge whether it is a balanced binary tree

Int height (Node* root) / / height {return! root? 0: max (height (root- > _ left), height (root- > _ right)) + 1;} void _ Inorder (Node* root) / / medium order traversal {if (! root) return; _ Inorder (root- > _ left) Printf ("% d:% d\ n", root- > _ Kv.first, root- > _ Kv.second); _ Inorder (root- > _ right);} / / determine whether it is a balanced binary tree bool IsAVLTree () {return _ IsAVLTree (_ root);} bool _ IsAVLTree (Node* root) {if (! root) return true; int left = height (root- > _ left) Int right = height (root- > _ right); / / check balance factor if (right-left! = root- > _ bf) {printf ("wrong balance factor% d:% d\ n", root- > _ Kv.first, root- > _ Kv.second); return false;} return (abs (right-left)

< 2) && _IsAVLTree(root->

_ left) & & _ IsAVLTree (root- > _ right);} destructor / / destructor ~ AVLTree () {Destroy (_ root); _ root = nullptr;} void Destroy (Node * root) / / subsequent destruction node {if (! root) return; Destroy (root- > _ left); Destroy (root- > _ right); delete root } copy construction Node* copy (Node* cp) {if (! cp) return nullptr; Node* newnode = new Node (cp- > _ Kv); newnode- > _ left = copy (cp- > _ left); newnode- > _ right = copy (cp- > _ right); return newnode;} / / copy construction AVLTree (const AVLTree& job) {if (& job! = this) _ root = copy (job._root) } copy assignment void operator= (AVLTree tmp) {if (& tmp! = this) swap (tmp._root, this- > _ root);}

Reload operator []

V & operator [] (const K & key) {return (Insert (make_pair (key, V () .first)-> _ Kv.second;}

The complete implementation of the AVL tree code blogger has been put on git.

At this point, the study of "how to realize the AVL tree by C++" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.