先入先出的数据结构（FIFO）

Queue接口，与List、Set同级别，继承了Collection接口

非阻塞：

PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。

ConcurrentLinkedQueue 无界线程安全，采用CAS机制是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大小

阻塞：

*ArrayBlockingQueue ：一个由数组支持的有界队列。有界
* LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。无界
* PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。
* DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。
* SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

阻塞队列的操作

add 增加一个元素 ，如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素    如果队列为空，则抛出一个NoSuchElementException异常
element 返回队列头部的元素             如果队列为空，则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true       如果队列已满，则返回false
poll 移除并返问队列头部的元素    如果队列为空，则返回null
peek 返回队列头部的元素             如果队列为空，则返回null
put 添加一个元素                      如果队列满，则阻塞
take 移除并返回队列头部的元素     如果队列为空，则阻塞

remove、element、offer 、poll、peek 其实是属于Queue接口

LinkedBlockingQueue的容量是没有上限的（说的不准确，在不指定时容量为Integer.MAX_VALUE，不要然的话在put时怎么会受阻呢），但是也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。

ArrayBlockingQueue在构造时需要指定容量， 并可以选择是否需要公平性，如果公平参数被设置true，等待时间最长的线程会优先得到处理（其实就是通过将ReentrantLock设置为true来 达到这种公平性的：即等待时间最长的线程会先操作）。通常，公平性会使你在性能上付出代价，只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队 列，此队列按 FIFO（先进先出）原则对元素进行排序。

PriorityBlockingQueue是一个带优先级的 队列，而不是先进先出队列。元素按优先级顺序被移除，该队列也没有上限（看了一下源码，PriorityBlockingQueue是对 PriorityQueue的再次包装，是基于堆数据结构的，而PriorityQueue是没有容量限制的，与ArrayList一样，所以在优先阻塞 队列上put时是不会受阻的。虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError），但是如果队列为空，那么取元素的操作take就会阻塞，所以它的检索操作take是受阻的。另外，往入该队列中的元 素要具有比较能力。

DelayQueue（基于PriorityQueue来实现的）是一个存放Delayed 元素的无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于或等于零的值时，则出现期满，poll就以移除这个元素了。此队列不允许使用 null 元素。

LinkedList、ConcurrentLinkedQueue、LinkedBlockingQueue对比分析

---| Itreable      接口 实现该接口可以使用增强for循环
				---| Collection		描述所有集合共性的接口
					---| List接口	    可以有重复元素的集合
                            ---| ArrayList   
                            ---|  LinkedList
					---| Set接口	    不可以有重复元素的集合
                            ---| HashSet  线程不安全，存取速度快。底层是以哈希表实现的。

HashSet不存入重复元素的规则.使用hashcode和equals.

把对象加入HashSet时，HashSet会使用对象的hashCode来判断对象加入的位置。同时也会与其他已经加入的对象的hashCode进行比较，如果没有相等的hashCode，HashSet就会假设对象没有重复出现。因此我们自定义类的时候需要重写hashCode，来确保对象具有相同的hashCode值。如果元素(对象)的hashCode值相同,是不是就无法存入HashSet中了? 当然不是,会继续使用equals 进行比较.如果 equals为true 那么HashSet认为新加入的对象重复了,所以加入失败。如果equals 为false那么HashSet 认为新加入的对象没有重复.新元素可以存入

总结：
元素的哈希值是通过元素的hashcode方法 来获取的, HashSet首先判断两个元素的哈希值，如果哈希值一样，接着会比较equals方法 如果 equls结果为true ，HashSet就视为同一个元素。如果equals 为false就不是同一个元素。

哈希值相同equals为false的元素是怎么存储呢,就是在同样的哈希值下顺延（可以认为哈希值相同的元素放在一个哈希桶中）。也就是哈希一样的存一列。
HashSet：通过hashCode值来确定元素在内存中的位置。一个hashCode位置上可以存放多个元素。
当hashcode() 值相同equals() 返回为true 时,hashset 集合认为这两个元素是相同的元素.只存储一个（重复元素无法放入）。调用原理:先判断hashcode 方法的值,如果相同才会去判断equals 如果不相同,是不会调用equals方法的。

public class Demo4 {
	public static void main(String[] args) {
		// Set 集合存和取的顺序不一致。
		Set hs = new HashSet();
		hs.add("世界军事");
		hs.add("兵器知识");
		hs.add("舰船知识");
		hs.add("汉和防务");
 
		// 返回此 set 中的元素的数量
		System.out.println(hs.size()); // 4
 
		// 如果此 set 尚未包含指定元素，则返回 true
		boolean add = hs.add("世界军事"); // false
		System.out.println(add);
 
		// 返回此 set 中的元素的数量
		System.out.println(hs.size());// 4
		Iterator it = hs.iterator();
		while (it.hasNext()) {
			System.out.println(it.next());
		}
	}
}

现在有一批数据，要求不能重复存储元素，而且要排序。ArrayList 、 LinkedList不能去除重复数据。HashSet可以去除重复，但是是无序。
TreeSet集合就应运而生了。

public class Demo5 {
	public static void main(String[] args) {
		TreeSet ts = new TreeSet();
		ts.add("ccc");
		ts.add("aaa");
		ts.add("ddd");
		ts.add("bbb");
 
		System.out.println(ts); // [aaa, bbb, ccc, ddd]
 
	}
}

---| Itreable      接口 实现该接口可以使用增强for循环
				---| Collection		描述所有集合共性的接口
					---| List接口	    有序，可以重复，有角标的集合
                            ---| ArrayList   
                            ---|  LinkedList
					---| Set接口	    无序，不可以重复的集合
                            ---| HashSet  线程不安全，存取速度快。底层是以hash表实现的。
                            ---| TreeSet  红-黑树的数据结构，默认对元素进行自然排序（String）。如果在比较的时候两个对象返回值为0，那么元素重复

红黑树

规则：左小右大

既然TreeSet可以自然排序,那么TreeSet必定是有排序规则的。

