Python中的二叉排序树和平衡二叉树是什么？
二叉排序树二叉排序树又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：若它的左子树不为空，则左子树上所有节点的值均小于它的根结构的值；若它的右子树不为空，则右子树上所有节点的值均大于它的根结构的值；它的左、右子树也分别为二叉排序树。
构造一颗二叉排序树的目的，往往不是为了排序，而是为了提高查找和插入删除关键字的速度。二叉排序树的操作：查找：对比节点的值和关键字，相等则表明找到了；小了则往节点的左子树去找，大了则往右子树去找，这么递归下去，最后返回布尔值或找到的节点。插入：从根节点开始逐个与关键字进行对比，小了去左边，大了去右边，碰到子树为空的情况就将新的节点链接。删除：如果要删除的节点是叶子，直接删；如果只有左子树或只有右子树，则删除节点后，将子树链接到父节点即可；如果同时有左右子树，则可以将二叉排序树进行中序遍历，取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。
二叉排序树总结：二叉排序树以链式进行存储，保持了链接结构在插入和删除操作上的优点。在极端情况下，查询次数为1，但最大操作次数不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状，也就引申出了后面的平衡二叉树。给定一个元素集合，可以构造不同的二叉排序树，当它同时是一个完全二叉树的时候，查找的时间复杂度为O(log(n))，近似于二分查找。当出现最极端的斜树时，其时间复杂度为O(n)，等同于顺序查找，效果最差。
平衡二叉树平衡二叉树（AVL树，发明者的姓名缩写）：一种高度平衡的排序二叉树，其每一个节点的左子树和右子树的高度差最多等于1。平衡二叉树首先必须是一棵二叉排序树！平衡因子（Balance Factor）：将二叉树上节点的左子树深度减去右子树深度的值。对于平衡二叉树所有包括分支节点和叶节点的平衡因子只可能是-1,0和1，只要有一个节点的因子不在这三个值之内，该二叉树就是不平衡的。
最小不平衡子树：距离插入结点最近的，且平衡因子的绝对值大于1的节点为根的子树。平衡二叉树的构建思想：每当插入一个新结点时，先检查是否破坏了树的平衡性，若有，找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，进行相应的旋转，成为新的平衡子树。下面是由[1,2,3,4,5,6,7,10,9]构建平衡二叉树
原文至：Python中的二叉排序树和平衡二叉树是什么-Python学习网
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/92447.html
