红黑树（Red Black Tree）是一种平衡的排序二叉树，如图： 所有的红黑树都满足如下性质： 每个节点要么是红色，要么是黑色的； 根节点和叶子节点（即 NIL 空节点）一定是黑色； 红色节点的父节...

红黑树与AVL树区别 1、调整平衡的实现机制不同 红黑树根据路径上黑色节点数目一致，来确定是否失衡，如果失衡，就通过变色和旋转来恢复 AVL根据树的平衡因子(所有节点的左右子树高度差的绝对值...

RBT面试题 问：有了二叉搜索树，为什么还需要平衡二叉树？ 二叉搜索树容易退化成一条链 这时，查找的时间复杂度从O ( log n）也将退化成O ( N ) 引入对左右子树高度差有限制的平衡二叉树 AVL，...

红黑树（RBTree） 红黑树是一种特化的AVL树（平衡二叉树） 红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）. 在1978年被 Leo J. Guibas 和 Robert S...