1. 自定义比较规则
2. 给TreeSet指定排序规则

方式二：容器具备比较性

当元素自身不具备比较性，或者自身具备的比较性不是所需要的，那么此时可以让容器自身具备，需要定义一个类实现接口Comparator，重写compare方法，并将该接口的子类实例对象作为参数传递给TreeMap集合的构造方法。

注意：当Comparable比较方式和Comparator比较方式同时存在时，以Comparator的比较方式为主；

在重写compareTo或者compare方法时，必须要明确比较的主要条件相等时要比较次要条件。（假设姓名和年龄一直的人为相同的人，如果想要对人按照年龄的大小来排序，如果年龄相同的人，需要如何处理？不能直接return 0，因为可能姓名不同（年龄相同姓名不同的人是不同的人）。此时就需要进行次要条件判断（需要判断姓名），只有姓名和年龄同时相等的才可以返回0.）
通过return 0来判断唯一性。

为什么使用TreeSet存入字符串,字符串默认输出是按升序排列的?因为字符串实现了一个接口,叫做Comparable 接口.字符串重写了该接口的compareTo 方法,所以String对象具备了比较性.那么同样道理,我的自定义元素(例如Person类,Book类)想要存入TreeSet集合,就需要实现该接口,也就是要让自定义对象具备比较性.

TreeSet属于Set集合，该集合的元素是不能重复的，TreeSet如何保证元素的唯一性

通过compareTo或者compare方法中的来保证元素的唯一性。

添加的元素必须要实现Comparable接口。当compareTo()函数返回值为0时，说明两个对象相等，此时该对象不会添加进来。

TreeSet集合排序的两种方式：

一，让元素自身具备比较性。也就是元素需要实现Comparable接口，覆盖compareTo 方法。

public class Demo4 {
	public static void main(String[] args) {
		TreeSet ts = new TreeSet();
		ts.add(new Person("aa", 20, "男"));
		ts.add(new Person("bb", 18, "女"));
		ts.add(new Person("cc", 17, "男"));
		ts.add(new Person("dd", 17, "女"));
		ts.add(new Person("dd", 15, "女"));
		ts.add(new Person("dd", 15, "女"));
 
 
		System.out.println(ts);
		System.out.println(ts.size()); // 5
 
	}
}
 
class Person implements Comparable {
	private String name;
	private int age;
	private String gender;
 
	public Person() {
 
	}
 
	public Person(String name, int age, String gender) {
 
		this.name = name;
		this.age = age;
		this.gender = gender;
	}
 
	public String getName() {
		return name;
	}
 
	public void setName(String name) {
		this.name = name;
	}
 
	public int getAge() {
		return age;
	}
 
	public void setAge(int age) {
		this.age = age;
	}
 
	public String getGender() {
		return gender;
	}
 
	public void setGender(String gender) {
		this.gender = gender;
	}
 
	@Override
	public int hashCode() {
		return name.hashCode() + age * 37;
	}
 
	public boolean equals(Object obj) {
		System.err.println(this + "equals :" + obj);
		if (!(obj instanceof Person)) {
			return false;
		}
		Person p = (Person) obj;
		return this.name.equals(p.name) && this.age == p.age;
 
	}
 
	public String toString() {
		return "Person [name=" + name + ", age=" + age + ", gender=" + gender
				+ "]";
	}
 
	@Override
	public int compareTo(Object obj) {
		
		Person p = (Person) obj;
		System.out.println(this+" compareTo:"+p);
		if (this.age > p.age) {
			return 1;
		}
		if (this.age < p.age) {
			return -1;
		}
		return this.name.compareTo(p.name);
	}
 
}

二，让容器自身具备比较性，自定义比较器。需求：当元素自身不具备比较性，或者元素自身具备的比较性不是所需的。
定义一个类实现Comparator 接口，覆盖compare方法。并将该接口的子类对象作为参数传递给TreeSet集合的构造函数。

public class Demo5 {
	public static void main(String[] args) {
		TreeSet ts = new TreeSet(new MyComparator());
		ts.add(new Book("think in java", 100));
		ts.add(new Book("java 核心技术", 75));
		ts.add(new Book("现代操作系统", 50));
		ts.add(new Book("java就业教程", 35));
		ts.add(new Book("think in java", 100));
		ts.add(new Book("ccc in java", 100));
 
		System.out.println(ts); 
	}
}
 
class MyComparator implements Comparator {
 
	public int compare(Object o1, Object o2) {
		Book b1 = (Book) o1;
		Book b2 = (Book) o2;
		System.out.println(b1+" comparator "+b2);
		if (b1.getPrice() > b2.getPrice()) {
			return 1;
		}
		if (b1.getPrice() < b2.getPrice()) {
			return -1;
		}
		return b1.getName().compareTo(b2.getName());
	}
 
}
 
class Book {
	private String name;
	private double price;
 
	public Book() {
 
	}
 
	public String getName() {
		return name;
	}
 
	public void setName(String name) {
		this.name = name;
	}
 
	public double getPrice() {
		return price;
	}
 
	public void setPrice(double price) {
		this.price = price;
	}
 
	public Book(String name, double price) {
 
		this.name = name;
		this.price = price;
	}
 
	@Override
	public String toString() {
		return "Book [name=" + name + ", price=" + price + "]";
	}
 
}

LinkedHashSet

会保存插入的顺序。

看到array，就要想到角标。

看到link，就要想到first，last。

看到hash，就要想到hashCode,equals.

看到tree，就要想到两个接口。Comparable，Comparator。

List主要分为3类，ArrayList， LinkedList和Vector

List是一个有序的集合，和set不同的是，List允许存储项的值为空，也允许存储相等值的存储项

ArraryList

ArrayList是一个数组实现的列表，由于数据是存入数组中的，所以它的特点也和数组一样，查询很快，但是中间部分的插入和删除很慢。

Vector

Vector就是ArrayList的线程安全版，它的方法前都加了synchronized锁，其他实现逻辑都相同。
如果对线程安全要求不高的话，可以选择ArrayList，毕竟synchronized也很耗性能

