title: "二叉排序树-BST"
date: 2015-06-25 09:08:54
categories: 数据结构
tags: 数据结构
为什么要有BST？
- 查找用顺序存储是最快的，但是顺序存储不适合插入/删除等操作；
- BST则可以两全齐美，在查找的同时可以进行插入和删除操作，采用
链式存储实现；
定义
- Binary Sort Tree；
- 又称为二叉查找树；
- 左子树上所有结点的值均小于根结点的值；
- 右子树上所有结点的值均大于根结点的值；
特性
- 二叉排序树中，各结点关键字是
惟一的； - 中序遍历BST为
有序序列；
操作
- 插入操作很简单，最终成为度<2的结点的孩子；
- 删除操作分为两种情况：
- 删除结点只有一个孩子，则将它的左/右子树整个移动到删除结点的位置；
- 删除结点有两个孩子，则将BST中序遍历该结点的
前驱或后继结点代替删除结点的位置，（或者说是将删除结点左子树中序遍历最后一个结点或删除结点右子树中序遍历第一个结点代替删除结点的位置）；
BST
- 上图：无序串 BFXDYAC可以存储在数据库或文件中
存储，我们在写程序的时候，将其取出，然后将其构造为BST内存，最后就可以对BST进行操作实际操作。
讨论板图
taolun-BST
