一,定义
二叉排序树(简称BST)的定义为:二叉排序或者是空树,或者是满足如下性质的二叉树:
若他的左子树非空,则左子树上所有记录的值均小于根记录的值
若他的右子树非空,则右子树上所有记录的值均大于根记录的值
左,右子树本身又各是一棵二叉排序树
二,性质
- 1, 二叉排序树按中序遍历该树所得到的中序序列是一个递增有序序列
- 2,二叉排序树最大节点是根节点的最右下节点,最小节点是根节点的最左下节点
三,二叉排序树的查找
若二叉排序树非空,将给定关键字与根节点比较,若相等,则查找成功.
若不等,则当根节点关键字值大于给定关键字值时,到根节点的左子树中查找;否则到根节点的右子树中查找.
四,二叉树的插入和构建
若原二叉排序树为空,则直接插入节点;
否则,若关键字k小于根节点的值,则插入到左子树
若关键字k大于根节点,则插入到右子树
例如LeetCode 108. Convert Sorted Array to Binary Search Tree
** 值得注意的是: 在二叉排序树中插入的节点都是作为叶子节点插入的 **
五,二叉排序的删除
BST删除一个节点后,仍要保持BST的特性. 删除一个节点本质上说,就是使用这个节点的中序遍历的直接前驱或者直接后继来代替他
删除一个节点分为四种情况
- 1)待删除节点p是个叶子节点,那么直接删除他即可
- 2)待删除节点p只有右子树而无左子树,此时只需p的右子树根节点代替p即可
- 3)待删除节点p只有左子树而无右子树,此时只需p的左子树根节点代替p即可
- 4)待删除节点p左右子树都不为空.可以有两种方法处理
A,用p的左子树的最右边节点代替
B,用p的右子树的最左边节点代替
例如LeetCode 450. Delete Node in a BST
