• 欢迎来到我的博客
  • [email protected]

标签:二叉树

学习笔记

红黑树(工程二叉树)

红黑树(工程二叉树)
引入 我们提到平衡二叉树是最理想的二叉排序树,性能最好,也最稳定,但是缺点是维护成本高,需要在插入和删除节点时维护新树的平衡性,所以工程实践中,我们倾向于使用另一种二叉排序树 —— 红黑树 定义 红黑树(Red-Black Tree)是每个节点都带有颜色属性的二叉排序(查找)树,具备以下特性: 节点是红色或黑色; 根节点是黑色的; 每个叶子节点都是黑色的空……继续阅读 »

tianlan 8个月前 (04-09) 198浏览 0评论 0个赞

学习笔记

平衡二叉树(AVL)

平衡二叉树(AVL)
引入 如果二叉排序树用不好,就会退化成斜树,实现算法性能退化成了 O(n) 定义 1.首先是二叉排序树 2.平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1,这个高度(深度)差的值叫做平衡因子 BF,也就是说 BF 的值不能大于1,否则就不是平衡二叉树。 实现原理 和二叉排序树差不多,只不过每次插入元素后,需要检查树的平衡性,如果平衡性遭到破坏,……继续阅读 »

tianlan 8个月前 (04-09) 168浏览 0评论 0个赞

学习笔记

二叉树、二叉排序树

二叉树、二叉排序树
树 几个概念:根节点、兄弟节点、叶子节点(没有子元素、末端节点) 度:节点的子节点数   二叉树 ①普通二叉树 ②满二叉树 ③完全二叉树(和满二叉树相比,只少了点最后一层的右侧叶子节点) 二叉树的基本性质 性质1: 在第 i 层最多有 2i-1 个节点。 性质2: 深度为 k 的二叉树最多有 2k-1 个节点。 性质3: 对于任何一个二叉树,叶……继续阅读 »

tianlan 8个月前 (04-09) 178浏览 0评论 0个赞