当前位置:网站首页>Balanced binary tree (AVL)
Balanced binary tree (AVL)
2022-07-07 16:16:00 【Ceylon_ CC】
Catalog
The definition of balanced binary tree
Balanced binary tree insertion
LL Balance rotation ( Right single rotation )
RR Balance rotation ( Left single rotation )
LR Balance rotation ( First left then right double rotation )
RL Balance rotation ( First right then left double rotation )
Construction of balanced binary tree
Search of balanced binary tree
The definition of balanced binary tree
Q: What is a binary sort tree
A: Binary sort tree or an empty tree , Or a binary tree with the following properties
- 1) If its left subtree is not empty , be The left subtree Values of all nodes on All less than The value of its root
- 2) If its right subtree is not empty , be Right subtree Values of all nodes on All are greater than The value of its root
- 3) Left 、 The right subtree is also a binary sort tree
Q: What is a balanced binary tree
A: It could be an empty tree , Or a binary sort tree with the following properties : The absolute value of the depth difference between the left subtree and the right subtree does not exceed 1, And its left and right subtrees are a balanced binary tree .
The height difference between the left subtree and the right subtree of a node is defined as the balance factor of the node , Then the balance factor of the balanced binary tree node can only be -1,0,1.
Balanced binary tree insertion
Whenever you insert... In a binary sort tree ( Or delete ) When a node , First, check whether the nodes on the insertion path are unbalanced due to this operation . If it causes an imbalance , Then find the absolute value of the balance factor on the path closest to the insertion node is greater than 1 The node of A, Then to A Root subtree , On the premise of maintaining the characteristics of sorting tree , Adjust the position relationship of each node , Bring it back to balance .
The first half of the insertion process of balanced binary tree is the same as that of binary sort tree , But after the new node is inserted , If a node on the search path is no longer balanced , Then you need to make corresponding adjustments . The law of adjustment can be summarized as follows 4 In this case :
LL Balance rotation ( Right single rotation )
Because at the node A The left child (L) The left subtree (L) A new node is inserted on ,A The equilibrium factor of is 1 to 2 , Lead to A The root of the subtree is out of balance , A right rotation operation is required , take A The left child B Rotate right up instead of A Become the root node , take A The node rotates down to the right to become B The root node of the right subtree of , and B The original right subtree of is used as A The left subtree of the node .
RR Balance rotation ( Left single rotation )
Because at the node A The right child (R) The right subtree (R) A new node is inserted on ,A The equilibrium factor of is −1 Be reduced to −2, Lead to A The root of the subtree is out of balance , A rotation to the left is required . take A The right child B Rotate left and up instead of A Become the root node , take A The node rotates to the left and down to become B The root node of the left subtree of , and B The original left subtree of is used as A Right subtree of node .
LR Balance rotation ( First left then right double rotation )
stay A The left child (L) The right subtree (R) Insert new node on ,A The equilibrium factor of is 1 to 2, Lead to A The root of the subtree is out of balance , Two rotations are required , Rotate left first, then right . First the A The left child of the node B The root node of the right subtree of C Rotate upward to the left to lift to B The location of the node , Then put the C Rotate the node to the right and up to A The location of the node .
RL Balance rotation ( First right then left double rotation )
Because in A The right child (R) The left subtree (L) Insert new node on ,A The equilibrium factor of is −1 Be reduced to −2, Lead to A The root of the subtree is out of balance , Two rotations are required , First right then left . First the A The right child of the node B The root node of the left subtree of C Rotate upward to the right to lift to B The location of the node , Then put the C Rotate the node to the left and up to A The location of the node .
Construction of balanced binary tree
Assume that the keyword sequence is {6,1,2,5,4,3}, The process of generating binary sort tree through this sequence is as follows :
First step : Create an empty tree
The second step : Insert node 6
The third step : Insert node 1
Step four : Insert node 2
Step five :LR rotate
Step six : Insert node 5
Step seven : Insert node 4
Step eight :LL rotate
Step nine : Insert node 3
Step 10 :RL rotate
Search of balanced binary tree
The process of searching on a balanced binary tree is the same as that of a binary sort tree . therefore , During the search , The number of keywords compared with the given value does not exceed the depth of the tree . Suppose nh, The depth is h The minimum number of nodes in the balanced tree . obviously ,nh Yes n0=0,n1=1,n2=2, And there are nh=nh−1+nh−2+1. Can prove that , contain n The maximum depth of a balanced binary tree of nodes is O(log2n), Therefore, the average search length of balanced binary tree is O(log2n).
边栏推荐
- laravel中将session由文件保存改为数据库保存
- Shandong old age Expo, 2022 China smart elderly care exhibition, smart elderly care and aging technology exhibition
- Power of leetcode-231-2
- AE learning 02: timeline
- 【花雕体验】15 尝试搭建Beetle ESP32 C3之Arduino开发环境
- prometheus api删除某个指定job的所有数据
- Eye of depth (VII) -- Elementary Transformation of matrix (attachment: explanation of some mathematical models)
- 深度之眼(七)——矩阵的初等变换(附:数模一些模型的解释)
- How to implement backspace in shell
- Performance comparison of tidb for PostgreSQL and yugabytedb on sysbench
猜你喜欢
SysOM 案例解析:消失的内存都去哪了 !| 龙蜥技术
Excessive dependence on subsidies, difficult collection of key customers, and how strong is the potential to reach the dream of "the first share of domestic databases"?
强化实时数据管理,英方软件助力医保平台安全建设
Three. JS introductory learning notes 18: how to export JSON files with Blender
[flower carving experience] 15 try to build the Arduino development environment of beetle esp32 C3
谈谈 SAP iRPA Studio 创建的本地项目的云端部署问题
What about the pointer in neural network C language
通知Notification使用全解析
【花雕体验】15 尝试搭建Beetle ESP32 C3之Arduino开发环境
Three. JS introductory learning notes 11:three JS group composite object
随机推荐
Three. JS introductory learning notes 19: how to import FBX static model
thinkphp3.2.3中设置路由,优化url
121. The best time to buy and sell stocks
如何在shell中实现 backspace
航天宏图信息中标乌鲁木齐某单位数据库系统研发项目
What else can an ordinary person do besides working in a factory to make money?
Three. JS introductory learning notes 13: animation learning
Eye of depth (VII) -- Elementary Transformation of matrix (attachment: explanation of some mathematical models)
TCP framework___ Unity
Particle effect for ugui
Three. JS introductory learning notes 05: external model import -c4d into JSON file for web pages
AE learning 01: AE complete project summary
Power of leetcode-231-2
hellogolang
PHP实现微信小程序人脸识别刷脸登录功能
Strengthen real-time data management, and the British software helps the security construction of the medical insurance platform
IP地址和物理地址有什么区别
【花雕体验】15 尝试搭建Beetle ESP32 C3之Arduino开发环境
分步式监控平台zabbix
Shandong old age Expo, 2022 China smart elderly care exhibition, smart elderly care and aging technology exhibition