算法复习-树

BST

二叉搜索树

在⼆叉树的基础上，增加了对⼆叉树上节点存储位置的限制：

• 左子节点值小于父节点的值
• 右节点的值大于父节点的值

在理想情况下，⼆叉树每多⼀层，可以存储的元素都增加⼀倍。也就是说 n 个元素的⼆叉搜索树，对应的树⾼为 O(logn)。所以我们查找元素、插⼊元素的时间也为 O(logn)。当然这是理想情况下，但在实际应⽤中，并不是那么理想，例如⼀直递增或递减的给⼀个⼆叉查找树插⼊数据，那么所有插⼊的元素就会⼀直出现在⼀个树的左节点上，数型结构就会退化为链表结构，时间复杂度就会趋于 O(n)，这是不好的。

AVL树用来解决这个问题

AVL

平衡搜索二叉树

在二叉搜索树的基础上满⾜左右⼦树⾼度不⼤于1

红黑树

红黑树也是一种特殊的二叉搜索树

在二叉搜索树的基础上添加以下限制：

• 节点是红⾊或⿊⾊
• 根节点必须是⿊⾊节点
• 所有的叶⼦节点都必须是值为NULL的⿊节点
• 如果⼀个节点是红⾊的，则它两个⼦节点都是⿊⾊的
• 从任⼀节点到达它的每个叶⼦节点的所有的路径，都有相同数⽬的⿊⾊节点