二叉排序树查找

1.二叉排序树的概念:

二叉排序树是一种动态树表。

二叉排序树的定义：二叉排序树或者是一棵空树，

或者是一棵具有如下性质的二叉树：

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

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

⑶ 左、右子树本身又各是一棵二叉排序树。二叉排序树的性质： 按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。

2.二叉排序树的插入:

在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。

插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；

当非空时，将待插结点关键字S->key和树根关键字t->key进行比较，

若s->key = t->key,则无须插入，若s->key< t->key,则插入到根的左子树中，

若s->key> t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，

如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。

3. 二叉排序树生成：

从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。

说明：

① 每次插入的新结点都是二叉排序树上新的叶子结点。

② 由不同顺序的关键字序列，会得到不同二叉排序树。

③ 对于一个任意的关键字序列构造一棵二叉排序树，其实质上对关键字进行排序。

4.二叉排序树查找的程序实现:

5. 二叉排序树的删除:

假设被删结点是*p，其双亲是*f，不失一般性，设*p是*f的左孩子，下面分三种情况讨论：

⑴ 若结点*p是叶子结点，则只需修改其双亲结点*f的指针即可。

⑵ 若结点*p只有左子树PL或者只有右子树PR，则只要使PL或PR 成为其双亲结点的左子树即可。

⑶ 若结点*p的左、右子树均非空，先找到*p的中序前趋结点*s（注意*s是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：

① 令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。

② 以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上。

6. 删除算法演示 :

7. 二叉排序树的查找:

在二叉排序树中进行查找的过程和二分查找类似，也是一个逐步缩小查找范围的过程。若查找成功，则是走了一条从根结点到待查结点的路径；若查找失败，则是走了一条根结点到某个叶子结点的路径。因此，查找过程中和关键字比较的次数不超过树的深度。

由于含有n个结点的二叉排序树不唯一，形态和深度可能不同。故含有n个结点的二叉排序树的平均查找长度和树的形态有关。

最好的情况是： 二叉排序树和二叉判定树形态相同。

最坏的情况是： 二叉排序树为单支树，这时的平均查找长度和顺序查找时相同。

最坏情况示例

就平均性能而言，

二叉排序树上的查找和二分查找相差不大，并且二叉排序树上的插入和删除结点十分方便，无须大量移动结点。

若根结点的关键字值等于查找的关键字，成功。

否则，若小于根结点的关键字值，递归查左子树。

若大于根结点的关键字值，递归查右子树。

若子树为空，查找不成功。

插入算法：

首先执行查找算法，找出被插结点的父亲结点。

判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

若二叉树为空。则首先单独生成根结点。

注意：新插入的结点总是叶子结点。

void InsertBST(t，key)

//在二叉排序树中插入查找关键字key

{

if(t==NULL){

t=new BiTree;

t->lchild=t->rchild=NULL;

t->data=key;

return; }

if(keydata ) InsertBST(t->lchild,key);

else InsertBST (t->rchild, key );

}

