当前位置：网站首页>Find balanced binary tree

Find balanced binary tree

2022-07-19 10:36:00 【InfoQ】



To understand the complete dynamic search, you can take a look at the previous article

Balanced binary trees

（1） A balanced binary tree is also called AVL Trees . In a balanced binary tree, each node has a balanced factor field , Used to store the balance factor value of this node ; For example, suppose TL Represents a node T The maximum depth of the left subtree of ;TR Represents a node T The maximum depth of the right subtree of ; that ,AVL The balance factor value of each node of the tree T->BF=TL-TR.
  • if TL-TR=0( That is, the value of the node balance factor is 0), Then it is called the equilibrium node .
  • if TL-TR=1( That is, the value of the node balance factor is 1), It is called left multiple node .
  • if TL-TR=-1, Then it is called right multiple node .
In a binary sort tree , If the balance factor value of each node is -1、0、1 One of the three , that , Call this tree balanced binary sort tree for short . The absolute value of the balance factor of nodes in the tree is greater than or equal to 2, The tree is unbalanced .


（2） Observe the construction process of binary sort tree to find out the cause of imbalance . The value of the new node inserted in the balance factor is 0 Neither the left nor the right of the node will cause imbalance . The value of the new node inserted in the balance factor is 1( or -1) Right of the node of ( Or left ) Branch , This node will not cause imbalance . The value of the new node inserted in the balance factor is 1( or -1) Left of node of ( Or right ) On the branch , here , The absolute value of the equilibrium factor of this node ≧2, Cause the binary sort tree to be unbalanced . The figure below 10.7 In the left figure of 70 Before insertion ,50 The balance factor value of is -1, And on the right 20 Before insertion ,50 The balance factor value of is 1.


  • Type definition of binary sort tree
typedef structBSTNode{
 ElemType data;
int bf;( Balance factor field of nodes ) 
struct BSTNode *lchild,*rchild;
} BSTNode,*BSTree;
Void R-Rotate(BSTree &p){( Rotate right ,) 
lc=p->lchild;(LC by *P The root node of the left subtree of )
p->lchild=lc->rchild;(LC The right subtree of *P The left subtree )
 lc->rchild=p; p=lc;(P Point to the new root node , namely B Belt replacement A)
}// R- Rotate
Void L-Rotate(BSTree &p){( Rotate left ) 
rc=p->rchild; (RC by *P The root node of the right subtree of ) 
p->rchild=lc->lchild;(RC The left subtree of as *P The right subtree )
 lc->lchild=p;p=rc;(P Point to the new root node , namely B Belt replacement A)
}// L- Rotate


Balanced binary tree algorithm is relatively complex , Do not ask , Understand balanced binary tree .
原网站

版权声明
本文为[InfoQ]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/200/202207171232218777.html

边栏推荐

猜你喜欢

随机推荐