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

This article is to share with you the content of the example analysis of C language balanced binary tree. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Balanced binary tree (Balanced Binary Tree) is also called AVL tree (different from AVL algorithm), and it has the following properties: it is an empty tree or the absolute value of the height difference between its left and right subtrees is not more than 1, and the left and right subtrees are both balanced binary trees. This scheme well solves the problem that the binary search tree is reduced to a linked list, and the time complexity of inserting, searching and deleting is maintained at O (logN) in the best and worst cases. However, frequent rotation will cost inserts and deletes about O (logN) time, but the time is much more stable than the binary search tree.

Most operations of a balanced binary tree are similar to a binary search tree, except that the balance of the balanced binary tree may be changed during insertion and deletion, and only the balance of the nodes on the path from those insertion points to the root node may be changed. because only the subtrees of these nodes may change.

The case of an imbalance in a balanced binary tree:

The node that needs to be rebalanced is called α. Because any two nodes have at most two sons, when the height is unbalanced, the height difference between the two subtrees of the α node is 2. 5%. It is easy to see that this imbalance may occur in the following four situations:

1. Insert the left subtree of the left son of α

two。 Insert the right subtree of the left son of α

3. Insert the left subtree of the right son of α

4. Insert the right subtree of the right son of α

Case 1 and case 4 are about the mirror symmetry of α, and case 2 and case 3 are also about the mirror symmetry of α, so there are only two cases in theory, but there are still four cases from a programming point of view.

The first situation is that the insertion occurs on the "outside" (left, left or right), which can be adjusted by a single rotation; the second case is that the insertion occurs in the "inside" situation (left or right), which is more complex and needs to be adjusted by double rotation.

Adjustment measures: first, single rotation

The left subtree K1 is two layers deeper than the right subtree z, and the deeper one in the K1 subtree is the left subtree x of K1, so it belongs to the left-left case.

In order to restore balance, we move x up one level and z down one level, but at this time we have actually exceeded the property requirements of the AVL tree. To do this, the nodes are rearranged to form an equivalent tree. In order to restore the balance of the tree, we turn K2 into the root node of this tree. Because K2 is greater than K1, K2 is placed on the right subtree of K1, while the Y of the right subtree of K1 is greater than K1 and less than K2, so Y is placed on the left subtree of K2, which satisfies not only the properties of binary search tree, but also the property of balanced binary tree.

This situation is called single rotation.

2. Double rotation

For the left and right and left and right cases, a single rotation can not solve the problem, it has to go through two rotations.

For the above picture, in order to restore the balance of the tree, we need to take two steps. The first step is to take K1 as the root and make a right-right rotation. After the rotation, it becomes a left-left situation, so the second step is to make another left-left rotation. Finally, we get a balanced binary tree with K2 as the root.

Delete operation of AVL tree:

Like the insert operation, it is possible to break the balance when deleting the node, which requires us to adjust the balance when deleting it.

Deletions can be divided into the following situations:

First of all, search the entire binary tree for the node to be deleted, and do the following if it is not found and returned directly without processing:

1. The node to be deleted is the current root node T.

If the left and right subtrees are not empty. Delete is performed in a subtree that is higher in height.

There are two situations:

(1) the height of the left subtree is greater than that of the right subtree, assign the largest element in the left subtree to the current root node, and then delete the node with the largest element value in the left subtree.

(1) the height of the left subtree is less than that of the right subtree, assign the smallest element in the right subtree to the current root node, and then delete the node with the lowest element value in the right subtree.

If one of the left and right subtrees is empty, simply replace the current root node with that non-empty subtree or NULL.

2. The value of the node element to be deleted is less than the T value of the current root node, so delete it in the left subtree.

Recursive call to delete in the left subtree.

It is necessary to judge whether the current root node still satisfies the equilibrium condition.

If the balance condition is met, only the height information of the current root node T needs to be updated.

Otherwise, you need to make rotation adjustments:

If the height of the left subtree of the left child node of T is greater than the height of the right subtree of the left child node of T, the corresponding single rotation is carried out. Otherwise, double rotation is performed.

3. The value of the node element to be deleted is greater than the T value of the current root node, and delete it in the right subtree.

The following is a detailed code implementation:

AvlTree.h

