平衡二叉树

冷不防 2024-03-22 22:55 19阅读 0赞

平衡二叉树是在二叉查找树的基础上使二叉树保持平衡，即任意节点的左右子树高度差不超过1，下图就是一个平衡二叉树  
![在这里插入图片描述][8a9aa929a586400db7ac75021ce5263c.png]  
当插入一个新的节点导致二叉树不平衡时可以通过两种操作来使二叉树达到平衡

## 一、左旋 ##

### 第一种情况 ###

![在这里插入图片描述][beab3dc69aef4dabb899be5f918e9737.png]  
在原来的平衡二叉树的基础上添加一个10节点，从新加入的节点向上找不平衡的节点，8节点的左子树高度为0，右子树的高度为2，高度差大于1  
步骤：  
①以8作为支点  
②把支点左旋降级变成左子节点  
③晋升原来的右子节点  
![在这里插入图片描述][17b1fc820da04926b19e5c008eacb6e7.png]

### 第二种情况 ###

![在这里插入图片描述][4382ca0e907141a0a3090236647b45d2.png]  
在上面平衡二叉树的基础上继续添加11，导致二叉树失衡  
步骤：  
①从添加到节点开始往父节点找不平衡的节点作为支点（上面二叉树中不平衡的支点为根节点）  
②将根节点的右侧往左拉  
③把原先的右子节（9）点作为根节点，把晋升的节点（9）的左子树（8）给降级的根节点（7）作为右子节点  
![在这里插入图片描述][350b086181b748ccbe0d28ee072e23d0.png]

## 二、右旋 ##

右旋与左旋相反

### 第一种情况 ###

![在这里插入图片描述][0bfe6614ef804ae28cc4e143a98665bb.png]

步骤：  
①以不平衡的点作为支点  
②把支点右旋降级，变成右子节点  
③晋升原来的左子节点  
![在这里插入图片描述][e2b9378815c64f8ab8d918c1ea09536a.png]

### 第二种情况 ###

![在这里插入图片描述][f48c0287914b4844888024fc23b7a1b2.png]

步骤：  
①以不平衡的点作为支点  
②把根节点左侧往右拉  
③把原来根节点（7）的左子节点（5）晋升为根节点，新的根节点（5）的右子节（6）点作为降级的根节点（7）的左子节点  
![在这里插入图片描述][03ac0707091940c2a87a76d269513cbc.png]

## 三、二叉树不平衡的四种情况 ##

![在这里插入图片描述][cced4e3b7e254880841e95b1e48baa6b.png]

1.左左：当根节点的左子树的左子树插入节点时导致二叉树不平衡  
![在这里插入图片描述][1fdad0037f0047ba81faa2bb814b214d.png]  
此时只需要一次右旋即可使二叉树平衡  
![在这里插入图片描述][977eb9e8e79e46d6a52a587905666337.png]  
2.左右：根节点的左子树的右子树插入节点时导致二叉树不平衡  
![在这里插入图片描述][2e43575e52f44f29a41999d96a01ab6f.png]  
此时一次以根节点为支点的右旋不能完成二叉树的平衡，需要先以4为支点进行一次左旋，再以根节点为支点进行一个右旋  
左旋  
![在这里插入图片描述][d268bf3421a3493f84e3b821ceec1436.png]  
右旋  
![在这里插入图片描述][0a94ef1e44c84e5ebf35675851a8c665.png]  
3.右右：根节点的右子树的右子树插入节点时导致二叉树不平衡  
![在这里插入图片描述][00a4b08abcf543c38ab9db2e244b5127.png]  
![在这里插入图片描述][110107b7939f427ba04556e0ef6f8d1b.png]  
只需要进行一次左旋即可  
![在这里插入图片描述][a26f2c3f0de345e2bd250ca20ff1b6e9.png]  
4.右左：根节点的右子树的左子树插入节点时导致二叉树不平衡  
![在这里插入图片描述][aa55777c52ac4d4ebb30f1fcdaca95a7.png]  
先以10为支点进行一次右旋，再以根节点为支点进行一次左旋  
右旋  
![在这里插入图片描述][a25fbf74c9914e5388764ce7fe0625d0.png]  
左旋  
![在这里插入图片描述][39fc9b2608de4115a80cdf48e23c984f.png]

[8a9aa929a586400db7ac75021ce5263c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/52b16289982a439ca5600cb3a86dbca7.png
[beab3dc69aef4dabb899be5f918e9737.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7661b586d07c4ee782594e24d72659cb.png
[17b1fc820da04926b19e5c008eacb6e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/4097e0802ce3433fb13866f81d2d9e5e.png
[4382ca0e907141a0a3090236647b45d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/681fdbca8a564efe981730ca04dad642.png
[350b086181b748ccbe0d28ee072e23d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/fca60b0af0ed4616be58b2a125064c2a.png
[0bfe6614ef804ae28cc4e143a98665bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8bf51f2790854d819d737c5a69db31a0.png
[e2b9378815c64f8ab8d918c1ea09536a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/aafabf1a8485420f89115da246c65ec2.png
[f48c0287914b4844888024fc23b7a1b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/bc00e42dd6fa4a0fad1aee2901ba70ce.png
[03ac0707091940c2a87a76d269513cbc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/b7e64e819d2843f280119e3bf6d5583c.png
[cced4e3b7e254880841e95b1e48baa6b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/446d6ee1086a4257a57d0af74d19d849.png
[1fdad0037f0047ba81faa2bb814b214d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/2d5cf8bf418f4f84abf4618febf6ade8.png
[977eb9e8e79e46d6a52a587905666337.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a476947caf7343d69c5a49c55e4ff06e.png
[2e43575e52f44f29a41999d96a01ab6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a1186f535b6f436b99862b9700434787.png
[d268bf3421a3493f84e3b821ceec1436.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/eb16c70998b142679c6a570a51c43b75.png
[0a94ef1e44c84e5ebf35675851a8c665.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/26ad6fb62beb4a9fa8f37fa814aa1b60.png
[00a4b08abcf543c38ab9db2e244b5127.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/be8dfbf6c2d547758f4e1b4ed5b9d19b.png
[110107b7939f427ba04556e0ef6f8d1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/da19af15caf54554bcfe0c9cec9a3447.png
[a26f2c3f0de345e2bd250ca20ff1b6e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/df18949234ec48cb979e135d55438486.png
[aa55777c52ac4d4ebb30f1fcdaca95a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/97c1989254414ffc861735d57d8f26c1.png
[a25fbf74c9914e5388764ce7fe0625d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/2d417b1035624229a840e8782b05af21.png
[39fc9b2608de4115a80cdf48e23c984f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7fcb06ba0b0d4951bd450216b962bb1f.png