LinkedList

故名思意就是链表，和我们大学在数据结构里学的链表是一会事，LinkedList还是一个双向链表。

LinkedList继承于AbstractSequentialList,和ArrayList一个套路。内部维护了3个成员变量，一个是当前链表的头节点，一个是尾部节点，还有是链表长度。然后我们在来看下Node这个数据结构

通过上面对ArrayList和LinkedList的分析，可以理解List的3个特性
1.是按顺序查找
2.允许存储项为空
3.允许多个存储项的值相等

• 通用Map：用于在应用程序中管理映射，通常在 java.util 程序包中实现 HashMap、Hashtable、Properties、LinkedHashMap、IdentityHashMap、TreeMap、WeakHashMap、ConcurrentHashMap
• 专用Map：通常我们不必亲自创建此类Map，而是通过某些其他类对其进行访问 java.util.jar.Attributes、javax.print.attribute.standard.PrinterStateReasons、java.security.Provider、java.awt.RenderingHints、javax.swing.UIDefaults
• 自行实现Map：一个用于帮助我们实现自己的Map类的抽象类 AbstractMap

栈是一种用于存储数据的简单数据结构，有点类似链表或者顺序表（统称线性表），栈与线性表的最大区别是数据的存取的操作，我们可以这样认为栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)，同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素，则称为空栈，

栈的基本操作创建栈，判空，入栈，出栈，获取栈顶元素等，注意栈不支持对指定位置进行删除，插入，其接口Stack声明如下：

public interface Stack<T>{
    //栈是否为空
    boolean isEmpty();
    
    //元素入栈
    void push(T data);
    
    //返回栈顶元素，未出栈
    T peek();
    
    //出栈，返回栈顶元素，同时从栈中移除元素
    T pop();
}

顺序栈

public class SeqStack<T> implements Stack<T>,Serializable{
    private static final long serialVersionUID = -5413303117698554397L;
    
    //栈顶指针，-1表示空栈
    private int top = -1;
    //容量默认为10
    private int capacity = 10;
    
    //存放元素的数组
    private T[] array;
    
    private int size;
    public SeqStack(int capacity){
        array = (T[])new Object[capacity];
    }
    public SeqStack(){
        array = (T[])new Object[this.capacity];
    }
    //……其他代码

其获取栈顶元素值的peek操作

代码如下：

//获取栈顶元素的值，不删除
@Override
public T peek(){
    if(isEmpty()){
        new EmptyStackException();
    }
    return array[top];
}

从栈添加元素的过程如下（更新栈顶top指向）：

@Override
public void push(T data){
    //判断容量是否充足
    if(array.length==size){
        ensureCapacity(size*2+1);//扩容
        
        //从栈顶添加元素
        array[++top]=data;
    }
}

栈弹出栈顶元素的过程如下（删除并获取值）：

@Override
public T pop(){
    if(isEmpty()){
        new EmptyStackException();
    }
    size--;
    return array[top--];
}

到此，顺序栈的主要操作已实现完，是不是发现很简单，确实如此，栈的主要操作就这样，当然我们也可以通过前一篇介绍的MyArrayList作为基础来实现顺序栈，这个也比较简单，后面也会提供带代码，这里就不过多啰嗦了。下面给出顺序栈的整体实现代码：

package com.zejian.structures.Stack;

import java.io.Serializable;
import java.util.EmptyStackException;

/**
 * Created by zejian on 2016/11/27.
 * Blog : http://blog.csdn.net/javazejian/article/details/53362993 [原文地址,请尊重原创]
 * 顺序栈的实现
 */
public class SeqStack<T> implements Stack<T>,Serializable {

    private static final long serialVersionUID = -5413303117698554397L;

    /**
     * 栈顶指针,-1代表空栈
     */
    private int top=-1;

    /**
     * 容量大小默认为10
     */
    private int capacity=10;

    /**
     * 存放元素的数组
     */
    private T[] array;

    private int size;

    public SeqStack(int capacity){
        array = (T[]) new Object[capacity];
    }

    public SeqStack(){
        array= (T[]) new Object[this.capacity];
    }

    public  int size(){
        return size;
    }


    @Override
    public boolean isEmpty() {
        return this.top==-1;
    }

    /**
     * 添加元素,从栈顶(数组尾部)插入
     * @param data
     */
    @Override
    public void push(T data) {
        //判断容量是否充足
        if(array.length==size)
            ensureCapacity(size*2+1);//扩容

        //从栈顶添加元素
        array[++top]=data;

        size++;
    }

    /**
     * 获取栈顶元素的值,不删除
     * @return
     */
    @Override
    public T peek() {
        if(isEmpty())
            new EmptyStackException();
        return array[top];
    }

    /**
     * 从栈顶(顺序表尾部)删除
     * @return
     */
    @Override
    public T pop() {
        if(isEmpty())
            new EmptyStackException();
        size--;
        return array[top--];
    }

    /**
     * 扩容的方法
     * @param capacity
     */
    public void ensureCapacity(int capacity) {
        //如果需要拓展的容量比现在数组的容量还小,则无需扩容
        if (capacity<size)
            return;

        T[] old = array;
        array = (T[]) new Object[capacity];
        //复制元素
        for (int i=0; i<size ; i++)
            array[i]=old[i];
    }

    public static void main(String[] args){
        SeqStack<String> s=new SeqStack<>();
        s.push("A");
        s.push("B");
        s.push("C");
        System.out.println("size->"+s.size());
        int l=s.size();//size 在减少,必须先记录
        for (int i=0;i<l;i++){
            System.out.println("s.pop->"+s.pop());
        }

        System.out.println("s.peek->"+s.peek());
    }
}

链式栈

链式栈（Linked Stack），就是采用链式存储结构的栈，由于我们操作的是栈顶一端，因此这里采用单链表（不带头结点）作为基础，直接实现栈的添加，获取，删除等主要操作即可。

从图可以看出，无论是插入还是删除直接操作的是链表头部也就是栈顶元素，因此我们只需要使用不带头结点的单链表即可。

package com.zejian.structures.Stack;

import com.zejian.structures.LinkedList.singleLinked.Node;

import java.io.Serializable;

/**
 * Created by zejian on 2016/11/27.
 * Blog : http://blog.csdn.net/javazejian/article/details/53362993 [原文地址,请尊重原创]
 * 栈的链式实现
 */
public class LinkedStack<T> implements Stack<T> ,Serializable{

