搜索树

二叉搜索树-红黑树

前面介绍了AVL树虽然AVL树将二叉树的高度差保证在1 但是实现的太过复杂因为要不断调整平衡因子故而要来介绍另外一个用途比较广的结构红黑树红黑树先来看来红黑树的特性 1 每个节点非红即黑 2 根节点为黑色 3 不能有连续的红节点

数据结构 搜索树 红黑树 二叉树
二叉搜索树-AVL树的实现

首先 AVL树是一棵加了额外平衡条件的搜索树这是因为普通的搜索树如果插入的key接近有序的话二叉树将会退化成一个单链表导致查找的时间复杂度为O N 而AVL树中用一个平衡因子来制约树的左右子树的高度保证任何节点的左右子树高度之差最多

数据结构 AVL树 搜索树 平衡树

二叉搜索树-红黑树