# include # include using namespace std;#pragma once// balanced binary tree node template struct AvlNode {T data; int height; / / height AvlNode * left; AvlNode * right; AvlNode (const T theData): data (theData), left (NULL), right (NULL), height (0) {}; / / AvlTreetemplate class AvlTree {public: AvlTree () {} ~ AvlTree () {} AvlNode * root / insert node void Insert (AvlNode * & t, T x); / delete node bool Delete (AvlNode * & t, T x); / / find whether there is node bool Contains (AvlNode * t, const T x) const; / / traversal void InorderTraversal (AvlNode * t) in the middle order; / / preorder traversal void PreorderTraversal (AvlNode * t); / / minimum node AvlNode * FindMin (AvlNode * t) const / / maximum node AvlNode * FindMax (AvlNode * t) const;private: / / find the height of the tree int GetHeight (AvlNode * t); / / single rotation left AvlNode * LL (AvlNode * t); / / single rotation right AvlNode * RR (AvlNode * t); / / a pair of rotation right AvlNode * LR (AvlNode * t); / / a pair of rotation left and right AvlNode * RL (AvlNode * t);} Template AvlNode * AvlTree::FindMax (AvlNode * t) const {if (t = NULL) return NULL; if (t-> right = = NULL) return t; return FindMax (t-> right);} template AvlNode * AvlTree::FindMin (AvlNode * t) const {if (t = = NULL) return NULL; if (t-> left = = NULL) return t; return FindMin (t-> left) } template int AvlTree::GetHeight (AvlNode * t) {if (t = NULL) return-1; else return t-> height;} / / single rotation / / unbalanced template AvlNode * AvlTree::LL (AvlNode * t) {AvlNode * Q = t-> left; t-> left = Q-> right; Q-> right = t; t = Q; t-> height = max (GetHeight (t-> left), GetHeight (t-> right) + 1 Q-> height = max (GetHeight (Q-> left), GetHeight (Q-> right)) + 1; return Q;} / single rotation / / unbalanced template AvlNode * AvlTree::RR (AvlNode * t) {AvlNode * Q = t-> right; t-> right = Q-> left; Q-> left = t; t = Q; t-> height = max (GetHeight (t-> left), GetHeight (t-> right)) + 1 Q-> height = max (GetHeight (Q-> left), GetHeight (Q-> right)) + 1; return Q;} / A double rotation / / the right subtree of the left son whose insertion point is located in t template AvlNode * AvlTree::LR (AvlNode * t) {/ / A pair of single rotations can be achieved by two single rotations / / a pair of left nodes of t are rotated by RR, and then the root node is rotated by LL RR (t-> left); return LL (t) } / / A pair of rotation / / insertion points are located in the left subtree template AvlNode * AvlTree::RL (AvlNode * t) {LL (t-> right); return RR (t);} template void AvlTree::Insert (AvlNode * & t, T x) {if (t = NULL) t = new AvlNode (x); else if (x)

Data) {Insert (t-> left, x); / / judge balance if (GetHeight (t-> left)-GetHeight (t-> right) > 1) {/ / left left or left left or left if (x) in two cases

Left- > data) / / left and left t = LL (t); else / / left and right t = LR (t);} else if (x > t-> data) {Insert (t-> right, x) If (GetHeight (t-> right)-GetHeight (t-> left) > 1) {if (x > t-> right- > data) t = RR (t); else t = RL (t);}} else; / / data repetition t-> height = max (GetHeight (t-> left), GetHeight (t-> right)) + 1 } template bool AvlTree::Delete (AvlNode * & t, T x) {/ / t is empty and cannot find the node if (t = = NULL) return false to be deleted / / found the node else if (t-> data = = x) {/ / the left and right subtrees are not empty if (t-> left! = NULL & & t-> right! = NULL) {/ / delete the node with the highest left subtree height and the largest left subtree height. Assign it to root node if (GetHeight (t-> left) > GetHeight (t-> right)) {t-> data = FindMax (t-> left)-> data Delete (t-> left, t-> data);} else// right subtree is higher. Delete the node with the lowest value in the right subtree and assign it to the root node {t-> data = FindMin (t-> right)-> data; Delete (t-> right, t-> data). }} else {/ / there is a left and right subtree that is not empty. Just replace it with the child node of the node that needs to be deleted to AvlNode * old = t; t = t-> left? T-> left: t-> right;//t is assigned to the child node delete old;}} else if (x

Data) / / the node to be deleted is on the left subtree {/ / Recursively delete the node Delete on the left subtree (t-> left, x) / / determine whether the equilibrium condition if (GetHeight (t-> right)-GetHeight (t-> left) > 1) {if (GetHeight (t-> right- > left) > GetHeight (t-> right- > right)) {/ / RL double rotation t = RL (t) } else {/ / RR single rotation t = RR (t);}} else// satisfies equilibrium condition adjustment height information {t-> height = max (GetHeight (t-> left), GetHeight (t-> right)) + 1 }} the node to be deleted by else// recursively deletes the right subtree node Delete (t-> right, x) on the right subtree. / / judging equilibrium if (GetHeight (t-> left)-GetHeight (t-> right) > 1) {if (GetHeight (t-> left- > right) > GetHeight (t-> left- > left)) {/ / LR double rotation t = LR (t) } else {/ / LL single rotation t = LL (t);}} else// satisfies equilibrium adjustment height {t-> height = max (GetHeight (t-> left), GetHeight (t-> right)) + 1;}} return true } / / find the node template bool AvlTree::Contains (AvlNode * t, const T x) const {if (t = = NULL) return false; if (x

Data) return Contains (t-> left, x); else if (x > t-> data) return Contains (t-> right, x); else return true;} / / medium order traversal template void AvlTree::InorderTraversal (AvlNode * t) {if (t) {InorderTraversal (t-> left); cout data right) } / / preorder traversal template void AvlTree::PreorderTraversal (AvlNode * t) {if (t) {cout data left); PreorderTraversal (t-> right);}}

Main.cpp

# include "AvlTree.h" int main () {AvlTree tree; int value; int tmp; cout value) {if (value = =-1) break; tree.Insert (tree.root,value);} 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.