    private static final long serialVersionUID = 1911829302658328353L;

    private Node<T> top;

    private int size;

    public LinkedStack(){
        this.top=new Node<>();
    }

    public int size(){
        return size;
    }


    @Override
    public boolean isEmpty() {
        return top==null || top.data==null;
    }

    @Override
    public void push(T data) {
        if (data==null){
            throw new StackException("data can\'t be null");
        }
        if(this.top==null){//调用pop()后top可能为null
            this.top=new Node<>(data);
        }else if(this.top.data==null){
            this.top.data=data;
        }else {
           Node<T> p=new Node<>(data,this.top);
            top=p;//更新栈顶
        }
        size++;
    }

    @Override
    public T peek()  {
        if(isEmpty()){
            throw new EmptyStackException("Stack empty");
        }

        return top.data;
    }

    @Override
    public T pop() {
        if(isEmpty()){
            throw new EmptyStackException("Stack empty");
        }

        T data=top.data;
        top=top.next;
        size--;
        return data;
    }
    //测试
    public static void main(String[] args){
        LinkedStack<String> sl=new LinkedStack<>();
        sl.push("A");
        sl.push("B");
        sl.push("C");
        int length=sl.size();
        for (int i = 0; i < length; i++) {
            System.out.println("sl.pop->"+sl.pop());
        }
    }
}

顺序栈与链式栈中各个操作的算法复杂度（时间和空间）对比，顺序栈复杂度如下：

链式栈复杂度如下：

栈的应用：

• 符号匹配
• 中缀表达式转换为后缀表达式
• 计算后缀表达式
• 实现函数的嵌套调用
• HTML和XML文件中的标签匹配
• 网页浏览器中已访问页面的历史记录

符号匹配
在编写程序的过程中，我们经常会遇到诸如圆括号“()”与花括号“{}”，这些符号都必须是左右匹配的，这就是我们所说的符合匹配类型，当然符合不仅需要个数相等，而且需要先左后右的依次出现，否则就不符合匹配规则，如“)(”，明显是错误的匹配，而“()”才是正确的匹配。有时候符合如括号还会嵌套出现，如“9-(5+(5+1))”,而嵌套的匹配原则是一个右括号与其前面最近的一个括号匹配，事实上编译器帮我检查语法错误是也是执行一样的匹配原理，而这一系列操作都需要借助栈来完成，接下来我们使用栈来实现括号”()”是否匹配的检测。
判断原则如下（str=”((5-3)*8-2)”）：

a.设置str是一个表达式字符串，从左到右依次对字符串str中的每个字符char进行语法检测，如果char是，左括号则入栈，如果char是右括号则出栈(有一对匹配就可以去匹配一个左括号，因此可以出栈)，若此时出栈的字符char为左括号，则说明这一对括号匹配正常，如果此时栈为空或者出栈字符不为左括号，则表示缺少与char匹配的左括号，即目前不完整。
b.重复执行a操作，直到str检测结束，如果此时栈为空，则全部括号匹配，如果栈中还有左括号，是说明缺少右括号。

package com.zejian.structures.Stack;

/**
* 表达式检测
*/
public class CheckExpression {

  public static String isValid(String expstr)
  {
      //创建栈
      LinkedStack<String> stack = new LinkedStack<>();

      int i=0;
      while(i<expstr.length())
      {
          char ch=expstr.charAt(i);
          i++;
          switch(ch)
          {
              case '(': stack.push(ch+"");//左括号直接入栈
                  break;
              case ')': if (stack.isEmpty() || !stack.pop().equals("(")) //遇见右括号左括号直接出栈
                  return "(";
          }
      }
      //最后检测是否为空,为空则检测通过
      if(stack.isEmpty())
          return "check pass!";
      else
          return "check exception!";
  }

  public static void main(String args[])
  {
      String expstr="((5-3)*8-2)";
      System.out.println(expstr+"  "+isValid(expstr));
  }
}

中缀表达式转换为后缀表达式

//1+3*(9-2)+9 --->中缀表达式（跟日常见到的表达式没啥区别）

在后缀表达式中，运算符是没有优先级的，整个计算都是遵守从左往右的次序依次计算的，如下我们将中缀表达式转为后缀表达式：

//1+3*(9-2)+9        转化前的中缀表达式
//1 3 9 2 - * + 9 +  转化后的后缀表达式

中缀转后缀的转换过程需要用到栈，这里我们假设栈A用于协助转换，并使用数组B用于存放转化后的后缀表达式具体过程如下：
1）如果遇到操作数，我们就直接将其放入数组B中。
2）如果遇到运算符，则我们将其放入到栈A中，遇到左括号时我们也将其放入栈A中。
3）如果遇到一个右括号，则将栈元素弹出，将弹出的运算符输出并存入数组B中直到遇到左括号为止。注意，左括号只弹出并不存入数组。
4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素存入数组B直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到” ) “的情况下我们才弹出” ( “，其他情况我们都不会弹出” ( “。
5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出存入到数组B中。
6）到此中缀表达式转化为后缀表达式完成，数组存储的元素顺序就代表转化后的后缀表达式。
执行图示过程如下：


简单分析一下流程，当遇到操作数时（规则1），直接存入数组B中，当i=1（规则2）时，此时运算符为+，直接入栈，当i=3(规则2)再遇到运算符*，由于栈内的运算符+优先级比*低，因此直接入栈，当i=4时，遇到运算符’(‘，直接入栈，当i=6时，遇运算符-，直接入栈，当i=8时（规则3），遇’)’，-和’(‘直接出栈，其中运算符-存入后缀数组B中，当i=9时（规则5），由于*优先级比+高，而+与+平级，因此和+出栈，存入数组B，而后面的+再入栈，当i=10（规则5），结束，+直接出栈存入数组B，此时数组B的元素顺序即为1 3 9 2 - * + 9 +，这就是中缀转后缀的过程。
接着转成后缀后，我们来看看计算机如何利用后缀表达式进行结果运算，通过前面的分析可知，后缀表达式是没有括号的，而且计算过程是按照从左到右依次进行的，因此在后缀表达的求值过程中，当遇到运算符时，只需要取前两个操作数直接进行计算即可，而当遇到操作数时不能立即进行求值计算，此时必须先把操作数保存等待获取到运算符时再进行计算，如果存在多个操作数，其运算次序是后出现的操作数先进行运算，也就是后进先运算，因此后缀表达式的计算过程我们也需要借助栈来完成，该栈用于存放操作数，后缀表达式的计算过程及其图解如下：

package com.zejian.structures.Stack;

/**
* Created by zejian on 2016/11/28.
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
* 中缀转后缀,然后计算后缀表达式的值
*/
public class CalculateExpression {

  /**
   * 中缀转后缀
   * @param expstr 中缀表达式字符串
   * @return
   */
  public static String toPostfix(String expstr)
  {
      //创建栈,用于存储运算符
      SeqStack<String> stack = new SeqStack<>(expstr.length());

      String postfix="";//存储后缀表达式的字符串
      int i=0;
      while (i<expstr.length())
      {
          char ch=expstr.charAt(i);
          switch (ch)
          {
              case '+':
              case '-':
                  //当栈不为空或者栈顶元素不是左括号时,直接出栈,因此此时只有可能是*/+-四种运算符(根据规则4),否则入栈
                  while (!stack.isEmpty() && !stack.peek().equals("(")) {
                      postfix += stack.pop();
                  }
                  //入栈
                  stack.push(ch+"");
                  i++;
                  break;
              case '*':
              case '/':
                  //遇到运算符*/
                  while (!stack.isEmpty() && (stack.peek().equals("*") || stack.peek().equals("/"))) {
                      postfix += stack.pop();
                  }
                  stack.push(ch+"");
                  i++;
                  break;
              case '(':
                  //左括号直接入栈
                  stack.push(ch+"");
                  i++;
                  break;
              case ')':
                  //遇到右括号(规则3)
                  String out = stack.pop();
                  while (out!=null && !out.equals("("))
                  {
                      postfix += out;
                      out = stack.pop();
                  }
                  i++;
                  break;
              default:
                  //操作数直接入栈
                  while (ch>='0' && ch<='9')
                  {
                      postfix += ch;
                      i++;
                      if (i<expstr.length())
                          ch=expstr.charAt(i);
                      else
                          ch='=';
                  }
                  //分隔符
                  postfix += " ";
                  break;
          }
      }
      //最后把所有运算符出栈(规则5)
      while (!stack.isEmpty())
          postfix += stack.pop();
      return postfix;
  }

  /**
   * 计算后缀表达式的值
   * @param postfix 传入后缀表达式
   * @return
   */
  public static int calculatePostfixValue(String postfix)
  {
      //栈用于存储操作数,协助运算
      LinkedStack<Integer> stack = new LinkedStack<>();
      int i=0, result=0;
      while (i<postfix.length())
      {
          char ch=postfix.charAt(i);
          if (ch>='0' && ch<='9')
          {
              result=0;
              while (ch!=' ')
              {
                  //将整数字符转为整数值ch=90
                  result = result*10 + Integer.parseInt(ch+"");
                  i++;
                  ch = postfix.charAt(i);
              }
              i++;
              stack.push(result);//操作数入栈
          }
          else
          {  //ch 是运算符,出栈栈顶的前两个元素
              int y= stack.pop();
              int x= stack.pop();
              switch (ch)
              {   //根据情况进行计算
                  case '+': result=x+y; break;
                  case '-': result=x-y; break;
                  case '*': result=x*y; break;
                  case '/': result=x/y; break;   //注意这里并没去判断除数是否为0的情况
              }
              //将运算结果入栈
              stack.push(result);
              i++;
          }
      }
      //将最后的结果出栈并返回
      return stack.pop();
  }
  //测试
  public static void main(String args[])
  {
      String expstr="1+3*(9-2)+90";
      String postfix = toPostfix(expstr);
      System.out.println("中缀表达式->expstr=  "+expstr);
      System.out.println("后缀表达式->postfix= "+postfix);
      System.out.println("计算结果->value= "+calculatePostfixValue(postfix));
  }

}

有序数组的优势在于二分查找，链表的优势在于数据项的插入和数据项的删除。但是在有序数组中插入数据就会很慢，同样在链表中查找数据项效率就很低。综合以上情况，二叉树可以利用链表和有序数组的优势，同时可以合并有序数组和链表的优势，二叉树也是一种常用的数据结构。
创建一个树的节点（包括左右子树）

//创建树节点
//创建一个树的节点
//每个node存放两个数据
//一个左node引用和一个右node引用
class Node
{
    public  int iData;
    public double dData;
    public Node leftNode;
    public Node rightNode;
    //显示树节点信息
    public void showNode()
    {
        System.out.println("{ "+iData+","+dData+" }");
    }
}

对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。又叫AVL树

平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

结点插入

1、6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左。

2、6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右。

3、2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左。

4、2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右。

从图2中可以可以看出，1和4两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，我们称之为单旋转。2和3两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，我们称之为双旋转。

单旋转是针对于左左和右右这两种情况的解决方案，这两种情况是对称的，只要解决了左左这种情况，右右就很好办了。图3是左左情况的解决方案，节点k2不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的左子树X子树，所以属于左左情况。

为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。

这样的操作只需要一部分指针改变，结果我们得到另外一颗二叉查找树，它是一棵AVL树，因为X向上一移动了一层，Y还停留在原来的层面上，Z向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同，插入操作使得X高度长高了。因此，由于这颗子树高度没有变化，所以通往根节点的路径就不需要继续旋转了。

void R_rotate(BiTree *t)
{
         BiTree s;
         s = (*t)->lchild;                    //s指向t的左子树根结点
         (*t)->lchild = s->rchild;          //s的右子树挂接为t的左子树
         s->rchild = (*t);
         *t = s;                                //t指向新的根结点
}

右旋转原理：获取失去平衡结点以及左结点，为了让lchild作为根节点，将lchild的rchild挂接到之前左结点上，然后在挂接到s->rchild.

void L_rotate(BiTree *t)
{
         BiTree s;
         s = (*t)->rchild;                    //s指向t的右子树根结点
         (*t)->rchild = s->lchild;          //s的左子树挂接为t的右子树
         s->lchild = (*t);
         *t = s;                                //t指向新的根结点
}

左旋转原理正好相反，让其右结点作为根节点

双旋转

对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。双旋转是针对于这两种情况的解决方案，同样的，这样两种情况也是对称的，只要解决了左右这种情况，右左就很好办了。图4是左右情况的解决方案，节点k3不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的右子树k2子树，所以属于左右情况。

为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次z左旋转，旋转之后就变成了左左情况，所以第二步再进行一次右旋转，最后得到了一棵以k2为根的平衡二叉树树。

#define LH +1 /*  左高 */ 
#define EH 0  /*  等高 */ 
#define RH -1 /*  右高 */ 
 
/*  对以指针T所指结点为根的二叉树作左平衡旋转处理 */
/*  本算法结束时，指针T指向新的根结点 */
void LeftBalance(BiTree *T)
{ 
    BiTree L,Lr;
    L = (*T)->lchild;                                      /*  L指向T的左子树根结点 */
    switch(L->bf)
    { 
        /* 检查T的左子树的平衡度，并作相应平衡处理 */
         case LH:                   /* 新结点插入在T的左孩子的左子树上，要作单右旋处理 */
            (*T)->bf=L->bf=EH;
            R_Rotate(T);
            break;
         case RH:                   /* 新结点插入在T的左孩子的右子树上，要作双旋处理 */
            Lr=L->rchild;                    /* Lr指向T的左孩子的右子树根 */
            switch(Lr->bf)
            {   /* 修改T及其左孩子的平衡因子 */
                case LH: (*T)->bf=RH;
                         L->bf=EH;
                         break;
                case EH: (*T)->bf=L->bf=EH;
                         break;
                case RH: (*T)->bf=EH;
                         L->bf=LH;
                         break;
            }
            Lr->bf=EH;
            L_Rotate(&(*T)->lchild);         /* 对T的左子树作左旋平衡处理 */
            R_Rotate(T);             /* 对T作右旋平衡处理 */
    }
}

首先，定义三个常数变量，分别代码1、0、-1。

（1）函数被调用，传入一个需调整平衡型的子树T，根节点为k3,由于LeftBalance函数被调用时，其实是已经确认当前子树是不平衡的状态，且左子树的高度大于右子树的高度。换句话说，此时T的根结点应该是平衡因子BF的值大于1的数。k3的BF为2

（2）将T的左孩子赋值给L。L指向K1.

（3）然后是分支判断。

（4）当L（k1)的平衡因子为LH，即为1时，表明它与根结点的BF值符号相同，因此，将它们的BF值都改为0，并进行右旋（顺时针）操作，是左左情况

（5）当L的平衡因子为RH时，即为-1时，表明它与根结点的BF值符号相反，此时需要做双旋操作。针对L的右孩子k2的BF作判断，修改结点T(k3)和L(k1)的BF值。将当前的Lr的BF改为0。从图中看到K2的左结点是连接到K1的右子树上，右结点连接到K3的左子树

其中当k2结点为RH，说明K2有右结点有，左结点无，k3为0（(*T)->bf=EH; ），k1就没有右结点为LH。当为Lh看程序。

（6）对根结点的左子树进行左旋，以K1为根节点进行左旋转，形成左左情况。

（7）对根结点K3进行右旋，完成平衡操作。

<strong>#include <stdio.h>    
#include <stdlib.h>   
 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100                     /* 存储空间初始分配量 */
 
typedef int Status;                     /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
 
 
/* 二叉树的二叉链表结点结构定义 */
typedef  struct BitNode                 /* 结点结构 */
{
    int data;                           /* 结点数据 */
    int bf;                             /*  结点的平衡因子 */
    struct BitNode *lchild, *rchild;    /* 左右孩子指针 */
} BitNode, *BiTree;
 
 
/* 对以p为根的二叉排序树作右旋处理 */
/* 处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */
//右旋-顺时针旋转(如LL型就得对根结点做该旋转)
void R_Rotate(BiTree *P)
{ 
    BiTree L;
    L=(*P)->lchild;                      /*  L指向P的左子树根结点 */
    (*P)->lchild=L->rchild;               /*  L的右子树挂接为P的左子树 */
    L->rchild=(*P);
    *P=L;                               /*  P指向新的根结点 */
}
 
/* 对以P为根的二叉排序树作左旋处理， */
/* 处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0  */
//左旋-逆时针旋转(如RR型就得对根结点做该旋转)
void L_Rotate(BiTree *P)
{ 
    BiTree R;
    R = (*P)->rchild;                    /* R指向P的右子树根结点 */
    (*P)->rchild = R->lchild;         /* R的左子树挂接为P的右子树 */
    R->lchild = (*P);
    *P = R;                             /* P指向新的根结点 */
}
 
#define LH +1                           /*  左高 */ 
#define EH 0                            /*  等高 */ 
#define RH -1                           /*  右高 */ 
 
/*  对以指针T所指结点为根的二叉树作左平衡旋转处理 */
/*  本算法结束时，指针T指向新的根结点 */
void LeftBalance(BiTree *T)
{ 
    BiTree L,Lr;
    L = (*T)->lchild;                    /*  L指向T的左子树根结点 */
    switch(L->bf)
    { 
        /* 检查T的左子树的平衡度，并作相应平衡处理 */
        case LH:                        /* 新结点插入在T的左孩子的左子树上，要作单右旋处理 */
            (*T)->bf=L->bf=EH;
            R_Rotate(T);
            break;
        case RH:                        /* 新结点插入在T的左孩子的右子树上，要作双旋处理 */ //
            Lr=L->rchild;                /* Lr指向T的左孩子的右子树根 */
            switch(Lr->bf)
            {   
                /* 修改T及其左孩子的平衡因子 */
                case LH: 
                    (*T)->bf=RH;
                    L->bf=EH;
                    break;
                case EH: 
                    (*T)->bf=L->bf=EH;
                    break;
                case RH: 
                    (*T)->bf=EH;
                    L->bf=LH;
                    break;
            }
            Lr->bf=EH;
            L_Rotate(&(*T)->lchild); /* 对T的左子树作左旋平衡处理 */
            R_Rotate(T);                /* 对T作右旋平衡处理 */
    }
}
 
/*  对以指针T所指结点为根的二叉树作右平衡旋转处理， */
/*  本算法结束时，指针T指向新的根结点 */
void RightBalance(BiTree *T)
{ 
    BiTree R,Rl;
    R=(*T)->rchild;                      /*  R指向T的右子树根结点 */
    switch(R->bf)
    { 
        /*  检查T的右子树的平衡度，并作相应平衡处理 */
        case RH:                        /*  新结点插入在T的右孩子的右子树上，要作单左旋处理 */
            (*T)->bf=R->bf=EH;
            L_Rotate(T);
            break;
        case LH:                        /*  新结点插入在T的右孩子的左子树上，要作双旋处理 */ //最小不平衡树的根结点为负，其右孩子为正
            Rl=R->lchild;                /*  Rl指向T的右孩子的左子树根 */
            switch(Rl->bf)
            { 
                /*  修改T及其右孩子的平衡因子 */
                case RH: 
                    (*T)->bf=LH;
                    R->bf=EH;
                    break;
                case EH: 
                    (*T)->bf=R->bf=EH;
                    break;
                case LH: 
                    (*T)->bf=EH;
                    R->bf=RH;
                    break;
            }
            Rl->bf=EH;
            R_Rotate(&(*T)->rchild); /*  对T的右子树作右旋平衡处理 */
            L_Rotate(T);                /*  对T作左旋平衡处理 */
    }
}
 
/*  若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */
/*  数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */
/*  失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。 */
Status InsertAVL(BiTree *T,int e,Status *taller)
{  
    if(!*T)
    { 
        /*  插入新结点，树“长高”，置taller为TRUE */
        *T=(BiTree)malloc(sizeof(BitNode));
        (*T)->data=e; 
        (*T)->lchild=(*T)->rchild=NULL; 
        (*T)->bf=EH;
        *taller=TRUE;
    }
    else
    {
        if (e==(*T)->data)
        { 
            /*  树中已存在和e有相同关键字的结点则不再插入 */
            *taller=FALSE; 
            return FALSE;
        }
        if (e<(*T)->data)
        { 
            /*  应继续在T的左子树中进行搜索 */
            if(!InsertAVL(&(*T)->lchild, e, taller)) /*  未插入 */
                return FALSE;
            if(*taller)                             /*   已插入到T的左子树中且左子树“长高” */
                switch((*T)->bf)                 /*  检查T的平衡度 */
                {
                    case LH:                        /*  原本左子树比右子树高，需要作左平衡处理 */
                        LeftBalance(T); 
                        *taller=FALSE; 
                        break;
                    case EH:                        /*  原本左、右子树等高，现因左子树增高而使树增高 */
                        (*T)->bf=LH; 
                        *taller=TRUE; 
                        break;
                    case RH:                        /*  原本右子树比左子树高，现左、右子树等高 */ 
                        (*T)->bf=EH; 
                        *taller=FALSE; 
                        break;
                }
        }
        else
        { 
            /*  应继续在T的右子树中进行搜索 */
            if(!InsertAVL(&(*T)->rchild,e, taller)) /*  未插入 */
            {
                return FALSE;
            }
            if(*taller)                             /*  已插入到T的右子树且右子树“长高” */
            {
                switch((*T)->bf)                 /*  检查T的平衡度 */
                {
                    case LH:                        /*  原本左子树比右子树高，现左、右子树等高 */
                        (*T)->bf=EH; 
                        *taller=FALSE;  
                        break;
                    case EH:                        /*  原本左、右子树等高，现因右子树增高而使树增高  */
                        (*T)->bf=RH; 
                        *taller=TRUE; 
                        break;
                    case RH:                        /*  原本右子树比左子树高，需要作右平衡处理 */
                        RightBalance(T); 
                        *taller=FALSE; 
                        break;
                }
            }
        }
    }
    return TRUE;
}
 
 
/* 
若在平衡的二叉排序树t中存在和e有相同关键字的结点，则删除之 
并返回TRUE，否则返回FALSE。若因删除而使二叉排序树 
失去平衡，则作平衡旋转处理，布尔变量shorter反映t变矮与否
*/
int deleteAVL(BiTree *t, int key, int *shorter)
{
    if(*t == NULL)                                      //不存在该元素 
    {
        return FALSE;                                   //删除失败 
    }
    else if(key == (*t)->data)                           //找到元素结点
    {
        BitNode *q = NULL;
        if((*t)->lchild == NULL)                     //左子树为空 
        {
            q = (*t);
            (*t) = (*t)->rchild;
            free(q);
            *shorter = TRUE;
        }
        else if((*t)->rchild == NULL)                    //右子树为空 
        {
            q = (*t);
            (*t) = (*t)->lchild;
            free(q);
            *shorter = TRUE;
        }
        else                                            //左右子树都存在,
        {
            q = (*t)->lchild;
            while(q->rchild)
            {
                q = q->rchild;
            }
            (*t)->data = q->data;
            deleteAVL(&(*t)->lchild, q->data, shorter);   //在左子树中递归删除前驱结点 
        }
    }
    else if(key < (*t)->data)                         //左子树中继续查找 
    {
        if(!deleteAVL(&(*t)->lchild, key, shorter))
        {
            return FALSE;
        }
        if(*shorter)
        {
            switch((*t)->bf)
            {
            case LH:
                (*t)->bf = EH;
                *shorter = TRUE;
                break;
            case EH:
                (*t)->bf = RH;
                *shorter = FALSE;
                break;
            case RH:
                RightBalance(&(*t));        //右平衡处理
                if((*t)->rchild->bf == EH)    //注意这里，画图思考一下 
                    *shorter = FALSE;
                else
                    *shorter = TRUE;
                break;
            }
        }
    }
    else                                //右子树中继续查找 
    {
        if(!deleteAVL(&(*t)->rchild, key, shorter))
        {
            return FALSE;
        }
        if(shorter)
        {
            switch((*t)->bf)
            {
            case LH:
                LeftBalance(&(*t));         //左平衡处理 
                if((*t)->lchild->bf == EH)  //注意这里，画图思考一下 
                    *shorter = FALSE;
                else
                    *shorter = TRUE;
                break;
            case EH:
                (*t)->bf = LH;
                *shorter = FALSE;
                break;
            case RH:
                (*t)->bf = EH;
                *shorter = TRUE;
                break;
            }
        }
    }
    return TRUE;
}
 
void InOrderTraverse(BiTree t)
{
    if(t)
    {
        InOrderTraverse(t->lchild);
        printf("%d  ", t->data);
        InOrderTraverse(t->rchild);
    }
}
 
 
int main(void)
{    
    int i;
    int a[10]={3,2,1,4,5,6,7,10,9,8};
    BiTree T=NULL;
    Status taller;
    for(i=0;i<10;i++)
    {
        InsertAVL(&T,a[i],&taller);
    }
    printf("中序遍历二叉平衡树:\n");
    InOrderTraverse(T);
    printf("\n");
    printf("删除结点元素5后中序遍历:\n");
    int shorter;
    deleteAVL(&T, 5, &shorter);
    InOrderTraverse(T);
    printf("\n");
    return 0;
}

平衡查找树之2-3树

在一棵具有N 个节点的树中，我们希望该树的高度能够维持在lgN左右，这样我们就能保证只需要lgN次比较操作就可以查找到想要的值。不幸的是，每次插入元素之后维持树的平衡状态太昂贵。所以这里会介绍一些新的数据结构来保证在最坏的情况下插入和查找效率都能保证在对数的时间复杂度内完成。本文首先介绍2-3查找树(2-3 Search Tree)

2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：

1. 要么为空，要么：

2. 对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key有效，有节点也是一个2-3节点，所有的值比key要大。

3. 对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个根节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。

如果中序遍历2-3查找树，就可以得到排好序的序列。在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。

查找

往一个2-node节点插入

往2-3树中插入元素和往二叉查找树中插入元素一样，首先要进行查找，然后将节点挂到未找到的节点上。2-3树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态。如果查找后未找到的节点是一个2-node节点，那么很容易，我们只需要将新的元素放到这个2-node节点里面使其变成一个3-node节点即可。但是如果查找的节点结束于一个3-node节点，那么可能有点麻烦。

往一个3-node节点插入

只包含一个3-node节点

如上图，假设2-3树只包含一个3-node节点，这个节点有两个key，没有空间来插入第三个key了，最自然的方式是我们假设这个节点能存放三个元素，暂时使其变成一个4-node节点，同时他包含四个子节点。然后，我们将这个4-node节点的中间元素提升，左边的节点作为其左节点，右边的元素作为其右节点。插入完成，变为平衡2-3查找树，树的高度从0变为1。

节点是3-node，父节点是2-node

和第一种情况一样，我们也可以将新的元素插入到3-node节点中，使其成为一个临时的4-node节点，然后，将该节点中的中间元素提升到父节点即2-node节点中，使其父节点成为一个3-node节点，然后将左右节点分别挂在这个3-node节点的恰当位置。操作如下图：

节点是3-node，父节点也是3-node

当我们插入的节点是3-node的时候，我们将该节点拆分，中间元素提升至父节点，但是此时父节点是一个3-node节点，插入之后，父节点变成了4-node节点，然后继续将中间元素提升至其父节点，直至遇到一个父节点是2-node节点，然后将其变为3-node，不需要继续进行拆分。

本地转换

将一个4-node拆分为2-3node涉及到6种可能的操作。这4-node可能在跟节点，也可能是2-node的左子节点或者右子节点。或者是一个3-node的左，中，右子节点。所有的这些改变都是本地的，不需要检查或者修改其他部分的节点。所以只需要常数次操作即可完成2-3树的平衡。

性质

这些本地操作保持了2-3树的平衡。对于4-node节点变形为2-3节点，变形前后树的高度没有发生变化。只有当跟节点是4-node节点，变形后树的高度才加一。如下图所示：

分析

2-3树的查找效率与树的高度是息息相关的。

• 在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN
• 在最好的情况下，所有的节点都是3-node节点，查找效率为log₃N约等于0.631lgN

距离来说，对于1百万个节点的2-3树，树的高度为12-20之间，对于10亿个节点的2-3树，树的高度为18-30之间。

对于插入来说，只需要常数次操作即可完成，因为他只需要修改与该节点关联的节点即可，不需要检查其他节点，所以效率和查找类似。下面是2-3查找树的效率：

实现

直接实现2-3树比较复杂，因为：

1. 需要处理不同的节点类型，非常繁琐
2. 需要多次比较操作来将节点下移
3. 需要上移来拆分4-node节点
4. 拆分4-node节点的情况有很多种

2-3查找树实现起来比较复杂，在某些情况插入后的平衡操作可能会使得效率降低。在2-3查找树基础上改进的红黑树不仅具有较高的效率，并且实现起来较2-3查找树简单。

但是2-3查找树作为一种比较重要的概念和思路对于后文要讲到的红黑树和B树非常重要。