树型查找¶

二叉排序树¶

二叉排序树的定义¶

二叉排序树，也叫二叉查找树、二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，它的每个节点都满足以下性质（除空树外）：

• 若左子树非空，则左子树上所有结点的值均小于根结点的值

• 若右子树非空，则右子树上所有结点的值均大于根结点的值

• 左、右子树也分别为二叉排序树

二叉排序树的查找¶

二叉排序树的插入¶

若二叉排序树为空，则新插入的结点为新的根结点；否则，新插入的结点必为新的叶结点，并遵守以下原则：

• 若新插入的结点值小于根结点值，则新插入的结点为左子树的最右结点

• 若新插入的结点值大于根结点值，则新插入的结点为右子树的最左结点

向二叉排序树插入一个新结点时，新结点总是插入到叶子结点下，且新插入的结点必然是一个叶子结点。

二叉排序树的构造¶

二叉排序树的删除¶

在二叉排序树中删除结点不能直接删除，要找到被删除结点的直接前驱或直接后继来代替被删除结点，然后删除该直接前驱或直接后继结点。

1. 若被删除的结点是叶子结点，则直接删除

2. 若结点只有一棵左子树或右子树，则让该结点的子树成为该结点的父结点的子树

3. 若结点有一棵左、右两棵树，则令该结点中序序列的直接后继（直接前驱）代替该结点，然后从二叉排序树中删去这个直接后继（直接前驱），这样就转换成了前面两种情况

二叉排序树的查找效率分析¶

平衡二叉树¶

平衡二叉树的定义¶

平衡二叉树的插入¶

LL平衡旋转¶

RR平衡旋转¶

LR平衡旋转¶

RL平衡旋转¶

平衡二叉树的删除¶

平衡二叉树的查找¶

红黑树¶

红黑树的定义¶

红黑树的插入¶

红黑树的删除¶