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

AVL tree of the establishment of the complete C code how to write, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain in detail for you, people with this need can come to learn, I hope you can gain something.

Related concepts of balanced binary tree

The time complexity of the search on the binary search tree is proportional to the path from the root node to the object node, and at worst equal to the height of the tree.

When constructing a binary search tree, if the sequence of input objects happens to be ordered by their key size, the result will be an one-branch tree.

For example, the input sequence is {11pm 39pm 46pm 38pm 75}.

The time required to find such a tree is O (n) (proportional to the number of nodes).

Balanced Tree: a tree with a height of O (logn).

Balanced binary tree (Balanced Binary Tree): it was first proposed by Adelson Wells and Adelson-Velskii and Landis in 1962, so it is also called AVL tree.

An empty binary tree is an AVL tree

If T is a non-empty binary search tree, and TL and TR are its left and right subtrees, then T is an AVL tree if T satisfies the following conditions:

1) TL and TR are AVL trees

2) | hL-hR | ≤ 1 ≤ HL and hR are the heights of the left and right subtrees, respectively.

The height of the AVL tree with n elements is O (logn)

An n-element AVL search tree can complete the search in the time O (height) = O (logn).

Insert a new element into an AVL search tree of n elements to get an AVL tree of n elements. This insertion process can be completed in O (logn) time.

Delete an element from an n-element AVL search tree to get an AVL tree of n-logn 1 element, which can be completed in O (logn) time.

Add a balance factor bf for each node. The balance factor bf (x) of node x is defined as: bf (x) = hL-hR.

That is, the height of the left subtree of x-the height of the right subtree of x

From the definition of AVL tree, we can know that the possible values of balance factor are-1, 0, 1.

If the absolute value of the balance factor of any node in the tree is greater than 1, the binary tree will lose its balance.

If an AVL tree has n nodes, its height can be maintained at O (logn), so the average search length can also be maintained at O (logn).

The binary search tree algorithm is completely suitable for AVL trees.

If a binary search tree is a balanced binary tree, it may become an unbalanced binary tree after inserting a node.

[solution] balance the binary tree to make it a balanced binary tree.

Balanced processing of non-AVL trees

Each time a new node is inserted, the balance of the related nodes in the AVL tree changes.

Therefore, after inserting a new node, you need to trace back from the insertion position along the path to the root and check the balance factor of each node (the height difference between the left and right subtrees).

If a height imbalance is found at a node, stop backtracking

Starting from the node where the imbalance occurs, take the nodes of the lower two layers directly along the path just backtracked, and do the balanced rotation. There are two types of balanced rotation:

Single rotation (LL rotation and LR rotation)

Double rotation (LR rotation and RL rotation)

If the three nodes are in a straight line, a single rotation is used for balancing.

If the three nodes are on a broken line, double rotation is used for balancing.

LL balance rotation:

If a node is inserted into the left subtree of the left subtree of C, the balance factor of C is increased from 1 to 2, which requires a clockwise rotation. (B as the axis of rotation)

RR balance rotation:

If a node is inserted into the right subtree of the right subtree of A, the balance factor of An is changed from-1 to-2, which requires a counterclockwise rotation. (B as the axis of rotation)

LR balance rotation:

If a node is inserted into the right subtree of the left subtree of C to increase the balance factor of C from 1 to 2, it is necessary to rotate counterclockwise and then clockwise. (take the inserted node B as the axis of rotation)

RL balance rotation:

If a node is inserted into the left subtree of the right subtree of A to change the balance factor of A from-1 to-2, it is necessary to rotate clockwise and then counterclockwise. (take the inserted node B as the axis of rotation)

LL rotation: the newly inserted node is in the left subtree of the left subtree of the unbalanced node

RR rotation: the newly inserted node is in the right subtree of the right subtree of the unbalanced node

LR rotation: the newly inserted node is in the right subtree of the left subtree of the unbalanced node

RL rotation: the newly inserted node is in the left subtree of the right subtree of the unbalanced node.

Establishment of AVL tree complete C code / * creation of AVL tree complete C code * / # include # include # define max (a) > (b))? (a): (B) typedef int ElemType;// defines the structure of the balanced binary tree typedef struct AVLNode {ElemType data; int height; struct AVLNode * lchild, * rchild;} AVLNode, * AVLTree;// calculates the height function int GetHeight (AVLTree t) {if (NULL = = t) return-1 Else return (1+max (GetHeight (t-> lchild), GetHeight (t-> rchild));} / / right-handed operation void SingleRotateWithRight (AVLTree * t) {AVLTree p; p = (* t)-> lchild; (* t)-> lchild = p-> rchild; p-> rchild = (* t) / / change the position of the node and update the height value of the node (* t)-> height = GetHeight (* t); p-> height = GetHeight (p); * t = p;} / / left-handed operation void SingleRotateWithLeft (AVLTree * t) {AVLTree p; p = (* t)-> rchild; (* t)-> rchild = p-> lchild; p-> lchild = (* t) / / change the position of the node, update the height value of the new node (* t)-> height = GetHeight (* t); p-> height = GetHeight (p); * t = p;} / / A double rotation operation-first left to right void DoubleRotateWithLeft (AVLTree * t) / / LR imbalance AVL {SingleRotateWithLeft (& (* t)-> lchild); SingleRotateWithRight (t) } / / double spin operation-first right to left void DoubleRotateWithRight (AVLTree * t) / / RL imbalance AVL {SingleRotateWithRight (& (* t)-> rchild); SingleRotateWithLeft (t);} / / Node insertion function void Insert (AVLTree * t, ElemType e) {if (NULL = * t) {(* t) = (AVLTree) malloc (sizeof (AVLNode)); (* t)-> data = e (* t)-> height = 0; (* t)-> lchild = (* t)-> rchild = NULL;} else if (e

Data) {/ / insert Insert (& (* t)-> lchild, e) into the left subtree; if (GetHeight ((* t)-> lchild)-GetHeight ((* t)-> rchild) = = 2) {/ / AVL tree unbalanced if (e)

Lchild- > data) / / LL is inserted into the left side of the subtree SingleRotateWithRight (& (* t)); else DoubleRotateWithLeft (& (* t)) / / LR is inserted to the right of the left subtree, first left to the left subtree, and then to the current root node right}} else if (e > (* t)-> data) {Insert (& (* t)-> rchild, e) If (GetHeight ((* t)-> lchild)-GetHeight ((* t)-> rchild) =-2) {if (e > (* t)-> rchild- > data) / / insert into SingleRotateWithLeft (& (* t) on the right side of the right subtree) Else DoubleRotateWithRight (& (* t)); / / is inserted to the left of the right subtree, first to the right subtree, and then to the current root node left}} (* t)-> height = max (GetHeight ((* t)-> lchild), GetHeight ((* t)-> rchild)) + 1 } / / define the function void CreateAVL (AVLTree * t, ElemType * a, int n) {(* t) = NULL; for (int itrees; ilchild); printf ("% d", t-> data); InOrderPrint (t-> rchild);} int main () {int n; AVLTree t; printf ("Please enter the number of nodes of the AVL tree:\ n") Scanf ("% d", & n); ElemType * a = (ElemType *) malloc (sizeof (ElemType) * n); printf ("Please enter node data:\ n"); for (int item0; I

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.