void CreateBiTree(tree,d【 】,n）

//n个数据在数组d中，tree为二叉排序树根

{tree=NULL;

for(i=0;i InsertBST(tree,d);

}

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文《An algorithm for the organization of information》中发表了它。

高度为 h 的 AVL 树，节点数 N 最多2^h − 1; 最少 (其中)。

最少节点数 n 如以斐波那契数列可以用数学归纳法证明:

Nh=F【h+ 2】 - 1 (F【h+ 2】是 Fibonacci polynomial 的第h+2个数)。

即:

N0 = 0 (表示 AVL Tree 高度为0的节点总数)

N1 = 1 (表示 AVL Tree 高度为1的节点总数)

N2 = 2 (表示 AVL Tree 高度为2的节点总数)

Nh=N【h− 1】 +N【h− 2】 + 1 (表示 AVL Tree 高度为h的节点总数)

换句话说，当节点数为 N 时，高度 h 最多为。

节点的平衡因子是它的右子树的高度减去它的左子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

AVL树的基本操作一般涉及运做同在不平衡的二叉查找树所运做的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL 旋转"。

假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a(即a是离插入点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行进行的规律可归纳为下列四种情况:

单向右旋平衡处理RR:由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作;

单向左旋平衡处理LL:由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作;

双向旋转(先左后右)平衡处理LR:由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转(先左旋后右旋)操作。

双向旋转(先右后左)平衡处理RL:由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转(先右旋后左旋)操作。

向AVL树插入可以通过如同它是未平衡的二叉查找树一样把给定的值插入树中，接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。因为折回到根节点的路途上最多有 1.5 乘 log n 个节点，而每次 AVL 旋转都耗费恒定的时间，插入处理在整体上耗费 O(log n) 时间。 在平衡的的二叉排序树Balanced BST上插入一个新的数据元素e的递归算法可描述如下: 若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1; 若e的关键字和BBST的根结点的关键字相等，则不进行; 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加(+1)时，分别就下列不同情况处理之: BBST的根结点的平衡因子为-1(右子树的深度大于左子树的深度，则将根结点的平衡因子更改为0，BBST的深度不变; BBST的根结点的平衡因子为0(左、右子树的深度相等):则将根结点的平衡因子更改为1，BBST的深度增1; BBST的根结点的平衡因子为1(左子树的深度大于右子树的深度):则若BBST的左子树根结点的平衡因子为1:则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变; 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加(+1)时，分别就不同情况处理之。

从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有 log n个节点被旋转，而每次 AVL 旋转耗费恒定的时间，删除处理在整体上耗费 O(log n) 时间。

在AVL树中查找同在一般BST完全一样的进行，所以耗费 O(log n) 时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查询而改变。(这是与伸展树查找相对立的，它会因为查找而变更树结构。)

给出一个操作AVLTREE的完整程序 大部分由Peter Brass编写

public class AVLTree<T extends Comparable<? super T>> {

private AVLNode<T> root;

public AVLTree() {root = null;}

/*** Check if given item x is in the tree.*/

public boolean contains(T x) {return contains(x, root);}

/*** Internal method to check if given item x is in the subtree.*

* @param x* the given item to check.

* @param t* the node that roots the subtree.*/

private boolean contains(T x, AVLNode<T> t) {while (t != null)

{int compareResult = x.compareTo(t.element);

if (compareResult < 0)

t = t.left;

else if (compareResult > 0)

t = t.right;

else

return true;}

return false;}

/*** Insert a new item to the AVL tree.*

* @param x

* the item to insert.*/

public void insert(T x) {

root = insert(x, root);}

/*** Internal method to insert into a subtree.*

* @param x

* the item to insert.

* @param t

* the node that roots the subtree.

* @return the new root of the subtree.*/

private AVLNode<T> insert(T x, AVLNode<T> t) {

if (t == null)

return new AVLNode<T>(x);

int compareResult = x.compareTo(t.element);

if (compareResult < 0)

{t.left = insert(x, t.left);

if (height(t.left) - height(t.right) == 2)

if (x.compareTo(t.left.element) < 0)

t = rotateWithLeftChild(t);

else

t = doubleWithLeftChild(t);}

else if (compareResult > 0)

{t.right = insert(x, t.right);

if (height(t.right) - height(t.left) == 2)

if (x.compareTo(t.right.element) > 0)

t = rotateWithRightChild(t);

else

t = doubleWithRightChild(t);}

else;

t.height = Math.max(height(t.left), height(t.right)) + 1;

return t;}

/*** Return the height of root t, or -1, if null.*

* @param t

* an AVLNode.

* @return the height.*/

private int height(AVLNode<T> t) {

return t == null ? -1 : t.height}

/*** Single rotation (left-left). Update height, then return new root.*/

private AVLNode<T> rotateWithLeftChild(AVLNode<T> z) {

AVLNode<T> y = z.left;

z.left = y.right;

y.right = z;

z.height = Math.max(height(z.left), height(z.right)) + 1;

y.height = Math.max(height(y.left), z.height) + 1;

return y;}

/*** Single rotation (right-right). Update height, then return new root.*/

private AVLNode<T> rotateWithRightChild(AVLNode<T> z) {

AVLNode<T> y = z.right;

z.right = y.left;

y.left = z;

z.height = Math.max(height(z.left), height(z.right)) + 1;

y.height = Math.max(height(y.right), z.height) + 1;

return y;}

/*** Double rotation (left-right).*/

private AVLNode<T> doubleWithLeftChild(AVLNode<T> z)

{z.left = rotateWithRightChild(z.left);

return rotateWithLeftChild(z);}

/*** Double rotation (right-left).*/

private AVLNode<T> doubleWithRightChild(AVLNode<T> z) {

z.right = rotateWithLeftChild(z.right);

return rotateWithRightChild(z);}

/**Remove item x.*/

public void remove(T x)

{root = remove(x, root);}

/*** Remove item x from subtree t.

* @param x the item to be removed.

* @param t the node that roots the subtree.

* @return the new root of the subtree.*/

private AVLNode<T> remove(T x, AVLNode<T> t) {

if (t == null)

return t;

int compareResult = x.compareTo(t.element);

if (compareResult < 0) {

t.left = remove(x, t.left);

if (height(t.right) - height(t.left) == 2)

if (height(t.right.left) < height(t.right.right))

t = rotateWithRightChild(t);

else

t = doubleWithRightChild(t);}

else if (compareResult > 0)

{t.right = remove(x, t.right);

if (height(t.left) - height(t.right) == 2)

if (height(t.left.left) > height(t.left.right))

t = rotateWithLeftChild(t);

else

t = doubleWithLeftChild(t);}

else if (t.left != null && t.right != null)

{t.element = findMin(t.right).element;

t.right = remove(t.element, t.right);

if (height(t.left) - height(t.right) == 2)

if (height(t.left.left) > height(t.left.right))

t = rotateWithLeftChild(t);

else

t = doubleWithLeftChild(t);}

else

{t = (t.left != null) ? t.left : t.right;}

if (t != null)

t.height = Math.max(height(t.left), height(t.right)) + 1;

return t;}

public T findMin()

{if (isEmpty())

return null;

return findMin(root).element;}

private AVLNode<T> findMin(AVLNode<T> t) {

while (t.left != null)

t = t.left;

return t;}

public T findMax()

{if (isEmpty())

return null;

return findMax(root).element;}

private AVLNode<T> findMax(AVLNode<T> t) {

while (t.right != null)

t = t.right;

return t;}

public void makeEmpty()

{root = null;}

public boolean isEmpty()

{return root == null;}

/** Internal class AVLNode */

private static class AVLNode<T>

{T element;

AVLNode<T> left;

AVLNode<T> right;

int height;

public AVLNode(T element)

{this(element, null, null);}

public AVLNode(T element, AVLNode<T> left, AVLNode<T> right)

{this.element = element;

this.left = left;

this.right = right;

this.height = 0;}}}

AVL